Definición de máquina de Turing y ejemplos

¿Qué es una máquina de Turing (MT)? ¿Cual es su cometido?

En esta entrada nos introduciremos en el ámbito de la computación, intentando entender una pequeña parte de la misma de mano de uno de los mejores científicos de la computación de la historia.

Definición.

Una MT es una forma de simular una máquina computacional compuesta por estados y transiciones que seguir. La MT está formada por una cinta, un conjunto de estados, un alfabeto de entrada, un alfabeto para la cinta, una función de transición, un estado inicial y unos estados finales. La cinta es leida con un único cabezal, y en la misma se puede leer o escribir simbolos de los dados en el alfabeto para la cinta. Los movimientos permitidos en la cinta son; izquierda, derecha o mantenerse en el sitio.

El funcionamiento es muy sencillo. Dada una palabra de entrada, formada por simbolos del alfabeto de entrada, el objetivo de la MT es responder entre dos opciones. «SI» si la palabra es aceptada, y «NO» en caso contrario. Para ello, la MT hace uso de las transiciones (o reglas) definidas, tomando el estado actual y el simbolo que lea en la cinta. Si tras N pasos (longitud de la palabra) el estado actual en el que nos encontramos pertenece al conjunto de los estados finales, la palabra es aceptada. En caso contrario, diremos que la palabra no es aceptada por la MT.

Objetivo.

Como ya hemos visto, una MT puede ser generada de forma simple para problemas sencillos. Sin embargo, la potencia de las MT es tal que puede simular cualquier algoritmo que seamos capaces de imaginar. Su uso tiene un sinfín de utilidades tanto en el ámbito de la computación, como en el análisis de complejidad algorítmica, o en el mismo campo matemático.

Es de gran utilidad para comprender los límites de algunos problemas matemáticos. Uno de los ejemplos más conocidos donde una MT muestra su capacidad es el problema de la parada  (Consultar: Entscheidungsproblem) donde, gracias al uso de la MT se concluyó que es imposible obtener un algoritmo con el cual pueda decidirse si un algoritmo dado parará para una entrada determinada.

Como dato anecdótico me gustaría citar el Teorema de Fermat el cual demuestra que para el problema de si termina o no el algoritmo:

x^n + y^n = z^n    Siendo x,y,z números enteros positivos.

No existe solución para n>2. Este teorema fué demostrado en el año 1995, pero formulado en el año 1637. ¡Se han necesitado casi 360 años para demostrar si un problema concreto termina o no!

Y nosotros pretendemos crear un algoritmo que para cualquier otro dado nos diga si para o no…

Ejemplos de funcionamiento.

Aquí os dejo un simulador muy sencillo, acompañado de algunos ejemplos diseñados personalmente, que os puede ayudar a comprender el funcionamiento de las máquinas de Turing. Podéis pegar los ejemplos que os dejo abajo directamente en el simulador para ver como funcionan paso a paso.

Simulador.

Primer ejemplo

;Una cadena de X seguida de una cadena de Y. Ambas de la misma longitud.

;{X^n Y^n , n>0}

;Estado inicial de la cinta: 000111#

;Transiciones:
0 0 X r 1
1 0 0 r 1
1 Y Y r 1
2 X X r 0
3 Y Y r 3
0 Y Y r 3
1 1 Y l 2
2 0 0 l 2
2 Y Y l 2
3 # # r 4
4 * * r halt

Segundo ejemplo

Para dos números naturales n,m € N se calcula f(n,m) que es igual a n-m si n>m o igual a 0 si n<m. En el caso de que n>m en la cinta deben quedar tantos 0 como sea el resultado de n-m. En caso contrario la cinta debe quedar vacia.

;Estado inicial de la cinta: El que se desee, solo que la entrada debe acabar en #.

;Transiciones:

0 0 # r 1
0 1 # r 5
1 0 0 r 1
1 1 1 r 2
2 0 1 l 3
2 1 1 r 2
2 # # l 4
3 0 0 l 3
3 1 1 l 3
3 # # r 0
4 0 0 l 4
4 1 # l 4
4 # 0 r 6
5 0 # r 5
5 1 # r 5
5 # # r 6
6 * * r halt

Tercer ejemplo

He tratado de comentar con más detalle este último ejemplo a favor de que se entienda con más claridad.

Aceptar las cadenas con el mismo número de 0 que de 1. Sin importar su orden.

En el estado 0 nos ocupados de buscar ceros.

0 0 # * 1 ;Si encuentra un 0 ponerlo en blanco y pasar al estado 1.
0 1 1 l 0 ; Si encontramos un 1 o un #, seguimos buscamos hacia la izquierda.
0 # # l 0
0 _ _ r 3 ; En caso de salirnos de nuestra cadena acudimos al estado 3.

En el estado 1 nos ocupamos de buscar unos.

1 1 # * 0 ;Si encuentra un 1 ponerlo en blanco y pasar al estado 0.
1 0 0 r 1 ;Si encontramos un 0 o un #, seguimos buscando hacia la derecha.
1 # # r 1
1 _ _ l 4 ;En caso de salirnos de nuestra cadena acudimos al estado 4.

El estado 3 es similar al 0, su objetivo es buscar ceros. Pero, ya que no sabemos el orden a priori en el que se han colocado los unos y los ceros debemos tener la posibilidad de buscar en sendas direcciones. De eso se ocupa el estado 3, busca hacia la derecha, dado que el estado 0 buscaba hacia la izquierda.

3 # # r 3 ;Si encontramos # o 1 seguimos buscando ceros hacia la derecha.
3 0 # * 1
3 1 1 r 3

El estado 4 es similar al 1, su objetivo es buscar unos. Pero, ya que no sabemos el orden a priori en el que se han colocado los unos y los ceros debemos tener la posibilidad de buscar en sendas direcciones. De eso se ocupa el estado 4, busca hacia la izquierda, dado que el estado 1 buscaba hacia la derecha.

4 # # l 4
4 0 0 l 4
4 1 # * 0

Una vez hemos recorrido la cadena en ambas direcciones damos el programa por finalizado.

3 _ _ * halt
4 _ e * halt

Espero que os sea de ayuda, cualquier duda o feedback podéis dejarlo en los comentarios.

¡Un saludo!