¿Qué es una Máquina de Turing? (ii)


En el artículo anterior hablamos de problemas matemáticos y algoritmos, haciendo uso de una definición algo compleja, pero que nos sirvió para introducir estos conceptos fundamentales a la hora de comprender qué es una Máquina de Turing. Hoy vamos a dar un paso más y hablaremos de modelos matemáticos, autómatas y, por último, de Máquinas de Turing.

“Una Máquina de Turing es un modelo matemático
“Modelo matemático” es una expresión de esas que se utilizan con cierta frecuencia pero que pocas veces nos paramos a pensar qué significa. Y aunque parezca algo complicado, en realidad se trata de un concepto bastante sencillo.

Un modelo matemático es un conjunto de reglas que “encajan” en la explicación y resolución de un problema, es decir, que modelizan una situación concreta para poder explicarla y encontrar el modo de resolverla. Más aún, se podría decir que un modelo matemático es un conjuto de reglas capaces de generalizar y resolver un problema matemático concreto y cualquier otro de su misma naturaleza que se pueda plantear.

El ejemplo más simple que se me ocurre es, ante el problema “¿cuántas manzanas tenemos si yo tengo tres y tú tienes dos?”, el modelo matemático a aplicar es el que comprende a los números naturales (1,2,3,4,…) y su suma finita. Así, cuando nos encontremos con otro caso similar, como por ejemplo averiguar cuántos años suman las edades de tres personas, basta con aplicar este modelo para averiguarlo, es decir, sumar la edad de cada uno de ellos. Tan fácil como parece.

Ahora la afirmación una Máquina de Turing es un modelo matemático cobra significado: nos dice que es una forma de resolver cierto tipo de problemas, que además funciona para cualquier problema de la misma naturaleza. Como a estas alturas se podrán imaginar, uno de los problemas que será capaz de resolver la Máquina de Turing es el Problema de la decisión.

“Una máquina de Turing es un autómata”
En matemáticas, un autómata es lo que se conoce como una máquina teórica, es decir, un dispositivo cuyo funcionamiento se estudia sin necesidad de construirlo realmente. En concreto un autómata es una máquina teórica que lee unas instrucciones en forma de símbolos y cambia de estado según éstas.

Vamos a tratar de explicar esto mediante un sencillo ejemplo. Imaginemos que nuestro autómata es un robot que sólo sabe hacer tres cosas: tumbarse, levantarse y decir “he quedado con unas robopilinguis”. Estas tres “cosas” serían los tres estados en los que se puede encontrar nuestro autómata.

Imaginemos también que el robot tiene una abertura por la que podemos introducir una cinta de papel perforada, y un dispositivo que lee si cada tramo concreto de la cinta tiene un agujero o no. Supongamos que el mecanismo del robot funciona de tal forma que cuando la cinta tiene un agujero, el robot se levanta, cuando tiene otro más, el robot habla y cuando no lo tiene, se sienta (esta serie de instrucciones de funcionamiento en función de las instrucciones de entrada forman lo que se denomina función de estado del autómata) Por último, supongamos que el robot está tumbado antes de leer la primera instrucción.

Entonces si introducimos una cinta que conste de dos agujeros y un espacio sin perforar, que representamos por OOX, el robot leerá el primer agujero y se levantará, leerá el segundo y dirá “he quedado con unas robopilinguis”, y al llegar al espacio sin perforar se volverá a tumbar.

Bender Autómata

Si ahora introducimos una cinta con la instrucción OXOOOX, el robot se levantará, se tumbará, se volverá a levantar, dirá dos veces su célebre frase, y acabará tumbado de nuevo.

Esto es básicamente un autómata: un dispositivo que lee (implementa) unas instrucciones (algoritmos), y cambia su estado en función de estas (se sienta, se levanta o dice la frase). Pero para un matemático, que el dispositivo sea un robot que vaya a cuerda o un computador cuántico es completamente indiferente, lo importante es el estudio de qué algoritmos puede implementar, qué simbología y qué gramática se puede utilizar para representar estos algoritmos y cómo hacer que el autómata llegue a un estado determinado partiendo de un estado inicial.

Este ejemplo puede parecer demasiado sencillo, pero háganse a la idea que con los actuales recortes en los presupuestos dedicados a I+D es probable que a lo más que podamos llegar en este país es a construir robots gamberros como este.

Pero, ¿qué es una Máquina de Turing?

Después de esta pequeña introducción en el mundo de la Computación, por fin nos encontramos en disposición de comprender lo que es una Máquina de Turing y cómo funciona.

