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!

Previous Line hace buena su campaña televisiva y ya cuenta con 10 millones de usuarios
Next Utilizando cookies para guardar el estado de un árbol JSTree

About author

Dario LM
Dario LM 36 posts

Estudiante de Ingeniería Informática buscando el Nirvana. Su curiosidad lo guía a través de la animación 3D, la programación o el diseño web entre otros temas. Escritor (blogger), músico y seriéfilo.

You might also like

Tutorial 4 Comentarios

[Administra tu Servidor] ¿Cómo hacer copias periódicas en Linux? Utiliza la shell.

Tanto si eres el administrador de un servidor con Linux o simplemente tienes instalada una de sus distribuciones en tu portátil personal, seguro que te ves en la necesidad de

Tecnologia & Ciencia 0 Comentarios

Cómo evitar ser un freelance esclavo (II)

Retomamos aquel artículo para ayudar a los neófitos y cándidos del freelancing TIC. Una de las razas de autónomo más puteadas y sufridas que pueden existir en nuestros días. Hace

Generales 1Comments

¿Se queda Tumblr con tus derechos de autor?

Hace meses que utilizo Tumblr como herramienta de microblogging para publicar algunos textos – ejercicios literarios, poemas y reflexiones personales sin importancia –  y el otro día me asaltó una duda:

12 Comentarios

  1. Anónimo
    abril 07, 19:01 Reply

    Que significa cada columna de la tabla de transiciones?

    • Dario LM
      abril 07, 19:28 Reply

      En el orden dado: “current state | current symbol | new symbol | direction | new state”

  2. Anónimo
    abril 07, 18:52 Reply

    Debes explicar la tablita de transiciones, no la entiendo, no soy turing!

    • Dario LM
      abril 07, 18:56 Reply

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

      Un saludo.

  3. Anónimo
    abril 07, 18:43 Reply

    Que lenguajes usas para el simulador?

    • Dario LM
      abril 07, 18:47 Reply

      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.

  4. James H H Rodríguez
    abril 07, 18:40 Reply

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

    • Dario LM
      abril 07, 18:50 Reply

      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.

  5. ruben
    marzo 28, 15:05 Reply

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

    • Dario LM
      noviembre 27, 17:15 Reply

      Me alegro de que te haya sido de utilidad. Un saludo.

Deja un comentario