Máquina de Turing, la cinta teórica


La máquina de Turing es un dispositivo puramente teórico, que se utiliza para deducir si un problema es informatizable o no.

En este artículo vamos a echar una mirada al lado teórico de los ordenadores: al campo que se denomina “ciencia de la computación”. Tal ciencia es a la informática lo que las matemáticas a la ingeniería, es decir, un campo que se caracteriza por ser extremadamente teórico pero del cual derivan las ideas prácticas.

La máquina Turing, por ejemplo, es una idea puramente teórica que desarrolló Alan Turing como ayuda para estudiar los algoritmos y la posibilidad de informatización. Se trata en realidad del “mínimo ordenador posible”, de modo que si se puede demostrar que un problema determinado no se puede resolver utilizando una máquina de Turing, entonces se puede afirmar que dicho problema no es “informatizable”. Turing pensó que un ordenador mínimo de este tipo necesitaría tres configuraciones: un almacenamiento externo para grabar y almacenar la información de entrada y de salida; un medio para leer dicho almacenamiento y para escribir en él, y en tercer lugar una unidad de control que permitiese determinar las acciones a emprender.

Por definición, una máquina de Turing posee, entonces, una cinta (si le sirve de ayuda, imagínesela como una cinta magnética) de longitud infinita (es decir: sea cual fuere la cantidad de cinta necesaria para solucionar un problema, siempre habrá la suficiente). La cinta está dividida en cuadrados, que o bien estarán en blanco o contendrán un símbolo. A lo largo de la cinta se mueve una “cabeza”, que puede leer o escribir símbolos en los cuadrados y que recibe sus instrucciones desde una unidad de control que le proporciona una doble indicación: cuáles son los símbolos que debe escribir y en qué dirección se ha de mover a continuación.

La unidad de control posee un programa de ejecución, y en este sentido se puede decir que cada máquina Turing se “fabrica” específicamente para realizar una aplicación, ya que en la especificación no existen medios para cargar o alterar un programa. Hemos entrecomillado la palabra fabricar porque las únicas máquinas de Turing que se han construido físicamente lo fueron con fines puramente educativos. Sin embargo, escribir un programa en BASIC que imite el funcionamiento de una máquina Turing en un ordenador personal es un ejercicio relativamente sencillo.

El programa de control de una máquina Turing consta de un conjunto de “quíntuplos”, o sentencias que contienen cinco elementos. Qué quíntuplo se ejecuta en cada etapa depende de dos factores: el símbolo que contenga el cuadrado que esté debajo de la cabeza de la cinta, y el “estado” o “condición de la máquina. Dicho estado es una cualidad estrictamente arbitraria: podemos especificar que la máquina se ponga en marcha en el estado “Sa” y que cuando llegue al estado especial “H” entonces se detenga, dándose por acabado el cálculo. Entretanto, el estado cambiará muchas veces de acuerdo con las instrucciones de los “quíntuplos”. El estado tan sólo refleja lo que está sucediendo hasta el momento en el cálculo y ayuda a seleccionar qué “quíntuplo” se ejecutará a continuación (nuevamente, si le sirve de ayuda, imagíneselo como una variable de bandera en un programa BASIC).

Los cinco elementos de que consta cada quíntuplo son:
1) El estado en curso de la máquina;
2) El símbolo del cuadrado de la cinta que se halle debajo de la cabeza;
3) El símbolo a escribir en ese cuadrado, que será el mismo que en 2) si no se requiere ninguna modificación de los datos;
4) El estado en que la máquina ha de entrar ahora;
5) La dirección en la que se debe mover la cabeza de cinta (izquierda o derecha)

El “quíntuplo” (Sa,5,3,Sb,D), por ejemplo, se ejecutará siempre que la máquina esté en estado Sa y que la cabeza de la cinta lea un 5. El 5 se reemplazará luego por un 3, la máquina pasará del estado Sa al Sb y la cabeza de la cinta se desplazará un cuadrado hacia la derecha.

Diseñar una máquina de Turing teórica para efectuar una tarea determinada implica especificar el formato en el cual se presentarán a la máquina sus datos de entrada en cinta, el formato de los datos de salida en cinta cuando se termine el cálculo (es decir, con la máquina en estado H), y el grupo de quíntuplos requeridos para ejecutar el algoritmo.

En el ejemplo siguiente hemos diseñado una máquina de Turing para realizar la función AND. Estableceremos los dos bits de entrada (cada uno con un 1 o un 0) en cuadros adyacentes, seguidos de un signo de interrogación, que se ha de reemplazar por la respuesta (nuevamente, un 1 o un 0, dependiendo de la dos entradas). Por convenio, hemos agregado un asterisco a los dos extremo del área de datos, y pondremos la máquina en funcionamiento en el estado Sa encima del asterisco situado más a la izquierda, acabando sobre el situado más a la derecha.

Se necesita un total de diez quíntuplos para especificar esta máquina, si bien, como se podrá ver en el ejemplo con que trabajamos (1 AND 1 = 1) se utilizan cinco para cualquier ejecución. Si usted prueba la misma máquina para, supongamos, 0 AND 1, descubrirá que de los diez quíntuplos se selecciona un grupo de quíntuplos diferentes.

(1)
La máquina Turing
Este ejemplo muestra la construcción de una máquina Turing para realizar la función AND. Los dos bits de entrada están establecidos en cuadros adyacentes, seguidos por un signo de interrogación que será reemplazado por el resultado. Flanquean el área de datos dos asteriscos para que actúen como bordes. Los diez quíntuplos reseñados abajo especifican la operación de esta máquina, aunque para cualquier ejemplo con el cual se trabaje (en este caso 1 AND 1), sólo se utilizan cinco de los diez.

(2)
La máquina comienza a funcionar en el estado Sa con la cabeza posicionada sobre el asterisco situado a la izquierda. El único efecto de este quíntuplo es mover la cinta hacia la derecha.

(3)
Si el siguiente cuadrado contiene un 1 entonces se selecciona este quíntuplo y la máquina pasa a estado Sc, instruyéndola para que se mueva hacia la derecha. Si se ha leído un 0, el resultado es Sb.

(4)
Con la máquina en estado Sc, un 1 es el segundo cuadrado da Se. En otro caso, la máquina pasaría a Sd.

(5)
Ante signo de interrogación, según el estado de la máquina, Se o Sd, se escribirá en su lugar un 1 o un 0. En cualquier caso, la máquina se coloca en estado Sf.

(6)
La máquina pasa a estado de detención (H) con el segundo asterisco. Se puede verificar sobre el papel el funcionamiento para 1 AND 0, 0 AND 1 y 0 AND 0.

(Fuente: Reproducción del artículo “Términos clave – La Cinta Teórica”, Mi Computer, fascículo 22)

About these ads
2 comentarios
    • afx dijo:

      Muy buena tu versión Basic para Spectrum de la máquina de Turing. Sería un buen ejercicio portarla a SuperBASIC (como diversión).

Deja un comentario

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

Seguir

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