Turing

Capítulo 9 – Máquinas de Turing
Exercícios

|q1 |1 |R |q1 | |
| | | | |Vá à Direita, até o fim da primeira coordenada |
|q1 |0 |R |q2 | |
|q2 |1 |R |q2 | |
| | | | |Vá à Direita, até o fim da segunda coordenada |
|q2 |0 |L |q3 | |
|q3 |1 |0 |q4 | |
| | | | |Volte à Esquerda, apagando a segunda coordenada |
| | | | | |
|q3 |0 |L |q5 | |
|q4 |0 |L |q3 | |
|q5 |1 |0 |q5 |Apague o último dígito da primeira coordenada |
|q5 |0 |L |q6 | |
| | | | |Volte à Esquerda, até o início da primeira coordenada |
|q6 |1 |L |q6 | |
|q6 |0 |R |q7 | |

2. a. Defina uma TM que calcule a função projeção sobre a primeira coordenada, P (m, n) = m .
Podemos resumir um algoritmo que calcule a projeção sobre a primeira coordenada da seguinte forma:

1) Vá à Direita, até o fim da primeira coordenada;
2) Vá à Direita, até o fim da segunda coordenada;
3) Volte à Esquerda, apagando a segunda coordenada;
4) Apague último dígito da primeira coordenada;
5) Volte à Esquerda, até o início da primeira