La máquina de Turing
En 1936, independientemente y con pocos meses de diferencia, se crearon dos definiciones matemáticas del concepto de algoritmo. La primera fue concebida por el lógico norteamericano Alonzo Church y la segunda, por el lógico inglés Alan Turing (1). Aunque ambas concepciones son equivalentes, la idea de Turing resulta intuitivamente más clara, por lo que en toda la exposición sólo nos referiremos a ella (2).
Para Turing el concepto de algoritmo puede asimilarse al de una máquina abstracta, una computadora teórica hoy conocida como máquina de Turing. Esta máquina consta en primer lugar de una cinta, en la cual se anotará la entrada y la salida del algoritmo y que servirá a la vez de memoria de trabajo del dispositivo.
La cinta está dividida en celdas o casillas, cada una de las cuales puede contener un único símbolo (que indicaremos como #) o bien puede estar vacía. La cinta, además, es potencialmente infinita, esto significa que tanto hacia la derecha como hacia la izquierda podemos agregar todas las celdas que sean necesarias. La cantidad inicial de símbolos # es siempre finita.
La máquina consta también de un cursor que puede ver el contenido de una casilla a la vez. Cuando la casilla observada está vacía el cursor puede, si sus instrucciones así lo indican, anotar en ella un símbolo #. Si la casilla tiene ya un símbolo #, el cursor puede borrarlo, dejando la casilla vacía. Por otra parte, el cursor puede moverse a razón de una casilla por vez, tanto hacia la derecha como hacia la izquierda. Debido a la infinitud de la cinta, el cursor nunca encontrará límites para su movimiento.
Las acciones del cursor están dirigidas por un programa o conjunto de instrucciones. En un momento dado, la máquina puede estar en uno de una cantidad finita de estados posibles (que indicaremos como q0, q1, q2,..., qn). El programa le indica a la máquina qué debe hacer dependiendo del estado en que ésta se encuentre y de qué contenido tenga la casilla que el cursor está viendo.Consideremos por ejemplo el siguiente programa:
q1 + # -> 0 D q2
q1 + 0 -> 0 I q1
q2 + # -> # S q0
q2 + 0 -> 0 D q2
A la izquierda aparecen todos los estados en que la máquina puede hallarse, excepto q0, y el contenido de la casilla que observa el cursor (0 es vacío). A la derecha se indica qué debe hacer el cursor en cada circunstancia. La primera instrucción (la máquina está en el estado q1 y el cursor está viendo un #) dice que el cursor debe borrar el símbolo de la casilla (ésta queda vacía) y luego debe moverse un lugar a la derecha, luego la máquina finalmente pasa al estado q2. La segunda instrucción dice que (si la máquina está en el estado q1 y el cursor está viendo una casilla vacía) entonces la celda debe quedar vacía, el cursor se mueve un lugar a la izquierda y la máquina queda en el estado q1. La S de la tercera instrucción significa que el cursor queda en su posición inicial. El estado q0 es el estado final, cuando la máquina pasa a él se detiene de inmediato. Es decir, el estado q0 indica que el cómputo ha terminado.
Convenimos en que inicialmente cualquier máquina se encontrará en el estado q1 y que el cursor observará el primer símbolo # de la izquierda.
Notas:
(1) Turing había nacido en 1912, por lo que, como Gödel, tenía menos de 25 años al publicar su trabajo fundamental. Tristemente, la vida de ambos fue difícil y terminó trágicamente. Turing se suicidó en 1954, abrumado por las presiones sociales causadas por su homosexualidad. Gödel, por su parte, sufrió a lo largo de toda su vida de periódicos y cada vez más profundos ataques de paranoia. Finalmente, en 1978, convencido de que existía una conspiración para envenenarlo, dejó de comer y murió de inanición.
(2) El artículo original de Turing lleva por título: On computable numbers with an aplication to the Entscheidungsproblem, y fue publicado en el Proceedings of London Mathematical Society, vol. 42 (1937), pp. 230 – 265.
(A la parte 2 - A la parte 4)
No hay comentarios.:
Publicar un comentario