BorrowBits
Portada » Blog » Computación » Inteligencia Artificial » Definición de máquina de Turing y ejemplos

Definición de máquina de Turing y ejemplos

Alan Turing ¿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.

Cinta de máquina de Turing con lector en el primer 0.
Cinta de máquina de Turing

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!

13 comentarios

  • me gustaria otros ejemplos mas sencillos sobre esta maquina, ya que recien estamos iniciando la materia y aun no logro comprenderlo

  • No pongas símbolos sin explicación! Que significa el # cuando va al final o va en otro sitio?

    • El # lo uso como símbolo de control de la cinta para saber cuando termina la cadena.

      Para hacer funcionar el simulador solo tienes que pegar el código en el simulador y poner la cadena de «Estado inicial de la cinta» en la parte de la derecha donde pone «Initial input».

      Un saludo.

    • Uso la sintaxis propia del simulador, en la parte de abajo de la página del simulador la tienes especificada.

      Syntax:
      Each line should contain one tuple of the form ‘ ‘.
      You can use any number or word for and , eg. 10, a, state1. State labels are case-sensitive.
      You can use any character for and , or ‘_’ to represent blank (space). Symbols are case-sensitive.
      should be ‘l’, ‘r’ or ‘*’, denoting ‘move left’, ‘move right’ or ‘do not move’, respectively.
      Anything after a ‘;’ is a comment and is ignored.
      The machine halts when it reaches any state starting with ‘halt’, eg. halt, halt-accept.

    • En la parte de abajo del artículo tienes una amplia explicación del ejemplo y de cada transición individualmente.

      Un saludo.

Darío L.M.

Suscríbete

¡Sácale el máximo partido a BorrowBits!

Apúntate para seguir recibir por email las nuevas publicaciones, noticias sobre Blockchain pre-filtradas y material exclusivo para suscriptores. De momento es gratis:

{subscription_form_1}

Categorías

Bits del pasado

Sitio patrocinado por:

JitKey rentabilización apartamentos turísticos

JITKey.- Startup enfocada en la gestión de alojamientos turísticos.