Los límites de la computabilidad (I) ¿Qué es una máquina de Turing?

En 1947 el famoso matemático inglés Alan Turing pronunció su polémica conferencia «¿Puede pensar una máquina?«. Frente al dualismo imperante, Turing defendió que era posible que una máquina pudiese llegar a hacer exactamente lo mismo que hace un hombre, incluida la función de pensar. Resulta curioso que algo tan normalizado hoy en día como el hecho de que las máquinas realicen mucho mejor que nosotros ciertas actividades que calificaríamos como inteligentes, hace tan sólo cincuenta años sonara a despropósito irrelevante.

Unos años antes, Turing había publicado un artículo titulado On computable Numbers, with an Application to the Entscheidungsproblem en donde desarrolló la teoría de las máquinas que llevan su nombre y que supondrán un hito para la historia de la informática al suponer el fundamento teórico de los computadores digitales modernos. Bien, ¿y qué es una máquina de Turing?

Antes de nada nos tenemos que acercar al concepto de algoritmo. La palabra procede del matemático árabe Al-Khowarizm, quien escribió en el 825 un tratado de aritmética muy conocido durante la Edad Media. No obstante, antes de él ya se conocían ejemplos de algoritmos. Uno de ellos es el popular algoritmo de Euclides que constituye un procedimiento para encontrar el máximo común divisor de dos números. Se trata de dividir entre sí ambos,  formar una nueva pareja con el divisor y el resto y volverlos a dividir. Así, sucesivamente hasta que se consiga un resto cero. El divisor que quede entonces será el máximo común divisor de ambos números.  El algoritmo de Euclides supone una regla, unas instrucciones para conseguir un resultado, que se obtendrá siempre sean cuales sean ambos números. Si son muy altos, el procedimiento tendrá más pasos, nada más. De este modo, todas las operaciones aritméticas son algoritmos (sumar, multiplicar, raíces cuadradas, elevar a una potencia…). Todas consisten en realizar un pequeño número de instrucciones que se repetirán cuantas veces sean necesarias para llegar a una conclusión. Entonces, un algoritmo se podría definir como un conjunto de instrucciones para realizar una tarea con las siguientes características:

1) Precisión: un algoritmo ha de estar definido con suficiente precisión para no albergar dudas sobre qué paso seguir.

2) Simplicidad: las reglas son sencillas. Cuando se trata de algoritmo, en apariencia sencillo, se puede descomponer en algoritmos más elementales. El de Euclides, por ejemplo, se puede descomponer en divisiones y agrupamientos divisor-resto.

3) Finitud: el número de reglas ha de ser finito mientras que el número de operaciones que pueden realizarse debe ser infinito.

4) Carácter mecánico: es un procedimiento mecánico, automático. Un algoritmo no requiere ninguna agudeza mental ni ingenio creativo, es algo que cualquier persona puede hacer con sólo tener la capacidad de seguir y obedecer reglas.

5) Procedimiento general: los algortimos están orientados a la solución de problemas, pero no tendría mucho sentido diseñar uno para solucionar un único problema particular (imaginemos crear un algorítmo para multiplicar 45 por 678 y nada más). Está en la naturaleza del algoritmo ser un mecanismo lo más sencillo y económico posible para realizar correctamente muchas tareas. Sin embargo, como la dificultad para realizar muchas tareas diferentes por un mismo algoritmo es mucha, se los suele utilizar para resolver un tipo de problemas. Así, el algoritmo de Euclides soluciona todos los casos posibles del problema de encontrar el máximo común divisor.

En 1936 el matemático norteamericano Alonzo Church (1903-1995) va a plantear la primera definición matemática de algoritmo. Su tesis principal es que la clase de las funciones calculables por un algoritmo es idéntica a la clase de las funciones recursivas. Church demostró (bueno, no era del todo una demostración…) la imposibilidad de encontrar un algoritmo para la teoría elemental de la aritmética y, en consecuencia, para la lógica de predicados de primer orden: tanto la aritmética como la lógica de primer orden resultaban indecidibles. El mismo resultado fue obtenido al mismo tiempo por Turing con sus máquinas, utilizando el concepto de función computable: una función tal para la que existe una máquina de Turing que proporciona el valor de la función. Con estos conceptos Church, Turing y otros (Post, Markov) habían llegado a la misma conclusión que Kurt Gödel unos años antes: el programa de Hilbert había fracasado.

Bien, pero vayamos a lo que nos interesaba: ¿Qué es entonces una máquina de Turing? Bien, Turing quería abordar de una forma rigurosa la noción de algoritmo o procedimiento mecánico. Así, imaginó cómo podría formalizarse el concepto de una máquina descomponiendo su modo de operar en sus pasos más elementales. Así que una máquina de Turing (MT) no es algo físico, no es una máquina de verdad (por mucho que los actuales ordenadores se basen en ella), sino un constructo, un experimento mental. ¿Cuáles son las partes elementales de la MT?:

1) Unidad de control: el el conjunto finito de todos los posibles estados internos. Una MT puede asumir diferentes estados dependiendo de las circunstancias que tiene lugar en el estado de computación.

2) Cinta: se trata de una cinta de longitud intinita tanto por la izquierda como por la derecha, dividida en celdillas de forma que en cada celdilla sólo cabe un único símbolo. En la cinta aparecerán los caracteres de un alfabeto previamente definido agrupados en cadenas. Las cadenas serán siempre finitas a pesar de la infinitud de la cinta. Esa infinitud expresa que en ella podemos escribir tantas cadenas como queramos y de cualquier longitud.

3) Cabeza: la unidad de control está conectada a la cinta mediante la cabeza, cuya función es la de observar en cada momento una sola celdilla escrita con un único símbolo. La cabeza lee, escribe, sustituye y borra un símbolo cada vez, además de hacer que la cinta se desplace una celdilla a la izquierda o a la derecha, de acuerdo con las instrucciones correspondientes.

4) Instrucciones: una MT se dirige desde un número finito de instrucciones numeradas. Una instrucción está formada por un cuadruplete de símbolos, dividido en dos partes. La primera describe una situación condicional (Si pasa esto…) y la segunda el cambio a operar (…entonces lo otro). El primer símbolo y el último siempre son estados (S0, S1, S2,…, Sn), siendo los símbolos intermedios las acciones dadas y a realizar respectivamente. Por ejemplo, si nos encontramos la instrucción «1. S0, a, b, S1», lo que hay que leer es: «Si la cabeza lee una a, entonces escribe una b y pasa al estado S1″.

Teniendo todos los componentes veamos algunos ejemplos. Vamos a construir una MT capaz de traducir de una lengua dada a otra (letra por letra). La máquina va a disponer de dos vocabularios:

A1={a,b,c} y A2={x,y,z}

Queremos que cuando la MT vea una a, la traduzca a una x, una b a una y y una c a una z. Las instrucciones serían las siguientes:

1. S0, a, x, S1

2. S1, x, I, S0

3. S0, b, y, S1

4. S1, y, I, S0

5. S0, c, z, S1

6. S1, z, I, S0

El estado inicial de la MT siempre es el So, siendo los restantes S1, S2, S3,…, Sn. Cuando la máquina se encuentra en la cinta con una a la traduce por una x y se va al estado S1. En S1, la MT lee x, avanza hacia la izquierda (las instrucciones de movimiento son I para la izquierda y D para la derecha. Borrar se escribe #) y vuelve al estado S0. Hay que tener en cuenta que cada estado es un condicional que si no se cumple, la máquina va bajando, estado por estado, hasta encontrar alguno que se cumpla. Por eso si la máquina vuelve a S0 pero en la cinta no hay una  a, irá bajando hasta encontrar un estado que represente lo que hay en la cinta.

Veamos otro ejemplo. Vamos a construir una MT que sea capaz de realizar sumas de dos sumandos utilizando un sistema numérico con base unaria. Es decir, vamos a hacer que nuestra máquina sume palitos. Las entradas que recibirá la MT serán de esta forma: «#///#//#», lo cual significará suma tres más dos, de tal modo que la máquina responderá «#/////#».  El lenguaje será entonces A={/,#} y las instrucciones:

1.S0, /, I, S0

2. S0, #, /, S1

3. S1, /, D, S1

4. S1, #, I, S2

5. S2, /, #, S2

Como vemos la numeración de los estados puede repetirse. Al construir esta MT hemos elaborado un algoritmo para sumar dos sumandos tal que puede sumar potencialmente cualquier cantidad de números que se agrupen de dos en dos. La máquina de Turing es equivalente al concepto de algoritmo, que es de lo que se trataba. Así hay que distinguir lo que se denomina una Máquina Universal de Turing, que es la formulación rigurosa de computación o algoritmo, de la de Máquina de Turing sin más, que es cualquier máquina para realizar una tarea cualquiera.

Cuando yo estaba en la facultad recuerdo haber diseñado una MT que era capaz de codificar y decodificar lenguajes en función de una clave numérica recibida (quería emular tontamente a la Enigma alemana, haciendo una máquina para escribir mensajes cifrados). Como el abecedario tenía demasiadas letras, y la MT trabaja de modo pesado y poco eficiente, sólo lo hice con las tres primeras. El número clave indicaba, emulando al método de cifrado Julio Cesar, las posiciones que había de rotar las letras (si la letra era a y la clave 2, la a se sustituía por la b). El profesor me puso un sobresaliente pero no me devolvió la máquina. Viendo retrospectivamente, ahora no me parece tan difícil de construir como cuando la hice y no entiendo por qué estuve tanto tiempo muy orgulloso por el logro.

Y para acabar y poneos un pequeño reto (es muy, muy fácil): teniendo un lenguaje similar al anterior A={/, #}, ¿sabriáis construir una MT capaz de responder S (Sí) o N (No) al hecho de encontrarse con un número divisible o no por dos?

P. D.: Los de LEGO han construido una MT real. Aquí la tenéis, con todas sus partes y aderezado el vídeo con la música del Equipo A.