O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim

ENADE 2011 - QUESTÃO 11

O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim descrito: determinar, para quaisquer máquina de Turing M e palavra w, se M irá eventualmente parar com entrada w.

Mais informalmente, o mesmo problema também pode ser assim descrito: dados um algoritmo e uma entrada finita, decidir se o algoritmo termina ou se executará indefinidamente.

Para o problema da parada,

A) existe algoritmo exato de tempo de execução polinomial para solucioná-lo.

B) existe algoritmo exato de tempo de execução exponencial para solucioná-lo.

C) não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado.

D) não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução polinomial que o soluciona, fornecendo respostas aproximadas.

E) não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução exponencial que o soluciona, fornecendo respostas aproximadas.

QUESTÃO ANTERIOR:

- Em determinado período letivo, cada estudante de um curso universitário tem aulas com um de três

GABARITO:

C) não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado.

RESOLUÇÃO:

Não temos resolução para essa questão! Você sabe explicar? Copie o link dessa página e envie sua resolução clicando AQUI!

PRÓXIMA QUESTÃO:

- Considere a gramática a seguir, em que S, A e B e são símbolos não terminais, 0 e 1 são terminais e E é a cadeia vazia.

QUESTÃO DISPONÍVEL EM:

- Prova de Computação ENADE 2011 com Gabarito