Questão 11 · ENADE 2011 — Computação (INEP)

Question

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,

Accepted Answer

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

Answer

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

Answer

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

Answer

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

Answer

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

INEP, ENADE

Questões parecidas