Si recopilamos lo que hemos visto hasta ahora, ya sabemos lo que es un modelo matemático, un autómata, un problema matemático, un algoritmo y lo que significa implementar, además de que todo esto debe de tener que ver con el Problema de la decisión, porque por algo se habrá mencionado. Así que sólo nos falta meterlo todo en la coctelera y sacar la Máquina de Turing de ella, así que vamos al lío.

Una máquina de Turing es un autómata que consta de una cabeza lectora y una cinta infinita en la que la cabeza puede leer símbolos, borrarlos, escribirlos y moverse a la derecha o a la izquierda. Por supuesto también  consta de una función de estado que determinará los cambios de un estado a otro que se deben producir en función de las instrucciones que reciba.

800px-Turing_Machine

Representación artística de una Máquina de Turing

Éste aparato tan sencillo (y tan parecido a un radiocasete) tiene una propiedad sorprendente, y es que es capaz de implemetar cualquier problema matemático que se nos ocurra, con la única condición de que éste se pueda expresar por medio de un algoritmo (que recordemos que no es más que estructurar el problema en un número de pasos determinados) Por tanto, podremos escribir una cadena de símbolos que represente el problema de manera que la máquina lo pueda leer y, como además también puede escribir y borrar, cuando vayamos de un paso a otro del algoritmo podrá recordar el paso en el que se encuentra en cada momento para así poder dar el siguiente en la dirección correcta.

Si nos fijamos bien, es sencillo encontrar una analogía entre una Máquina de Turing y un computador moderno. En un computador, tenemos un dispositivo de lectura y borrado que interpreta los datos grabados en un soporte (hardware) sobre el que puede además borrar, escribir y moverse. Además, este dispositivo dispone de un código (software) que, según sean las instrucciones de entrada, proporciona una salida determinada en forma de imagen en una pantalla, cálculo matemático, sonido, etc.  La única diferencia esencial es que el soporte de información no es infinito, pero eso en la práctica no es un gran problema porque en la mayoría de los casos nuestras necesidades de computación son finitas.

Por tanto, podemos identificar el hardware de un computador con la cabeza lectora y la cinta, mientras que el software serían las instrucciones de la cinta y la función de estado de la Máquina de Turing.

Ahora sí es fácil ver las implicaciones que el estudio teórico de la Máquina de Turing tiene en el avance de la Informática, pues nos permite, entre otras cosas, comprender los límites de lo que podemos esperar que haga una computadora y lo que no.

La Máquina de Turing y el Problema de la decisión

Lo más curioso de todo esto es que, en realidad, cuando Alan Turing descubrió su máquina no lo hizo buscando la forma de inventar un ordenador personal (al menos no era su principal motivación), sino tratando de resolver el Problema de la decisión.

Alan Turing probó que cualquier método de implemetar un problema se puede siempre simplificar a una Máquina de Turing, es decir, que su máquina era algo así como “la madre de todos los métodos”. Por otro lado, también probó que no se puede construir una Máquina de Turing capaz de determinar si un problema se va a poder resolver o no y, por tanto, quedó demostrado que no hay ningún sistema para decidir si un problema matemático tiene solución o no, ya que si lo hubiera, nos encontraríamos con la paradoja de que el sistema se podría reducir a una Máquina de Turing que sabemos a ciencia cierta que no existe.

En definitiva, lo más interesante de la Máquina de Turing desde el punto de vista de un matemático es que nos señala la existencia de una limitación en el universo de las matemáticas: la imposibilidad de saber, a priori,  si un problema matemático va a poder ser resuelto o no. Así, la próxima vez que su jefe le exija una respuesta antes de ponerse a trabajar en la pregunta, podrá contestarle que, gracias al Problema de la decisión, no sólo no puede dársela aún, sino que debe hacerse a la idea de que a lo mejor ésta no existe.

Para que después digan que las matemáticas puras no tienen aplicaciones en la vida real…

Sevilla, Octubre de 2009

Lo publicó Javier Oribe en  El Máquina de Turing.

About these ads

