O problema da parada para máquinas de T… (INEP (ENEM) 2011)

Questões de Tecnologia da Informação · INEP (ENEM)

Tecnologia da InformaçãoAlgoritmos de ordenação, busca e complexidadeINEP (ENEM) 2011

ENADE

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,

Aexiste algoritmo exato de tempo de execução polinomial para solucioná-lo.Bexiste algoritmo exato de tempo de execução exponencial para solucioná-lo.Cnão existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado.Dnão existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução polinomial que o soluciona, fornecendo respostas aproximadas.Enão existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução exponencial que o soluciona, fornecendo respostas aproximadas.

Mais questões de Algoritmos de ordenação, busca e complexidade

Questão de prova oficial, com o gabarito definitivo publicado pela banca. Reproduzida para fins de estudo.