Archivo de la categoría: Computación

La máquina de Turing

cabecera

A principios de 1936, un joven Alan Turing terminó un artículo que sentó en gran parte las bases de lo que sería un ordenador actual. Para resolver el Entscheidungsproblem, uno de los problemas que traían de cabeza a los matemáticos de la época, Turing ideó un sorprendente experimento mental. Había nacido la máquina de Turing.

Alan empezó por definir lo que era un número computable: números reales cuya expresión como decimal puede calcularse por medios finitos.

A partir de esta definición, Turing ideó una máquina imaginaria que pudiera tratar con números computables. Las características son las siguientes:

  • Alberga un número finito de condiciones, a las que llamó configuraciones-m (q_i).
  • La máquina tiene una cinta dividida en celdas, cada una de los cuales puede tener escrito un símbolo. La cinta pasa a través de la máquina y tiene una longitud infinita.
  • En cada momento de funcionamiento de la máquina, una sola celda de la cinta estará dentro de ella.

A la celda de la cinta que puede leer la máquina, le llamaremos la celda activa. El símbolo dentro de esta celda es el único dato de entrada que conoce la máquina en un momento dado, pero a través de cambios de configuraciones, se puede tener conocimiento de los símbolos leídos anteriormente.

La configuración-m activa en la máquina, junto al símbolo de la celda activa, forman la configuración de la máquina en un momento dado.

Turing definió también las posibles acciones que podía realizar la máquina:

  • Escribir un símbolo en la celda activa (P).
  • Borrar símbolo de la celda activa (E).
  • Mover la cinta una posición hacia la izquierda (L).
  • Mover la cinta una posición hacia la derecha (R).
  • Finalmente, en cada paso puede producirse un cambio en la configuración.
Esquema de una máquina escrito por Turing. En concreto para la máquina que escribe la secuencia 001011011101111...

Esquema de una máquina escrito por Turing. En concreto para la máquina que escribe la secuencia 001011011101111…

Turing dio dos ejemplos sencillos de máquinas. Una escribía la secuencia 01010101… y otra escribía la secuencia 001011011101111… A continuación vamos a ver un ejemplo de ésta última. En concreto esta máquina escribe la secuencia con un espacio entre cada dígito, algo que Turing encontró muy cómodo a la hora de realizar estas secuencias.

La primera tabla que podéis ver en el ejemplo es la tabla de configuraciones, que consta de:

  • Configuración: identificador de la configuración
  • Símbolo: símbolo que junto al código de configuración activa las acciones
  • Acciones: acciones a realizar cuando la máquina se encuentra en ese modo de configuración y con uno de los símbolos correspondientes en la celda activa.
  • Nueva configuración: configuración a la que pasa la máquina cuando acaba sus acciones.

En la fila que se puede ver abajo tenemos la cinta. La máquina comienza escribiendo una secuencia de inicio, que le servirá para controlar el proceso.

En verde aparecerá la próxima configuración que se ejecutará, en naranja la que se acaba de ejecutar. Si la siguiente configuración es la misma que la que se acaba de ejecutar, se mantiene el color naranja.

El pase de diapositivas requiere JavaScript.

Podemos realizar cualquier cálculo que se nos ocurra con una máquina de Turing. Los ejemplos que dio Turing eran sencillos porque buscaba la comprensión del lector. A poco que busquéis, veréis que se han hecho todo tipo de ejemplos de máquinas de Turing, en la documentación de un curso de análisis de algoritmos de la universidad Cornell, hay un artículo, que en la página ocho, describe como hacer una criba de Eratóstenes para saber si el número de símbolos 1 de una cadena de entrada es primo.

Una vez definido el funcionamiento de la máquina, Turing pasó a buscar una forma de encontrar un número que describiera a la máquina. Para ello modificó la forma de expresar la escritura en la cinta y pasó de los símbolos P0, P1 o Px a identificar cada escritura con un número. Por ejemplo, si el alfabeto con el que permite trabajar la máquina es {x, 0, 1,…},  tendríamos que Px pasaría a ser S0, P0 pasaría a ser S1 y P1 pasaría a ser S2. A continuación estableció una correspondencia entre configuraciones y acciones y letras:

  • Cada configuración-m q_i, será sustituida por una D, seguida de un número de Aes igual al subíndice i.
  • Cada escritura S_i, será sustituida por una D y tantas Ces, como valor tenga i.
  • R (mover a la derecha), L (mover a la izquierda), E (borrar) se escribirán con sus letras correspondientes.
  • Si no hay acciones en la configuración, se escribe una N.
  • Para separar una configuración de otra, se usará el punto y coma.

Además ya no podremos resumir la tabla, cada entrada de la tabla de configuración tendrá un solo símbolo activo. En nuestro ejemplo teníamos una fila de la tabla configuración así:

q3 0 o 1 R, R q3

Ahora lo que tendremos es dos líneas: q3S1RRq3 y q3S2RRq3

Los valores dentro de estas cadenas los traduciremos por:

  • q3: DAAA
  • S1: DC
  • RR: RR
  • S2: DCC

Quedándonos DAAADCRRDAAA; DAAADCCRRDAAA;

A esta cadena de texto, Turing la llamó “la descripción estándar de la máquina”. A continuación asignó un número a cada letra (A=1, C=2, D=3, L=4, R=5, N=6, ;=7), así que nuestra descripción estándar anterior pasaría a ser:

