Matemáticas y Ciencia Ficción: Las máquinas de Turing

'Bienvenida al Castillo Turing —dijo el señor con voz metálica.'

Cuando Nell, una de las protagonistas de La era del diamante de Neal Stephenson, entra en el Castillo Turing en la aventura interactiva de su Manual Ilustrado para Señoritas no tiene ni idea de que se dispone a aprender sobre máquinas de Turing. Más adelante usará este conocimiento para resolver diferentes problemas y puzzles propuestos por el Manual y también para explorar la naturaleza de la consciencia y la mente humana. Pero, ¿qué son las máquinas de Turing?

Las máquinas de Turing fueron definidas por Alan Turing, uno de los científicos y matemáticos más importantes del siglo 20. Turing es considerado por muchos como uno de los padres de la informática moderna y en 2012 estamos celebrando el céntesimo aniversario de su nacimiento. En 1936, Turing introdujo un dispositivo abstracto capaz de realizar todo tipo de computaciones simbólicas, un precursor del ordenador moderno que sería conocido como máquina de Turing.

En La era del diamante, Stephenson hace un buen trabajo describiendo las máquinas de Turing. Citaré algunos pasajes de esta novela de ciencia ficción con el objeto de proporcionar una introducción informal a estos dispositivos. 

Las máquinas de Turing tienen una cinta dividida en casillas que almacenan símbolos. Una cabeza lee estos símbolos y realiza diferentes acciones de acuerdo a su conjunto de instrucciones, su estado interno y el contenido de la cinta. En la versión de Stephenson:

'La cerradura sólo tenía unas partes que podía observar: la manivela, el cerrojo y un par de ruedas de cobre en la parte alta con dígitos grabados del 0 al 9 (...). El número en la parte alta cambiaba con cada eslabón que entraba en la máquina, y parecía determinar, de forma limitada, lo que la máquina haría a continuación (...)'

Una máquina de Turing con su cabeza en estado q1 y leyendo una casilla que contiene un 0 (imagen tomada de Wikipedia)

Una característica importante de las máquinas de Turing es que su cinta (su memoria) es potencialmente infinita. Aunque sólo usan un número finito de casillas es un momento dado, no hay una cota superior para cuántas pueden llegar a usar. Stephenson explica este hecho con una interesante metáfora:

'La cadena que contenía el programa del duque colgaba a cada lado por esos agujeros. Nell intentó arrojar piedras por los agujeros, pero no oía cómo chocaban con el fondo; la cadena debía de ser increíblemente larga.'

La cinta infinta de una máquina de Turing (imagen tomada de Wikipedia)

Sobre el modo en que una máquina de Turing funciona, esto es lo que Nell averigua:

' (...) había descubierto que si el número resultaba ser 09, y el siguiente eslabón de la cadena estaba en posición vertical (que el duque llamaba uno), las ruedas giraban y cambiaba al número 23. Pero si el siguiente eslabón era, en su lugar, un cero (como llamaba el duque a los eslabones con palancas horizontales), el número en las ruedas cambiaba al 03. Pero eso no era todo: en ese caso, la máquina, por alguna razón, invertía la dirección en que se movía la cadena a través de la máquina, y también cambiaba la palanca del cero al uno. Es decir, la máquina podía escribir en la cadena así como leer de ella.'

Como podemos ver, las acciones que la máquina puede ejecutar están reducidas a moverse a la izquierda o la derecha (y, por tanto, explorar otra casilla de la cinta), reemplazar el símbolo de la cinta y cambiar su estado interno. En el vídeo que se encuentra bajo estas líneas podemos ver una máquina de Turing en acción (se trata de un modelo desarrollado con Lego Mindstorms en la Univesidad de Aarhus).

A pesar de su modesta apariencia, estas pocas acciones son todo lo que se necesita para realizar cualquier computación posible (esto se conoce a veces con el nombre de Tesis de Church-Turing). De hecho, cualquier otro dispositivo de cómputo podría ser simulado (aunque a una velocidad muy lenta) por una máquina de Turing con un conjunto adecuado de instrucciones. Esto es usado por Nell para resolver uno de los puzzles:

'(...) llegó a un castillo con un magnífico órgano, movido por la presión del aire y controlado por una desconcertante red de barras, que podía tocar música almacenada en una cinta de papel con agujeros. Un misterioso caballero negro había programado el órgano para tocar una tonada triste y deprimente, hundiendo al lugar en una profunda depresión, de forma que nadie trabajaba y ni siquiera salía de la cama. Con algunas pruebas, la Princesa Nell estableció que el comportamiento del órgano podía simularse con una disposición extremadamente sofisticada de compuertas, lo que significaba, a su vez, que podía reducirse igualmente a un increíblemente largo y complejo programa para una máquina de Turing.'

En particular, añadir nuevas cintas o cabezas al modelo de las máquinas de Turing no incrementaría su capacidad computacional. Como Nell descubre leyendo un informe escrito por el Duque de Turing:

  'No importa lo complicado que fuese el diseño. El duque siempre encontraba la forma de simular su comportamiento poniendo una cadena lo suficientemente larga en una de las máquinas de Turing tradicionales. Es decir, aunque las máquinas paralelas y multidimensionales funcionaban mucho más rápidas que el modelo original, realmente no hacían nada que fuese diferente.'

Uno de los resultados más importantes en el artículo original de Turing es que las máquinas de Turing, a pesar de ser capaces de ejecutar cualquier algoritmo, no pueden resolver todos los problemas posibles. Esto, a su vez, implica que no todos los problemas matemáticos pueden ser resueltos sólo con computación, un resultado similar al Teorema de Incompletitud de Gödel. De hecho, ninguna máquina de Turing puede determinar en un tiempo finito si una máquina de Turing dada parará para una entrada determinada o seguirá computando para siempre. Este problema autoreferencial se conoce como el Problema de la parada y es central en el estudio de los límites de la computación y de los fundamentos de las Matemáticas. En La era del diamante, Nell parece conocer estas limitaciones, aunque son mencionadas en una manera bastante filosófica que también está relacionada con otra de las ideas de Turing, el famoso Test de Turing:

'En el Castillo Turing había aprendido que una máquina de Turing no podía entender realmente a un ser humano. Pero el Manual era en sí mismo una máquina de Turing, o eso sospechaba; así que, ¿cómo podía entender a Nell?'

Si quieres aprender más acerca de máquinas de Turing, hay varios buenos libros de divulgación. Tanto Gödel, Escher, Bach de Douglas R. Hofstadter como La nueva mente del emperador de Roger Penrose exploran, entre otras muchas cosas, el concepto de máquina de Turing y sus implicaciones para la posibilidad de crear una inteligencia artificial. Para una aproximación formal y matemática, recomiendo Introducción a la Teoría de Autómatas, Lenguajes y Computación de John E. Hopcroft, Rajeev Motwani y Jeffrey D. Ullman.

(Esta entrada es mi participación en la edición 3.1 del Carnaval de Matemáticas que en esta ocasión tiene como anfitrión a Scientia potentia est)

(You can read this post in English/Puedes leer esta entrada en inglés)

Mathematics and Science Fiction: Turing Machines

(Disclaimer: English is my second language, so I want to apologize in advance for there may be mistakes in the text below. If you find any, please let me know so that I can correct it. I'd really appreciate it. Thanks.)   

'"Welcome to Castle Turing," said the lord in a metallic voice.'

When Nell, one of the protagonists of The Diamond Age by Neal Stephenson, enters Castle Turing in the interactive adventure of her Young Lady's Illustrated Primer she doesn't know that she is going to learn about Turing machines. She will later use this knowledge to solve different problems and puzzles posed by the Primer and also to explore the nature of consciousness and the human mind. But, what are Turing machines?

Turing machines were first defined by Alan Turing, one of the most important scientists and mathematicians of the 20th century. He is considered by many as one of the fathers of modern Computer Science and in 2012 we are celebrating the 100th anniversary of his birth. In 1936, Turing introduced an abstract device capable of performing all kinds of symbolic computations, a precursor of modern computers that would become known as the Turing machine.

In The Diamond Age, Stephenson does a very good job of describing Turing machines. I will quote from this science fiction novel in order to provide a gentle and informal introduction to these devices.

Turing machines have a tape divided into cells where symbols are stored. A tape head reads these symbols and performs different actions according to its set of instructions, its internal state and the content of the tape. In Stephenson's version:

'The lock only had a few parts that she could observe: the crank, the bolt, and a pair of brass drums set into the top with digits from 0 to 9 engraved in them (...). The number on the top changed with every link that went into the machine, and it seemed to determine, in a limited way, what the machine would do next (...)'

A Turing machine with its head in state q1 and scanning a cell which stores 0 (image taken from Wikipedia)

An important characteristic of Turing machines is that their tape (their memory) is potentially infinite. Although they only use a finite number of cells at a given time, there is no upper bound on how much cells they can use. Stephenson explains this with a striking metaphor: 

'The chain containing the Duke's program dangled on either side into these holes. Nell tried throwing stones into the holes and never heard them hit bottom; the chain must be unfathomably long.'

The infinite tape of a Turing machine (image taken from Wikipedia)

As for the way the Turing machine works, this is what Nell finds out:

' (...) she had learned that the number happened to be 09, and if the next link in the chain was in the vertical position (which the Duke referred to as a one), the drums would spin around and change the number to 23. But if the next link was, instead, a zero (as the Duke referred to links with horizontal toggles), the number drums would change to 03. But that wasn't all: In this case, the machine would, for some reason, reverse the direction in which the chain was moving through the machine, and also flick the toggle from zero to one. That is, the machine could write on the chain as well as read from it.'

As we can see, the actions that the machine can execute are reduced to moving left of right (and thus exploring another cell of the tape), replacing the symbol on the tape for another one and changing its internal state. In the video below we can see a Turing machine in action (this is a Lego Mindstorms model developed at Aarhus University).

Despite their humble appearance, these few actions are all that is needed in order to perform any possible computation (this is sometimes known as the Church-Turing thesis). In fact, any other computing device could be simulated (albeit very slowly) by a Turing machine with a suitable set of instructions. This is used by Nell to solve one the puzzles:

'(...) she came to a castle with a magnificent organ, powered by air pressure and controlled by a bewildering grid of push-rods, which could play music stored on a roll of paper tape with holes punched through it. A mysterious dark knight had programmed the organ to play a sad, depressing tune, plunging the place into a profound depression so that no one worked or even got out of bed. With some playing around, Princess Nell established that the behavior of the organ could be simulated by an extremely sophisticated arrangement of water-gates, which meant, in turn, that it could just as well be reduced to an unfathomably long and complicated Turing machine program.'

In particular, adding new tapes or head tapes to the Turing machine model does not increase its computational power. As Nell learns by reading a report written by the Duke of Turing:

  'No matter how complicated his designs became, the Duke always found a way to simulate their behavior by putting a sufficiently long chain into one of the traditional Turing machines. That is to say that while the parallel and multidimensional machines worked more quickly than the original model, they didn't really do anything different.'

One the most important results in Turing's seminal paper is that Turing machines, despite being able to run any algorithm, can't solve all possible problems. This, in turn, implies that not all mathematical problems can be solved by computation alone, a result similar to Gödel's Incompleteness Theorem. In fact, no Turing machine can determine in a finite amount of time whether a given Turing machine will stop its computation with a given input or will compute forever. This autorefential problem is known as the Halting problem and it's central to the study of the limits of computation and to the foundations of Mathematics. In The Diamond Age, Nell also seems to know about these limitations, although they are stated in a rather philosophical way which is also related to another of Turing's ideas, the famous Turing Test:  

'In Castle Turing she had learned that a Turing machine could not really understand a human being. But the Primer was, itself, a Turing machine, or so she suspected; so how could it understand Nell?'

If you want to learn more about Turing machines, there are several good popular accounts. Both Gödel, Escher, Bach by Douglas R. Hofstadter and The Emperor's New Mind by Roger Penrose explore, among many other things, the concept of Turing machine and its implications to the possibility of creating an artificial intelligence. For a formal, mathematical approach I recommend Introduction to Automata Theory, Languages and Computation by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman.

(You can read this post in Spanish/Puedes leer esta entrada en castellano)