Uma máquina de Turing é uma máquina hipotética pensada pelo matemático Alan Turing em 1936. Apesar de ser desenvolvida de uma forma bem simples, pode simular qualquer algoritmo de computador, independentemente da complexidade. Analise a figura que representa a configuração inicial da fita de uma máquina de Turing, com a cabeça da máquina apontando para o terceiro espaço da fita:
Dado o conjunto de transições { (δ (A, 0) = (B, 1, D)), (δ (B, 0) = (A, 1, E)), (δ (A, 1) = (B, 1, E)), (δ (B, 0) = (A, 1, E)), (δ (A, 0) = (A, 1, D)), (δ (B, 1) = (PARADA, 1, D))} e a configuração inicial da fita, assinale a alternativa que representa a configuração final da fita depois de executar todas as transições do conjunto, em sequência.
Escolha uma:
a.
1 1 1 1 0 0 0 0, com a cabeça da máquina apontando para a quinta posição da fita.
b. 0 0 1 1 1 0 0 0, com a cabeça da máquina apontando para a quarta posição da fita.
c. 0 1 1 1 0 0 0 0, com a cabeça da máquina apontando para a segunda posição da fita.
d. 0 0 1 1 0 0 0 0, com a cabeça da máquina apontando para a terceira posição da fita.
e. 1 1 1 1 0 0 0 0, com a cabeça da máquina apontando para a terceira posição da fita.