Máquinas de Turing, primera parte.

Las ideas son entes muy especiales. No puedo dejar de pensar en Platón pensando en la existencia de plano de las ideas, una especie de paraíso en que la mesa existe como una mesa perfecta, la idea de la mesa, el colmo de la mesidad. La idea del cuadrado, del círculo. La abstracción del cuadrado, del círculo y de la mesa.

Cuando abstraemos algo, estamos tomando la idea de ello. De donde lo sacamos y donde lo ponemos, es lo que Platón encontró en el hyperuránion tópon, el lugar más allá del cielo.

Las abstracciones son poderosas, son la manera que tenemos de manipular ideas, de darles vuelta, examinarlas, confrontarlas unas con otras.

Tenemos una necesidad de explicarnos el mundo y encontrar relación entre los hechos de éste de manera que podamos ver lo que va a suceder antes de que suceda y así tener tiempo de prepararnos para ello. Esta necesidad y la habilidad que tenemos para satisfacerla está hardcodeada en nuestros cerebros evolutivamente. Es necesario para nuestra sobrevivencia adelantarnos a los predadores, a las estaciones, y en general a los fenómenos del mundo, de manera que podamos alargar nuestra vida y proteger nuestra descendencia.

En la historia de las abstracciones esta es la razón por la que la mayoría de nuestras abstracciones tienen que ver con comprender el mundo. La mayoría de nuestras ideas: el lobo (la idea del lobo), la luna (la idea de la luna), la cosecha (la idea de la cosecha,) tienen que ver con hechos palpables, necesarios para nuestra sobrevivencia. La ciencia es un refinamiento de nuestra manipulación de las ideas en la búsqueda de las explicaciones de la realidad.

Pero la ciencia se basa en las matemáticas, y en las matemáticas las ideas ya no encuentran equivalencia física. Es un despegue del mundo físico hacia el mundo de las ideas. Todo en la matemática son conceptos y relaciones entre los mismos. Claro que la manera en que construimos estos conceptos viene supeditada a nuestra existencia física de manera que las matemáticas que hemos construido tienen ciertos sesgos que se explican por nuestra biología, como la elección de la base diez para contar (por el número de dedos de nuestra especie), que probablemente serían diferentes si hubiéramos tenido otras historias evolutivas. Aun así, las matemáticas siguen siendo ese campo en el que las ideas son más libres de ataduras físicas.

Otra cuestión con los humanos es que apreciamos la belleza. Tenemos un sentido estético que nos permite apreciar la belleza tanto natural como construida. Este sentimiento hacia la belleza, que no podemos terminar de nombrar o describir nos conecta con la sensación de eternidad.

En las matemáticas, que no son ciencia, ni sabemos bien qué sean, también existe la belleza. Y también existe esta apreciación hacia la belleza. Hay ideas y juegos y relaciones entre ideas que nos arroban, nos catapultan hacia ese sentido de eternidad. Unas frases atrás dije “ni sabemos bien que sean” refiriéndome a las matemáticas. Tal vez es de esos conceptos, como la aleatoriedad, que necesitan periódicamente adiciones a su definición. Así que, aunque no tengo la definición de matemáticas, ni creo que se pueda tener por completo, sí sé que entre las muchas cosas que puede decirse de las matemáticas, una muy importante es entender que las matemáticas son un arte.

Traigo todos esto a colación porque estoy escribiendo esto debido a una ¿obsesión? ¿deslumbramiento? Acerca de una idea, las Máquinas de Turing.

Ahora las llamamos así en honor a Alan Turing, quien las describiera (¿inventara? ¿construyera? Con los conceptos matemáticos nunca sé cuál es el verbo apropiado) por primera vez en 1936.

Turing utilizó esta idea para resolver un problema, y lo hizo de manera brillante. El problema tenía que ver con los límites del cómputo. Pero ahora no vamos a hablar del problema que resolvió, sino del instrumento mental que inventó para resolverlo.

Para apreciar las consecuencias maravillosas de ésta idea, tenemos primero que conocerla íntimamente, que es a lo que me dedicará en este artículo, ya en artículos posteriores tendremos oportunidad de aprecias algunas de sus implicaciones.

Para conocer íntimamente a estas máquinas vamos a hacer un pequeño experimento mental, para eso te quiero pedir que imagines lo siguiente:

Imagina que te encuentras en una habitación cerrada, bueno no completamente cerrada porque existe en la habitación una pequeña ventana donde puedes ver una cinta blanca. Además, tienes una manivela, un lápiz y una goma, y un tablero con instrucciones. El tablero dice:

Mueve la manivela de manera que la cinta corre a la derecha hasta que veas algo escrito.

Si el signo es “1”, bórralo, escribe “0” y mueve la cinta a la derecha.

Si el signo es “0”, bórralo, escribe “1” y mueve la cinta a la derecha.

Y como no tienes otra cosa mejor que hacer, lo haces. Te puedes dar cuenta que la cinta avanza por saltos, es decir, no de manera continua; la cinta no se mueve hasta que la manivela da una vuelta y entonces brinca a la derecha. Das unas cuantas vueltas hasta que aparece un signo y el signo es: “1”.

Como tienes curiosidad de lo que pasará si cumples las instrucciones, borras el “1” y escribes “0”, y mueves la cinta a la derecha. Aparece otro “1”, de manera que repites la operación”. Después, aparece un “0”. Lo borras y escribes “1”. Mueves la cinta a la derecha y encuentras la cinta en blanco.

En ese momento una puerta (que antes no se veía por ninguna parte) se abre. Sales y encuentras la libertad.

Acabas de salir de una Máquina de Turing. O más correctamente, eras parte de una. Esta máquina en concreto calculaba el complemento a 1 de un número binario.

Ya que conoces las Máquinas de Turing desde dentro, pues estabas atrapado dentro de una, formaste parte de ella convertido en una maquinaria, ya que las conoces, digo, vamos a explicarlas.

Una Máquina de Turing, que en adelante abreviaremos como MT para ahorrarnos unos cuantos tecleos, se compone de los elementos que ya conociste:

• Una cinta infinita (bueno, no sabías que era infinita, ahora ya lo sabes),
• Una manivela que permite que la cinta se mueva discretamente (es decir, a saltos; la cinta se divide en celdas y se mueve de celda en celda)
• Un cabezal de lectura y escritura (que estaba compuesto por tus manos, tu lápiz y tu goma)
• Una tabla de instrucciones
• Un alfabeto (un conjunto de signos valido tal que tanto lo que esté escrito en la cinta como lo que se pueda escribir en ella tiene que estar definido en dicho alfabeto, en el ejemplo que imaginamos el alfabeto estaba compuesto de “0”, “1”, y espacio vacío y de hecho con este conjunto mínimo se podría realizar cualquier cómputo)
• Un conjunto de estados (un estado inicial, que fue cuando entraste al cuarto y accionaste la manivela, y un conjunto de estados finales, de los cuales en el experimento imaginario solamente hubo uno, y fue cuando terminaste el cálculo y la puerta se abrió),
• Un mecanismo que le permita cumplir con la tabla de instrucciones (no necesito recordarte cuál eras el mecanismo).

No está definido el mecanismo por el cual se cumplen las instrucciones y ahora solemos imaginar un mecanismo mecánico, electrónico, o electromecánico para ello, pero esto no es necesario. Si gustas, puedes continuar con la imagen de que en cada MT hay un pequeño humano atrapado siguiendo las instrucciones de la tabla. De hecho, así se lo imaginó Turing allá en 1936, cuando la palabra computador significaba literalmente un ser humano que seguía instrucciones con lápiz y goma en una hoja de papel.

Con estos elementos tan modestos tenemos uno de los instrumentos mentales que le han dado forma a nuestro presente, y al parecer, continuarán dándole forma al futuro.

Existe la concepción un poco mal encaminada de que Turing inventó la computadora. Si bien la idea detrás de las computadoras actuales sí proviene de las MT, la concreción física de las máquinas actuales principalmente se debe a la arquitectura de John Von Neumann, otro de las grandes mentes del siglo pasado. Lo que Turing nos presenta es una herramienta para pensar en la naturaleza y los límites del cómputo. Las MT son la formalización del algoritmo, que no estaba bien definido. Ahora consideramos que un algoritmo y una MT son intercambiables. Así que al definir una MT también estamos definiendo al algoritmo. Un algoritmo es un conjunto de instrucciones tal que sea posible de realizar por una máquina de Turing.

El poder de la MT

Resulta que todo lo que puede ser calculado por cualquier medio, puede ser calculado en una MT. A esto se le conoce como la tesis Church-Turing (Alonzo Church, que se nombra primero en esta tesis es también muy importante en esta historia y espero poder hablar de él en otra ocasión), y en realidad no puede ser demostrado, aunque se acepta como cierta mientras no se demuestre lo contrario.

Esto es demoledor. Digámoslo otra vez, lentamente. Si lo puede alguien hacer en su cabeza, en un ábaco, o en una supercomputadora del pasado, presente o futuro, entonces se puede hacer en una de esas cajitas imaginarias con humanos minúsculos dentro. Y viceversa, si lo puede hacer en un MT, entonces lo puede hacer en cualquier computadora o supercomputadora, del pasado, presente o futuro.

Se han propuesto muchos otros modelos de cómputo, y aunque muchos pueden alcanzar el resultado más rápidamente para algún algoritmo dado, ningún otro modelo de cómputo es más expresivo que las MT. Esto es, ninguno puede hacer algo que una MT no pueda.

Las MT como datos, y las Máquinas de Turing Universales.

En esencia una MT hace lo que las instrucciones dicen que haga. Y las instrucciones son datos. Siendo datos, podemos codificarlos.

Esto es, podemos traducir las instrucciones en “0”’’s y “1”’’s o en cualquier otro alfabeto que queramos. La instrucción que recibiste dentro de la máquina:

Si el signo es “1”, bórralo, escribe “0” y mueve la cinta a la derecha.

Se convierte en:

“ Borrar 0 Escribir 1 Derecha”

Que después podemos escribir como:

“B 0 E 1 D”

Y podemos definir nuestro alfabeto con esos signos: B E 0 1 D I (la I para izquierda). Con este alfabeto podemos convertir una máquina de Turing en unas cuantas líneas de código.

Ahora, atentos.

Definimos la Máquina de Turing Universal (abreviado MTU) como aquella MT que es capaz de interpretar los signos de la cinta como instrucciones. También podemos decir que una MTU es una MT capaz de simular a cualquier otra MT. Y en un lenguaje más contemporáneo diremos que una MTU es una MT programable, y que cualquier MT es un programa.

Esta es una idea importante y hermosa. Las MT dejan de ser de propósito único para convertirse en programables. Se vuelve borrosa la frontera entre datos, instrucciones, hardware y software. Una máquina de propósito único puede convertirse en datos que alimenten a otra máquina de propósito general para que ésta se comporte como aquella (ahora decimos que la simula o la programa).

Esta parte de la teoría detrás de las MT es, tal vez, la que más influencia tuvo en la construcción de las actuales computadoras. Aunque las primeras computadoras eran aproximaciones reales a las MT’s, máquinas de un solo propósito, era claro que el desarrollo tenía que ser encaminado hacia la construcción de aproximaciones a las MTU’s, o computadoras programables como lo son las actuales. Claro que como sucede a menudo en la historia de las ideas, existe un precedente importante a la idea de las máquinas programables: A mediados del siglo XIX, Ada Lovelace se convirtió en la primer programadora de la historia, al desarrollar un pequeño programa para la máquina analítica de Charles Babbage (desafortunadamente esta máquina nunca se construyó). Indudablemente el mérito de ser la primera programadora de la historia es de ella. Turing en cambio sentó bases lógicas para estudiar las propiedades del cómputo.

El problema de la parada.

Este fue el problema que motivó la invención de las MT. Encontrar un algoritmo para examinar otros algoritmos y saber si estos alcanzarán un estado final o seguirán trabajando para siempre. O, dicho de otra manera, construir una MT que nos diga si otra MT llegará a su estado final.

Lo que Turing demostró, usando sus máquinas, es que esto no es posible.

Vamos despacio, digámoslo de nuevo, porque esto es importante. Una de las limitaciones de las máquinas de Turing es la incapacidad de predecir si un cómputo se detendrá. En la vida real cuando dividimos uno entre tres, encontramos 0.33333333333333333333333…y como sabemos que nunca se detendrán los “3”, lo dejamos ahí o lo aproximamos a 0.33 o a 0.3 y nos contentamos con eso. Sin embargo, en el universo de reglas que hemos definido para una MT, esto no es así. La máquina continuará escribiendo “3” infinitamente. O tal vez no. Puede que se detenga dentro de un minuto, un mes, un año, o nunca. No lo podemos saber.

No puede definirse un algoritmo para examinar algoritmos que nos diga, solamente viendo el algoritmo, si una MT se detendrá o no. Claro, que en la vida real si una computadora se queda trabada en un cálculo más de media hora, o una hora, o un día, podemos decidir que no se detendrá. Apagamos y prendemos el programa o la máquina y listo. Pero nunca, dice Turing, estaremos seguros de que un programa va a llegar o no a un final. Al menos no lo podemos saber aplicando un algoritmo al algoritmo. Existen demostraciones maravillosas de esta imposibilidad, de manera que si al lector le interesa le será fácil encontrarlas.

Entonces…

Quiero volver a un punto que mencioné de pasada. Turing no estaba inventando las computadoras. La historia de las máquinas computadoras es también muy interesante y muy antigua. Ya en el siglo II o III A.C. se inventó una computadora con propósitos astrológicos que es increíble, la máquina de Anticitera. Alrededor de 1670 Leibniz inventó una máquina calculadora. Ya mencionamos a Ada Lovelace, y su primer lenguaje de programación para la máquina análitica de Babbage. En fin, esa es otra historia, de la que tal vez hablaré luego. Ahora estamos en el campo de las ideas, y la idea de Turing fue muy importante, tanto que todavía seguimos encontrándole aplicaciones.

Algunas de estas aplicaciones son matemáticas, otras que a mi me interesan mucho, son filosóficas.