31113255311173111322553117

Y a este número Turing lo llamó “número de descripción (DN) de la máquina”. Gracias a este número, tenemos una forma de darle un único identificador a cada máquina de Turing que ideemos, un identificador que además la describe totalmente.

 La máquina de Turing universal

¿Y qué hacemos con este número? El siguiente paso de Turing fue idear una nueva máquina, a la que llamó “máquina universal”, a partir de ahora U. Ésta máquina tiene una configuración tal que, si le introducimos a través de la cinta un número de descripción de otra máquina, puede configurarse de tal manera que se convierte en la máquina que describe ese número.

Es decir, tenemos una computadora (máquina universal) a la que podemos introducirle cualquier software que se nos ocurra (número de descripción) y ejecutará las instrucciones que correspondan.

El primer paso que realizó Turing para abordar el Entscheidungsproblem fue solucionar primero un problema más simple: ¿se podría construir una máquina (D) que al recibir un número de descripción de otra máquina (T) pudiera decirnos si T termina su ejecución?

Para Turing que una máquina terminara su ejecución quería decir que en algún momento de su funcionamiento, no tenía más pasos que realizar. La máquina no era cíclica. En el caso de que la máquina estuviera realizando operaciones sin fin, la máquina se consideraba cíclica.

Si existiera esa máquina D, podríamos pasarle a través de la cinta el número de descripción de una máquina (G) que para cada número par entero n mayor que dos, busca dos números primos cuya suma sea n y pasa a calcular el siguiente número, a no ser que no encuentre esos dos números primos, entonces parará. Si la máquina D nos indica que la máquina G no termina nunca, habríamos demostrado la conjetura de Goldbach.

¿Puede existir la máquina D? Por desgracia no puede existir. Para demostrarlo Turing utilizó la diagonalización de Cantor, pero incluso él mismo indica que éste método es engorroso y ofreció una explicación más sencilla.

Imaginemos que la máquina D existe. Por tanto podemos pasarle cualquier número de descripción de una máquina T y nos dirá si ésta es cíclica o no.

Ahora utilizamos esta máquina D y creamos una máquina híbrida, denominada DU. La máquina DU en primer lugar funcionará en modo D, y comprobará si el número de descripción de la máquina T que llega en la cinta corresponde a una máquina circular. Si la máquina T es circular, finaliza el trabajo de DU. Si la máquina T no es circular, DU pasa al modo U, que se configurará con el número de descripción de T y realizará los pasos determinados por esta máquina (T).

DU es una máquina no cíclica, ya que cuando reciba el número de una máquina cíclica desechará éste número y terminará. Cuando le pasemos un número de una máquina no cíclica, la ejecutará, y ya sabemos que es no cíclica. Por tanto DU es una máquina que siempre termina su ejecución en algún punto.

¿Pero qué pasa si a la máquina DU le pasamos el número descriptor de la propia DU?

1.- DU se sitúa en modo D y comprueba que el número de descripción, correspondiente a DU, pertenece a una máquina no cíclica.

2.- DU se sitúa en modo U y se configura para ejecutar la máquina DU’ (le ponemos el ‘ para distinguirla de la máquina DU inicial).

3.-DU’ inicia su ejecución, se sitúa en modo D y comprueba que el número de descripción que se encuentra en la cinta, correspondiente a una máquina DU, pertenece a una máquina no cíclica.

4.- DU’ se sitúa en modo U y se configura para ejecutar la máquina DU”.

Podéis imaginar como sigue el proceso, cada máquina DU configurada volverá a crear otra máquina DU, hasta el infinito. Con esta elegante demostración, Turing reducía al absurdo la posibilidad de la existencia de una máquina D.

Todavía le quedaban unos cuantos pasos para acabar con el Entscheidungsproblem, pero si sigo, puedo acabar así:

life_of_brian___stoning_gif_by_kraljaleksandar-d3c7mbj

De pronto me han dado ganas de lentejas.

 

Legado

Los conceptos que presentó en este documento, junto a su trabajo en las máquinas Colossus para el descifrado de códigos de Enigma, situaron a Turing como uno de los mayores expertos en computación al final de la Segunda Guerra Mundial. Von Neumann quiso contar con él, pero en su breve visita a EEUU no se sintió cómodo y volvió a Inglaterra, donde creó el primer ordenador británico: ACE.

Mientras, en EEUU, se creaba el ENIAC y Von Neumann ponía nombre, de manera un tanto injusta, a su arquitectura. Prácticamente todos los ordenadores de hoy en día utilizan la arquitectura Von Neumann, en la que tanto  el programa a ejecutar como los datos, se encuentran en una misma memoria. Éste era el concepto que Turing adelantó en 1936 que acabaría imponiéndose en la breve historia de los computadores.

Arquitectura Von Neumann (Fuente Wikipedia)

Esta entrada participa en la edición 5.7 del Carnaval de Matemáticas, dedicada a Alan Turing y alojada por este blog.

turing

Referencias

On computable numbers with an application to the Entscheidungsproblem. Alan Turing.

Alan Turing. El hombre que sabía demasiado. David Leavitt. Antoni Bosch editor.

A %d blogueros les gusta esto: