| Artículos | 01 ENE 1997

La máquina de Turing

Tags: Histórico
Eloy Anguiano.

El tema de hoy está dedicado a uno de los mayores teóricos de la informática y la computación. A un pionero que, en su corta vida sentó buena parte de las bases teóricas de lo que actualmente se denomina ingeniería informática. Me refiero, como no, a Alan Turing y a uno de sus aportes mas importantes: la máquina de Turing.

Alan Mathison Turing (1912-1954) fue un famoso lógico y matemático inglés, pionero de las teorías de computación y del análisis lógico de los procesos computacionales.

A la corta edad de 25 años publicó un artículo que llevaba por título "On Computable Numbers, with an Application to the Entscheidungsproblem". En este artículo demostraba la existencia de algunos problemas matemáticos que no son resolubles mediante un proceso definido y fijo. Aquí proceso es necesario entenderlo como a la sucesión de hechos que puede ser programados en una máquina de proceso automático (esencialmente un computador). Es más, en este mismo artículo propuso una máquina computadora teórica no limitada (como lo son las reales) en su capacidad de almacenamiento y sin posibilidad de fallo. A esta computadora teórica se la denominó más tarde con el nombre de "Máquina de Turing". Esta máquina es el punto de inicio de cualquier estudio de la teoría de autómatas y base teórica del desarrollo de los primeros computadores hace casi 60 años.

El propio Alan Turing demostró que su maquina era una maquina de computación general, es decir, que era capaz de efectuar todo aquello que pudiese realizar o computar un sistema digital.

Una buena representación de una máquina de Turing es la de una caja que viaja sobre una cinta transportadora. La caja es un dispositivo de entrada y salida, es decir, es capaz de leer lo que hay en una determinada posición de la cinta transportadora y también lo es de cambiar o no lo que hay en esa posición.

Esta caja tiene una serie de estados que determinan qué es lo que hará con lo que hay en la posición de la cinta transportadora en función de lo que ha sucedido anteriormente. Esta serie de estados son, en esencia, el programa que se va a ejecutar.

La cinta transportadora a su vez está formada por una serie de elementos discretos donde hay un 1 o un 0. Esta cinta transportadora es el dato de entrada del programa. A su vez, la propia cinta es el dato de salida una vez que la máquina de Turing se ha parado. La cinta transportadora debe ser infinita o por lo menos preparada para que se le añadan más valores en el caso en el que la máquina de Turing no haya llegado a parar.

Curiosamente, no se puede predecir (salvo casos muy simples o que se ajusten a un algoritmo muy determinado) cuando una máquina de Turing se va a parar o si lo hará.

Otra de las características esenciales de esta máquina es que puede ejecutar absolutamente cualquier algoritmo y finalizar si este algoritmo es finito. Ahora, querido lector le veo preguntándose ¿cómo no se puede predecir si parará o no y al mismo tiempo se puede hacer que ejecute cualquier algoritmo y que termine? Muy sencillo, una maquina de Turing puede crearse con una serie de estados que no correspondan con ningún algoritmo y por tanto no podremos predecir si parará o no. Sin embargo, si construimos una máquina que ejecute un algoritmo finito, sabemos que, salvo error de programación, el programa (la máquina) terminará.

Un ejemplo

Para saber cómo funciona de una forma más clara es aconsejable ver un ejemplo. Definamos primero la máquina de Turing que vamos a utilizar.

Para ello es necesario enunciar todos los estados y sus reglas. En nuestro caso van a ser las siguientes:

Estado 1:

Lee 0

Escribe 1

Traslación izquierda

Pasa a estado 3

Lee 1

Alto

Estado 2:

Lee 0

Escribe 1

Traslación derecha

Pasa a estado 1

Lee 1

Escribe 1

Traslación izquierda

Pasa a estado 3

Estado 3:

Lee 0

Escribe 0

Traslación derecha

Pasa a estado 2

Lee 1

Escribe 0

Traslación derecha

Pasa a estado 3

Esta máquina de Turing es muy sencilla puesto que el número de estados es de sólo 3 y además carece de finalidad específica. Con ésta, lo que se pretende es mostrar de una forma sencilla el funcionamiento de la máquina de Turing.

En la figura adjunta, en la parte (a) vemos el dato original sin la máquina y en la figura (b) puede verse la maquina de Turing en la que se ha elegido como su situación inicial, es decir, sobre un determinado elemento y en el estado 3. Como el dígito es un cero la máquina no cambia el dígito, se desplaza a la derecha una posición y se pone en el estado 2.

En la figura (c) se puede ver el siguiente paso. La máquina está en estado 2 y tiene un 0 luego escribe un 1, se desplaza a la derecha y se pone en el estado 1. En la figura (d) se pueden ver los diez primeros pasos que realiza la máquina que hemos diseñado.

En general, una máquina de Turing creada para ejecutar un algoritmo es mucho más complicada que la aquí presentada pero con un funcionamiento idéntico al descrito.

El lector puede realizar un pequeño divertimiento con la máquina de Turing y es crear una máquina que al menos sume dos bits. Otro de los divertimiento posibles es crear máquinas de Turing generalizadas, con niveles de entrada-salida que no sean binarios o crear un autómata recursivo que vaya tomando como entrada la salida de la ejecución anterior y representar cada ejecución por una línea distinta en la pantalla (y consecutivas).

Esta representación supondría que se asignaría el color blanco al nivel 1 y el negro al nivel 0. Si es un autómata multinivel se pueden utilizar además otros colores.

Si usted lector crea un autómata puede enviármelo a mi dirección electrónica y si es suficientemente interesante o curioso lo publicaré con el nombre de su autor.

Bibliografía

-A.K. Dewdney, "The Turing Omnibus", Computer Science Press, 1989.

-M.L. Minsky, "Computation: Finite and Infinite Machines", 1967.

-Andrew Hodges, "Alan Turing: The Enigma", 1983 (biografía de Turing).

Contenidos recomendados...

Comentar
Para comentar, es necesario iniciar sesión
Se muestran 0 comentarios
X

Uso de cookies

Esta web utiliza cookies técnicas, de personalización y análisis, propias y de terceros, para facilitarle la navegación de forma anónima y analizar estadísticas del uso de la web. Consideramos que si continúa navegando, acepta su uso. Obtener más información