22 respuestas

  1. Santiago Pereyra |Responder

    Muy claro y gracioso! Felicitaciones!

  2. hola excelente tendran algun codigo en c++ que lleve la maquina de turing

  3. hola excelente tendran algun codigo en c++ que lleve la maquina de turing….plis ayudenme espero lo mas pronto su repusta…

    1. Lo siento, Floridelma, pero no soy programador y no conozco el c++. Espero que alguien pueda ayudarte.

      Gracias por tu comentario.

      Un saludo.

  4. Mariela Castellanos |Responder

    muchisimas gracias por fin encontré algo que explicara la maquina de Turing tan bien, todos losotros lo explicaban en otro idioma para mi

  5. Genial!. Muy bien escrito, y entendible para los que no gozamos del estudio complejo de las matematicas.

  6. para comenzar ante todo gracias me gusto quisiera que complemente con mas ejemplos por favor

    1. Gracias por su comentario, aunque lamentándolo mucho en estos momentos tengo el blog parado por razones personales. Espero poder retomar la actividad en un futuro próximo y contestarle adecuadamente.

      Un saludo,

  7. Gabriel Guerrero Arellano |Responder

    muchas gracias amigo por la explicacion tan bacana que nos has publicado me gusto mucho tu manera de explicar ya que antes de entrar aqui lei y mire videos sobre la maquina de turing y no comprendia un carajo muchas gracias una pregunta amigo me podrias decir si hay software sencillo que sea una aplicacion de el concepto de maquina de turing esque es un trabajo para la universidad y no se como podria ser ??

  8. Alberto Moctezuma |Responder

    Amigo, muy buena explicación e introducción de una forma divertida a los conceptos básicos que forman parte esencial de la Teoría de la Computación. Te faltó profundizar un poco sobre el tema de la Máquina de Turing. Pero está demasiado interesante tu artículo.

  9. MUY BUENO!!….HE DECIDIDO NO ROMPERME LA CABEZA CON LA MATEMATICAS !!

  10. la mejor explicacion de la maquina de turing:)

  11. que buena explicación, felicidades y gracias por tomarte el tiempo a explicarlo

  12. el ejemplo de autómata me ayudó muchisimo, gracias por explicar de esta manera lo que es una maquina de turing ;D

  13. Me admira tu capacidad didáctica, paso por paso como debe ser ja. Cosa que reconocemos los que nos dedicamos a la filosofia analítica. Saludos.

  14. José Ribagorda L. |Responder

    Gracias Javier, estoy empezando con la segunda parte del temario de Informática II de matemáticas, en la UNED y tu explicación me da una idea para poder empezar. De nuevo, gracias.

  15. bastante entendible, tengo que hacer la materia de automatas programables y solo mencionan la maquina de turing, pero no dicen lo que es, asi que con esto me queda claro lo que es un automata y lo que es la maquina de turing, gracias amigo y buen aporte.

  16. Muy entendible para novatos como yo , gracias por tomar tu tiempo y redactar este articulo. Saludos desde Mexico.

  17. Maravilloso

  18. Tu si que eres una máquina, macho.

  19. La mejor explicación que e visto, Gracias!!!!

Si tiene algo que decir, éste es el momento

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Cuentos Cuánticos

Un sitio donde los cuentos de ciencia están contados y no contados al mismo tiempo

J.M.Hernández

Página personal

El escéptico de Jalisco

"Usted tiene perfecto derecho a elegir entre conocer las matemáticas o no, pero debe ser consciente de que, en caso de no conocerlas, podrá ser manipulado más fácilmente." John A. Paulos

Los Matemáticos no son gente seria

"Usted tiene perfecto derecho a elegir entre conocer las matemáticas o no, pero debe ser consciente de que, en caso de no conocerlas, podrá ser manipulado más fácilmente." John A. Paulos

Francis (th)E mule Science's News

La Ciencia de la Mula Francis. Relatos breves sobre Ciencia, Tecnología y sobre la Vida Misma

El mundo de Rafalillo

"Usted tiene perfecto derecho a elegir entre conocer las matemáticas o no, pero debe ser consciente de que, en caso de no conocerlas, podrá ser manipulado más fácilmente." John A. Paulos

"Usted tiene perfecto derecho a elegir entre conocer las matemáticas o no, pero debe ser consciente de que, en caso de no conocerlas, podrá ser manipulado más fácilmente." John A. Paulos

Hablando de Ciencia

La Ciencia al Alcance de tu mano

Tito Eliatron Dixit

"Usted tiene perfecto derecho a elegir entre conocer las matemáticas o no, pero debe ser consciente de que, en caso de no conocerlas, podrá ser manipulado más fácilmente." John A. Paulos

Gaussianos

Porque todo tiende a infinito...

La Ciencia y sus Demonios

La primera gran virtud del hombre fue la duda y el primer gran defecto la fe (Carl Sagan)

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

Únete a otros 588 seguidores

%d personas les gusta esto: