CALENDARIO ACADEMICO

”Máquina de Turing”

Curso:

Compiladores Y Lenguajes De Programación

Alumna:

Quispe Navarro, Cesarina Del Rosario

Profesor:

Francia Espinoza, Máximo Gustavo

LIMA – PERU

2014

INDICE

1 Marco Teórico 3

2 Análisis 3

3 Aplicación 4

4 Bibliografía 6

1 Marco Teórico

Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de datos. En cada instante la máquina puede leer un solo dato de la secuencia (generalmente un carácter) y realiza ciertas acciones en base a una tabla que tiene en cuenta su "estado" actual (interno) y el último dato leído. Entre las acciones está la posibilidad de escribir nuevos datos en la secuencia; recorrer la secuencia en ambos sentidos y cambiar de "estado" dentro de un conjunto finito de estados posibles.

2 Análisis

En realidad se dice que la máquina de Turing es más un modelo matemática que un dispositivo físico o mecánico. El hecho que se le denomine "máquina" se debe a que su funcionamiento puede ser descrito en términos de operaciones individuales muy sencillas que sugieren una implementación muy simple.

3 Aplicación

Diseñar una Máquina de Turing que calcule el complemento a 1 de un número binario. (Es decir, que sustituya los 0’s por 1’s y los 1’s por 0’s).

 Solución:

• Algoritmo: Recorrer la cinta de izquierda a derecha, sustituyendo 1’s por 0’s y viceversa.

• Definición de la MT :Necesitamos implementar una Máquina de Turing que se comporte como transductor, porque genera una salida en la cinta.

Tendremos un solo estado, que será el inicial, q0, sobre el que se realizan todas las transiciones

MT1= ({0,1},{0,1,},,{q0},q0,f,{Φ}), donde f:

Si además se exige que el transductor termine en un estado final y pare, si la entrada es correcta, es decir, una simple secuencia de ceros y unos, la solución sería:

MT1.2=({0,1},{0,1,},,{q0,q1},q0,f,{q1}), donde f:

Si además del estado final se exige que la cabeza de la pila termine al inicio de la palabra (para que se pueda ver el contenido de la cinta

...