Um dos modelos mais utilizados para descrever algoritmos de maneira formal é a máquina de Turing. Considere a seguinte máquina de Turing, em que Q ...

Um dos modelos mais utilizados para descrever algoritmos de maneira formal é a máquina de Turing. Considere a seguinte máquina de Turing, em que Q correspondente ao conjunto de estados (q0 é o estado inicial, e qP é o estado de parada) e £ indica os símbolos que a fita pode conter (B é o símbolo de espaço em branco):

Q = { q0, q1, q2, q3, qP }

£ = { 0, 1, X, Y, B}

A função de transição é dada pela seguinte tabela de regras:

 |  0  |  1  |  X  |  Y  |  B  |

q0|(q1,X,D)|    |    |(q3,Y,D)|    |

q1|(q1,0,D)|(q2,Y,E)|    |(q1,Y,D)|    |

q2|(q2,0,E)|    |(q0,X,D)|(q2,Y,E)|    |

q3|             |(q3,Y,D)|(qP,B,P)| 

Assinale a alternativa correta a respeito do funcionamento da máquina acima considerando a entrada 0011B.

A. 

A máquina de Turing vai parar considerando a entrada informada, e os símbolos que estarão na fita serão XXYYB.

B. 

Uma vez que a máquina sai do estado q0, ela não retorna a esse mesmo estado durante o processamento de todos os símbolos da entrada.

C. 

Considerando uma entrada com símbolos invertidos, ou seja, 1100B, a máquina executará a mesma quantidade de passos que a entrada original.

D. 

Durante o processamento da entrada informada, a máquina não passa por todos os estados possíveis.

E. 

Para a entrada informada, a máquina entra em um laço infinito alternando entre dois estados sucessivamente.