Question

Na teoria da complexidade computacional, um problema é considerado indecidível quando, em um problema de decisão, é impossível elaborar um algoritmo que sempre leva a uma resposta correta, sendo tal resposta sim ou não.

SOARE, Robert I. Turing computability: Theory and applications. Springer, 2016.



Considerando o contexto, analise as afirmativas.



I. Existem linguagens não reconhecidas por máquinas de Turing que são decidíveis.

II. Máquinas de Turing reconhecem linguagens indecidíveis em tempo infinito.

III. Problemas indecidíveis são chamados de não recursivos.

Considerando o contexto, assinale a alternativa correta.

Escolha uma:
a.
Apenas a afirmativa III está correta.

b.
As afirmativas I, II e III estão corretas.

c.
Apenas a afirmativa I está correta.

d.
Apenas as afirmativas I e II estão corretas.

e.
Apenas as afirmativas II e III estão corretas.

Answer 1

Resposta:

Apenas a afirmativa III está correta.

Explicação: