Turing

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1675 palavras )
  • Download(s) : 0
  • Publicado : 9 de maio de 2012
Ler documento completo
Amostra do texto
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çãosobre 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 daprimeira coordenada.
A máquina ao lado efetua estas operações:

|q1 |1 |0 |q2 | |
|q1 |0 |R |q3 |Vá à Direita, apagando n1 |
|q2 |0 |R |q1 | |
|q3 |1 |0 |q4 | ||q3 |0 |R |q5 |Vá à Direita, apagando n2 |
|q4 |0 |R |q3 | |
|. . . |... |... |. . . | |
|q2(i-1)-1 |1 |0 |q2(i-1) | |
|q2(i-1)-1 |0 |R |q2i-1 |Vá à Direita, apagando ni-1|
|q2(i-1) |0 |R |q2(i-1)-1 | |
|q2i-1 |1 |R |q2i-1 | |
|q2i-1 |0 |R |q2i |Pule ni , indo à Direita |
|q2i |1 |0 |q2i+1 | |
|q2i |0 |R |q2i+2 |Vá à Direita, apagandoni+1 |
|q2i+1 |0 |R |q2i | |
|. . . |... |... |. . . | |
|q2k-2 |1 |0 |q2k-1 | |
|q2k-2 |0 |L |q2k |Vá à Direita, apagando nk |
|q2k-1 |0 |R |q2k-2 ||
|q2k |0 |L |q2k |Volte à Esquerda, até o fim de ni |
|q2k |1 |0 |q2k+1 |Apague último dígito de ni |
|q2k+1 |0 |L |q2k+2 | |
|q2k+2 |1 |L |q2k+2 |Volte à Esquerda, até o início de ni |
|q2k+2 |0 |R |q2k+3 |...
tracking img