Question

O problema computacional conhecido como problema da parada (Halting Problem) foi o primeiro problema computacional ser comprovadamente insolucionável, por Alan Turing, em 1936. O objetivo é analisar se um programa computacional, executado por uma máquina de Turing, vai terminar sua execução para uma entrada, ou executar indefinidamente.

TURING, Alan Mathison. On computable numbers, with an application to the Entscheidungsproblem. J. of Math, v. 58, n. 345-363, p. 5, 1936.

Considerando o contexto, analise as afirmativas.



I. É impossível determinar se a máquina de Turing executará indefinidamente ao processar uma palavra ou cadeia.

II. É um problema decidível, visando determinar/decidir se sua execução termina ou executa indefinidamente.

III. A máquina de Turing executará indefinidamente se, e somente se, a palavra processada não fazer parte da linguagem em execução.

Considerando o contexto, assinale a alternativa correta.

Escolha uma:
a.
Apenas as afirmativas I e II estão corretas.

b.
Apenas as afirmativas I e III estão corretas. Correto

c.
Apenas a afirmativa I está correta.

d.
Apenas a afirmativa II está correta.

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

Answer 1

Resposta: Não é a Letra A

Explicação:

Answer 2

Resposta:

b. Apenas as afirmativas I e III estão corretas.