Si estás leyendo esto, estarás usando un ordenador o similar (móvil, tablet,... o quien sabe, quizás la pantalla de una lavadora de última tecnología). Pero, ¿qué es, realmente, un ordenador?
Wir müssen wissen. Wir werden wissen.
(Debemos saber. Sabremos)
En particular, el programa de Hilbert pretendía reformular toda la matemática de forma axiomática, consistente y completa. Las consecuencias serían tremendas, incluyendo la posibilidad de demostrar "de forma automática" cualquier proposición (piensa en la hipótesis de Riemann o la conjetura de Goldbach, aún por resolver). Uno de los resultados que quería probar era el Entscheidungsproblem (problema de decisión), consistente en encontrar un algoritmo capaz de decidir si una proposición es decidible (es decir, si se puede demostrar que es o bien verdadera o bien falsa).
El primer mazazo se lo propinó Gödel, con sus teoremas de incompletitud. Gödel demostró que en cualquier sistema axiomático que contuviera la aritmética, existen proposiciones que no pueden ser probadas como verdaderas o falsas. Así que hay preguntas cuya respuesta nunca sabremos. Así que, del sueño de Hilbert volvemos al Ignoramus et ignorabimus (ignoramos e ignoraremos).
Pero el sueño de Hilbert se tornó en pesadilla debido al trabajo de Turing (y de forma independiente, de Church). Muchos de vosotros quizás conozcáis a Turing gracias a una película reciente, The imitation game (Descifrando Enigma). Además de ser el padre de la computación, Turing tuvo una vida personal fascinante, y terrible. A pesar de haber sido un héroe en la Segunda Gerra Mundial por descifrar los mensajes de los nazis codificados con la máquina Enigma, eso no le valió el respeto de Gran Bretaña, que le condenó a la castración química por el mero hecho de ser homosexual.
Para resolver el Entscheidungsproblem, Turing inventó el concepto de máquina-a (actualmente conocida como "máquina de Turing"), como prototipo de "las cosas que se pueden calcular".
La máquina de Turing original está compuesta por tres partes:
- Una cinta con instrucciones (programa). La cinta es infinita en ambas direcciones, y en ella están escritas las instrucciones empleando un conjunto de símbolos (imagínatelo como una antigua cinta de casette, en la que los dominios magnéticos apuntando en una dirección o la contraria).
- Una cabeza lectora, situada en uno de los símbolos de la cinta.
- Una memoria interna, codificada con un conjunto de símbolos.
Cuando la cabeza lectora lee un símbolo de la cinta, de forma determinista dependiendo del símbolo leído y de la memoria interna puede modificar la memoria interna, la cinta en la posición de la cabeza, mover la cabeza y finalizar la operación.
Hay un tipo especial de máquinas de Turing, las máquinas universales, capaces de simular el funcionamiento de cualquier otra máquina de Turing. Así que, con una máquina de Turing universal podemos calcular "todo lo que se puede calcular" (en realidad, con una máquina no determinista o con una cuántica se podrían calcular más cosas). La invención de Turing transformó el Entscheidungsproblem en el Halting problem (problema de parada): hay que determinar si dada una máquina de Turing y una cinta de instrucciones, la máquina se parará en algún momento.
Y la respuesta de Turing es que para algunos programas es imposible saber si se parará o no. La prueba no es demasiado complicada, y depende del hecho de que el conjunto de todas las máquinas de Turing es contable, por lo que podemos etiquetar cada máquina con un número natural:
Suponemos que la máquina \(T_Y(n, m)\) es capaz de saber si el programa \(m\) acabará al ejecutarlo en la máquina \(T_n\): si acaba, \(T_Y\) nos devuelve un 1, y si no, un 0. Entonces podemos construir otra máquina de Turing \(T_N(n)\) que nos devuelve 1 si \(T_Y(n, n) = 0\) y en caso contrario nunca para. ¿Qué pasa si evaluamos esta máquina con ella misma? Si \(T_N(N)\) se para, significa que \(T_Y(N, N)=0\), es decir, que \(T_N(N)\) no para, lo que es una contradicción. Pero si \(T_N(N)\) nunca para, entonces \(T_Y(N,N)=1\), lo que ocurre si \(T_N(N)\) para, de nuevo una contradicción. Así que no es posible determinar si la máquina \(T_N(N)\) para alguna vez o no, zanjando el Halting problem. Si te has liado, no es muy diferente de la paradoja del mentiroso: Epiménides, un cretense, dijo que todos los cretenses eran mentirosos. ¿Mentía o decía la verdad?
Y aunque la máquina de Turing nos privó de la posibilidad de calcular cualquier cosa, nos ofreció un modelo de aquéllo que sí podemos calcular: la máquina universal de Turing.
Un ordenador no es más que una máquina de Turing implementada con circuitos lógicos y electrónicos, siguiendo una arquitectura ideada por von Neumann (curiosamente, uno de los padres fundadores de la mecánica cuántica).
Si abres las entrañas de un ordenador, verás que es un caos de cables y circuitos integrados. ¿Es posible hacer máquinas de Turing más sencillas? Por supuesto, y en sencillez nadie gana a los autómatas celulares.
 |
| Seguramente, uno de mis cómics de xkcd favoritos: A bunch of rocks |
Un autómata celular es un tablero con celdas de varios colores. En cada turno del autómata, los colores de la celda cambian según los colores de las celdas vecinas.
El autómata más sencillo que es capaz de actuar como máquina de Turing es la regla 110 de Wolfram. El tablero es unidimensional, y las celdas pueden ser o blancas o negras. Si la celda es blanca, cambiará de color si su vecina de la derecha es negra. Si la celda es negra, cambiará de color si su dos vecinas son negras:
Partiendo de cualquier configuración inicial, aparecen estructuras estables que son capaces de interactuar entre sí, lo que permite emplearlas para "hacer cálculos". Por supuesto, cualquier programa práctico que te puedas imaginar sería inimaginablemente difícil de codificar en los colores de las celdas, y precisaría de una cantidad ingente de celdas y tiempo.
No hay comentarios:
Publicar un comentario