O problema da parada para máquinas de Turing, ousimplesmente problema da parada, pode ser assimdescrito: determinar, para quaisquer máquina de Turing Me palavra w, se M irá eventualmente parar com entrada w.Mais informalmente, o mesmo problema também podeser assim descrito: dados um algoritmo e uma entradafi nita, decidir se o algoritmo termina ou se executaráindefi nidamente.Para o problema da parada,A existe algoritmo exato de tempo de execuçãopolinomial para solucioná-lo.B existe algoritmo exato de tempo de execuçãoexponencial para solucioná-lo.C não existe algoritmo que o solucione, não importaquanto tempo seja disponibilizado.D não existe algoritmo exato, mas existe algoritmo deaproximação de tempo de execução polinomial que osoluciona, fornecendo respostas aproximadas.E não existe algoritmo exato, mas existe algoritmo deaproximação de tempo de execução exponencial queo soluciona, fornecendo respostas aproximadas.
#ENADE
Respostas
A resposta correta é a letra C) não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado .
Dentro da teoria da computabilidade e também do experimento mental sobre o problema de parada isso nada mais é do que um problema de decisão que pode ser identificado de forma informal com a seguinte maneira.
“conforme uma determinada descrição de um programa e uma entrada finita, cabe ao mesmo decidir se o programa irá terminar de rodar ou se irá continuar rodando de forma indefinida”.
No ano de 1936, o famoso Alan Turing conseguiu provar que um algoritmo genérico pode resolver todos os problemas de parada para todos os pares de programa de entrada.
Por isso dizem que os problemas de parada são indecidíveis para as máquinas de turing,
Bons estudos!