Question

Considere a convenção de quíntuplas para representar máquinas de Turing, onde cada quíntupla está na forma . Seja a máquina de Turing não determinística dada pelas seguintes quíntuplas: ; ; .

Indique a alternativa precisa e correta sobre as computações da máquina de Turing acima, quando ela está inicialmente com a configuração .
Escolha uma:
a. Cada computação da máquina de Turing acima, iniciada com a configuração termina no estado final e resulta em um número binário qualquer de 8 bits. Idealmente qualquer número binário de 8 bits é o resultado de uma computação da máquina.
b. Cada computação evolui para uma configuração que mistura a´s, 1´s e 0´s de forma não determinística, isto é, qualquer cadeia com estes símbolos é um resultado para a computação da máquina
c. A máquina tem como resultado todos os numerais binários de 8 bits de comprimento em ordem aleatória
d. A máquina computa de forma ordenada a seguinte lista de cadeias e para. Lista de cadeias: 00000000, 00000001, 000000010, 00000011, 00000100, ....
e. Máquinas de Turing não-determinísticas não possuem resultados determinados, por isso esta questão não tem sentido.

Answer 1

CORRIGIDO PELO AVA.........

Answer 2

resposta correta

letra A do print