Pocas criaturas en la naturaleza poseen esa constancia y tesón propios de los castores, trabajadores incansables que, ramita a ramita, construyen sus presas. Fue sin duda esa conducta la que indujo a Tibor Rado a bautizar con el nombre de «juego del castor laborioso» a cierto problema que plantea la Máquina de Turing.

En los albores de la informática, Alan Turing, matemático inglés, estableció las bases de la computación mucho antes de que existieran los medios técnicos y electrónicos para llevarlas a cabo. Diez años antes de que esto sucediera, Turing predijo, valiéndose de teoremas lógicos y matemáticos recientemente descubiertos, que no toda función era computable. No importa la cantidad de memoria o de potencia de proceso que dispongamos, existen ciertas funciones que a pesar de utilizar una maquinaria automática de capacidad infinita, no podrán ser calculadas por ella. Esto supone un duro revés a los que ciegamente creen en las capacidades de las nuevas tecnologías, y presenta nuevos retos a aquellos que pretender abordar esos problemas con soluciones parciales.

Dentro de esos retos se encuentra, como ya hemos dicho, el «juego del castor laborioso» formulado por Tibor Rado [Rado 1962]. En cuanto ha su definición es bastante simple. Un «castor laborioso» es una Máquina de Turing que cumple dos condiciones:

1. Al poner al «castor» en funcionamiento sobre una cinta totalmente ocupada por ceros acaba por detenerse.

2. El número de unos que imprime no es inferior al que pueda imprimir cualquier Máquina de Turing de igual número de estados que llegue a detenerse.

Figura 1.- Castor laborioso de 3 estados. Esquema obtenido de [Dewdney, A. K. 1990].

A lo largo del presente artículo iremos explicando qué es una Máquina de Turing, qué representa la cinta de la máquina y otros aspectos necesarios para comprender esta definición.

La función «castor laborioso» o «busy beaver» (BB(n)) presenta mucha dificultad para valores de n superiores a 5. Todos los esfuerzos en la comprensión y resolución de esta función han sido ayudados por un ordenador, dada la magnitud del problema y el inmenso universo de posibles soluciones. Los cuarenta años de estudio sobre este tema no arrojan demasiada luz al respecto, si bien es cierto que investigadores de renombre como Heiner Marxen y Juergen Buntrock, de la Universidad de Berlín; o Penousal Machado y Roberto B. Pereira, de la Universidad de Coimbra han aportado novedosos métodos para su resolución.

Antecedentes Matemáticos

A finales del siglo XIX y durante la primera mitad del XX los principios matemáticos y lógicos sufrieron una profunda crisis. Bertrand Russell (1872-1970) a través de su «Principia Matemática» [Garciadiego 1992], analizó las relaciones entre la lógica y las matemáticas puras, para explicar de esta manera los principios de las matemáticas. Durante este trabajo, estudió paradojas o antinomias que escapaban a los límites de las matemáticas de entonces como la paradoja del numero cardinal máximo o su ataque a la teoría de conjuntos sobre «la clase de todas las clases que no son miembros de sí mismas».

Figura 2.- Kurt Gödel revolucionó el mundo de la lógica.

En 1931, Kurt Gödel (1906-1978), con su artículo «Sobre proposiciones formalmente indecidibles de los Principia Mathematica y sistemas afines» («Uber forma unentscheidbare Sätze der Principia Matemática und verwandter Systeme») [Nagel 1994] resquebraja la lógica y matemáticas de su tiempo. Su principal resultado es el Teorema de la incompletud de la aritmética («Teorema de Gödel») por el que se establece que todo sistema formal deductivo que añada, cuando menos, al aparato de la lógica elemental los principios y las reglas de la aritmética se enfrentará fatalmente con proposiciones bien construidas que no podrá demostrar ni refutar y que, por lo tanto, son «indecidibles». Esto delata que el sistema es «incompleto». El artículo de Gödel dio al traste con el formalismo de su maestro Hilbert, vigente por entonces, y revolucionó los planteamientos de la lógica. El hecho de que se detectasen anomalías de esa importancia en un sistema lógico que pretendía formalizar una pieza del saber científico tan venerable y segura como es la aritmética elemental, contribuyó a determinar la crisis de confianza de los años 30 en el optimismo de la razón.

Años más tarde, en 1994, Roger Penrose (1931-) se valió en su «Sombras de la Mente» («Shadows of the Mind: A Search for the Missing Science of Consciousness») [Penrose 1994] del Teorema de Gödel para cuestionar los supuestos de la inteligencia artificial, y probar que la mente humana tiene capacidades que son no-computables. Los trabajos de Roger Penrose en este sentido han recibido múltiples críticas de otros investigadores, y el debate permanece abierto en el seno de los científicos estudiosos de la Inteligencia Artificial. ¿Seremos capaces de formalizar toda la capacidad de inferencia y razonamiento de la mente humana, o demuestran estos teoremas que es una misión imposible?

Teoría de la Computación

El Teorema de Incompletud de Gödel motivó a Alan Turing (1912-1954) a estudiar qué funciones eras susceptibles de poder ser calculadas y cuáles no. Para ello se sirvió de su Máquina de Turing (que explicaremos más adelante), una máquina de propósito general mediante la que formalizó las funciones y procedimientos de cálculo.

Turing demostró que existían funciones que no son posibles de calcular mediante la Máquina de Turing. El paradigma de este conjunto de funciones lo representa la función que establece si dada una Máquina de Turing, ésta produce un resultado o, por el contrario, se queda calculando indefinidamente. Esta función, conocida con el nombre de «Problema de Parada» (Halting Problem), será pieza fundamental para demostrar la incomputabilidad de ciertas funciones.

Figura 3.- Alan Turing, padre de la informática.

Así pues, Turing dividió las funciones en computables y no computables, en función de si existía una Máquina de Turing que era capaz de realizar dicha función o no era posible diseñar la Máquina de Turing especifica para esa función. La incompletud y la incomputabilidad son importantes para comprender el proceso del cálculo, sin embargo, la noción de intratabilidad tuvo repercusiones más importantes. En términos generales se dice que un problema se considera intratable si el tiempo necesario para la resolución de determinados casos de esa clase de problemas crece, al menos, exponencialmente con el tamaño de esos casos. Turing y Alonzo Church, su ex-profesor, afirmaron lo que se conoció como la Tesis de Church-Turing que dice que si un problema que se pude representar en una Máquina de Turing no es resoluble para ésta, tampoco lo será para el pensamiento humano. Las interpretaciones «fuertes» de la tesis de Church-Turing proponen una equivalencia esencial entre lo que un ser humano puede pensar o conocer y lo que una máquina puede calcular. Nos encontramos así ante la desconcertante situación de ser capaces de definir un problema, demostrar que sólo tienen una respuesta válida y, sin embargo, saber que nunca se podrá conocer esa respuesta.

A mediados de la década de los 60, Cobham y Edmonds [Edmonds 1965] estudiaron la diferencia entre crecimiento polinomial y exponencial de la complejidad de un problema. Es este un concepto importante, ya que un crecimiento exponencial implica la imposibilidad de resolver en un tiempo razonable casos de tamaño reducido. Dicho esto, será necesario reducir el problema general en subproblemas que sí sean tratables en lugar de manejar el problema no tratable. Para realizar ese proceso, durante la misma década se estudió la reducción, es decir, la transformación general de una clase de problemas a otra, de manera que la solución de la primera clase se obtenga reduciendo ésta a problemas que pertenecen a la segunda y resolviendo éstos.

A comienzos de los años 70, Steven Cook y Richard Karp introdujeron la Teoría de la Completud NP [Cook 1971], mediante la que se explica la existencia de grandes clases de problemas canónicos de razonamiento y búsqueda combinatoria que son NP completos. Toda clase de problemas a la que una clase de problema NP completo pueda reducirse posiblemente será intratable. Esto choca frontalmente con el entusiasmo que se creó en torno a la Inteligencia Artificial y sus múltiples posibilidades. A pesar de que la potencia y velocidad de los ordenadores es cada vez mayor, y de los avances en sistemas inteligentes, las teorías que analizan la complejidad de los problemas demuestran que hay problemas que precisan una capacidad de cálculo a la que actualmente no tenemos acceso (y probablemente nunca lo tendremos).

Máquinas de Turing

Hasta 1936 todos los mecanismos y autómatas conocidos era de propósito particular, es decir, que todo mecanismo construido o ideado hasta la fecha estaba enfocado en una tarea concreta. Sin embargo, la idea de autómata tal y como es utilizada hoy en día, y que da lugar a la Teoría de autómatas, aparece con la formulación de la Máquina de Turing. Todo parte de la historia ya mencionada sobre lo que se conoció como el segundo problema de Hilbert (Enstscheidungsproblem), que consistía en demostrar que los axiomas de la aritmética ordinaria eran consistentes entre sí (coherentes o sin contradicción). Este problema condujo a uno más general, el problema de decisión, que pretendía descubrir un método general para determinar si una fórmula de la lógica formal podía o no satisfacerse (declararse verdadera).

En 1936, Alan Turing, mientras estudiaba este problema, se plantea como definir con precisión la idea de método. Para ello define primero la idea intuitiva de algoritmo como un procedimiento que puede ser ejecutado mecánicamente sin intervención creativa alguna. A continuación define el proceso de computación como aquel en el que un algoritmo es descompuesto en una secuencia de pasos atómicos simples. Y concluye diciendo que el sistema resultante es una construcción lógica que hoy en día conocemos como Máquina de Turing. Una Máquina de Turing es un mecanismo teórico compuesto de una cabeza lectora/escritora y una cinta de caracteres de longitud infinita. La cabeza lectora/escritora se va desplazando a lo largo de la cinta, escribiendo o leyendo en función de una tabla de transiciones que gobierna el funcionamiento de la Máquina de Turing, y en función del estado inicial de la cinta. La cinta es, por tanto, ilimitada en cuanto a longitud, unidimensional, y dividida en una secuencia de posiciones que pueden estar ocupadas por un símbolo o un espacio en blanco (caracteres).

Figura 4.- La Máquina de Turing, constructo de un ordenador «ideal».

La tabla de transiciones se define en base a estados y acciones. Al comienzo de cada estado, se analiza la entrada obtenida tras la lectura de la cinta, y se realiza la acción asociada. Finalmente se cambia de estado, pudiendo volver al mismo estado en el que empezó la acción.

Veámoslo con un ejemplo:

Tabla 1.- Tabla de Transiciones.

Esta tabla representa una Máquina de Turing de un estado (Estado0) que va llenando la cinta con unos, independientemente de cómo se encontrase esa cinta con anterioridad. Si lee un 0, escribe un 1 y vuelve a leer. Cuando lee un 1, mueve la cabeza lectora/escritora hacia la derecha, y así sucesivamente.

Tal y como hemos visto anteriormente, una Máquina de Turing está compuesta por un autómata finito de estados (Tabla de Transiciones) y una cinta de longitud infinita donde se escriben y de donde se leen símbolos de un alfabeto predefinido. El autómata procede a la lectura de la cinta que contiene una serie de símbolos, tomados de un conjunto, y opera sobre ellos según sus reglas produciendo finalmente una salida en la cinta. Si dos configuraciones finales o salidas (el resultado aparecido en la cinta una vez la Máquina de Turing se ha detenido) difieren, entonces necesariamente las entradas fueron diferentes. Esto es cierto para la misma Máquina de Turing, es decir, para Máquinas de Turing con autómatas finitos de estados equivalentes.

Podemos considerar que la Tabla de Decisiones que define el autómata finito de estados es el programa de la Máquina de Turing, mientras que las cadenas de símbolos en la cinta son los datos iniciales sobre los que opera el programa. Podemos cambiar los programas de las Máquinas de Turing y entonces se dará el caso de que para estados iniciales de la cinta idénticos, diferentes programas darán como resultado diferentes estados finales o salidas. Pero también puede darse el caso de que, cambiando los programas y operando sobre los mismos datos, las salidas sean las mismas. En esta propiedad se basa el hecho importante de que cualquier modificación que hagamos en el programa que rige el comportamiento de una Máquina de Turing, puede ser simulada por otra Máquina de Turing con diferente programa si añadimos una determinada cadena de símbolos a la cadena de símbolos inicial (entrada).

Siempre podremos encontrar una Máquina de Turing que con un determinado programa simule otra (produzca la misma salida o estado final que la otra) si disponemos de la cadena de símbolos adecuada al comienzo. Esto es, siempre existe una Máquina de Turing con un programa (P1) tal que, para cualquier otra Máquina de Turing con otro programa (P2) y cualquier cadena de símbolos (C2), podemos encontrar una cadena de símbolos (C1) que haga:

P1(C1) = P2(C2)

 

C1 = C2 x Cx

 

Donde C2 es la cadena de símbolos que representa a los datos iniciales sobre los que opera el segundo autómata y Cx es la parte de los datos iniciales sobre los que opera el primer autómata que simulan las reglas del segundo autómata. De tal modo que, si proponemos un esquema básico de reglas para un autómata, podemos interpretar que la cadena de símbolos que hemos llamado datos iniciales no sólo contiene datos sobre los que el autómata debe operar, sino que contiene los pasos o reglas del programa también.

Figura 5.- Simulación de un programa P1 por P2 añadiendo C2. Esquema obtenido de [Fernández, Moreno 1992]

Una Máquina de Turing Particular es el conjunto formado por un autómata finito de estados (Tabla de Decisión) que proporciona un esquema de interacciones básico, y una cadena de símbolos que proporciona la entrada y / o programa (tal y como hemos visto, la cadena inicial puede ser parte del programa). Una Máquina de Turing Universal, por el contrario, es aquella que no dispone de la cadena inicial de símbolos, por lo que está abierta a recibir cualquier entrada (y / o programa) que le proporcionemos.

De lo anterior se puede deducir que toda Máquina de Turing Universal puede ser programada para que opere como una Máquina de Turing Particular determinada.

Limitaciones físicas de la computación

Las Máquinas de Turing no requieren, en principio, una cinta de tamaño infinito sino una cinta infinitamente extensible (no acotada por el tamaño de la entrada). Ambas cosas, aunque equivalentes en determinados casos, no atienden a la misma idea. Cuando se debate la equivalencia lógica entre una computadora física y una Máquina de Turing, el problema no está tanto en que la computadora no posea una memoria infinita, sino en que no posee una memoria infinitamente extensible. Si nuestra computadora precisa más memoria para llevar a cabo una determinada función, podremos adquirir una expansión de memoria y añadírsela. El problema comienza cuando las necesidades de memoria de nuestra computadora crezca más allá de determinado límite. Pero no será éste un problema desde un punto de vista lógico, ya que nuestra computadora posee una memoria infinitamente extensible, sino será un problema desde el punto de vista físico, más concretamente problemas de comunicación entre los dispositivos y problemas de inmensidad.

Todo dispositivo computacional físicamente construido esta sujeto, en su funcionamiento, a las leyes físicas. Por tanto la cantidad de computación potencialmente posible es menos o igual que un límite superior que depende de la masa del sistema, la velocidad de la luz y la constante de Planck. Por supuesto, las capacidades computacionales de las que disponemos hoy día no se acercan ni de lejos a esos límites, pero aunque utilizáramos todos los recursos disponibles en nuestro universo nunca podríamos computar más allá de ese límite. Aunque nos encontramos lejos, algunos problemas ya se han presentado en la práctica.

Además, el tamaño del sistema, en relación con el tamaño de los elementos básicos que lo componen, es crítico en lo que se refiere a la comunicación entre las distintas partes. Por encima de un determinado valor se desincroniza, y haría falta añadir nuevos componentes encargados de volver a sincronizar las comunicaciones. Pero, a su vez, esos componentes deben estar comunicados, por lo que es necesario añadir nuevos elementos para sincronizar las comunicaciones de determinados elementos, y así sucesivamente.

Lo mismo ocurre con las propiedades cuánticas de la materia. Se pueden utilizar, tal y como ha propuesto Conrad [Conrad 1989], procesos cuánticos como elementos computacionales, pero, por otra parte, éstos imponen ciertas restricciones a las capacidades computacionales de los aparatos físicos derivadas del principio de incertidumbre y del problema de la medida en física cuántica. En este marco, una típica discusión es la del coste energético mínimo que implica el procesamiento de un «bit». La discusión se mantiene en los siguientes términos: Mientras que unos autores proponen que los procesos computacionales son intrínsecamente irreversibles siendo el coste energético del procesamiento de un bit igual a kT unidades de energía, otros sostienen que no existe un mínimo energético que se pueda asociar con cada paso lógico, y apoyan esta afirmación mostrando la posibilidad de la computación reversible.

Con respecto a otras limitaciones, como la del tamaño que puede alcanzar un sistema computacional, parece que existe cierto consenso. Se considera que el universo que conocemos tiene del orden de 1080 átomos (y se dice que un sistema de 1080 o más componentes es un sistema inmenso). ¿Qué ocurre si queremos «computar un sistema inmenso» (por ejemplo, construir una lista de los primeros 1080 números naturales? Pues simplemente que no tenemos materia suficiente. Aunque todos los demás problemas no existieran no dispondríamos ni de un átomo para representar cada número.

El problema de parada

Como ya hemos comentado anteriormente, el problema de parada (halting problem) constituye un escollo insalvable para la Máquina de Turing Universal. Recordemos que una Máquina de Turing representa a una función computable, y solamente proporcionará un resultado cuando la máquina se detenga. Mientras la Máquina de Turing está computando una función, los resultados intermedios almacenados en la cinta no son más que pasos previos que pueden no tener nada que ver con el resultado final, por lo que no nos serviría parar abruptamente la Máquina de Turing y ver «hasta dónde ha podido llegar» en el cálculo de una función para la que la máquina no se detiene jamás.

Turing demostró que no existe una Máquina de Turing que nos informe sobre si otra Máquina de Turing se detendrá o no durante su procesamiento, es decir, si nos dará un resultado final. La demostración de este hecho se basó en el carácter formal de los sistemas simbólicos empleados, y su inconsistencia reflejada en proposiciones indecidibles descubiertas a raíz del Teorema de Gödel, así como todas las paradojas derivadas de situaciones de autorreferencia en sistemas formales (las explicadas en «Principia Matemática» de Bertrand Russell, entre otras). Formalmente el problema de parada podría enunciarse de la siguiente manera [Fernández, Moreno 1992]:

«Supongamos que, dada una Máquina de Turing (MT1), existe una cadena de símbolos (S1) que nos informa si otra Máquina de Turing (MT2), con un determinado programa (P2) y unos datos iniciales (D2) se detendrá proporcionando una salida (S1=P1[P2,D2]). Supongamos ahora que aplicamos el programa P1, que determina el comportamiento de la MT1 sobre el mismo programa, pero tomando como datos los propios (P1[P1,D1]). Entonces, para que MT1 pudiera informar sobre si la Máquina de Turing objeto de análisis parará o no, debería existir un programa (P1) que parara cuando un segundo programa (P1), introducido como dato al anterior, no parara. Pero la existencia de este programa es imposible cuando se aplica sobre sí mismo.»

Estas conclusiones fueron desarrolladas durante la tesis doctoral de Turing en la Universidad de Princeton, en estrecha colaboración con Church. A pesar de que en ese trabajo Turing analizaba la lógica matemática profundizando en sistemas de lógica definidos por ordinales, la pregunta que subyacía en dicha tesis se podría formular como ¿Cuál es la consecuencia de suplir un sistema formal con pasos deductivos incomputables? A raíz de esta cuestión, Turing introduce la idea del «oráculo», que podría ser capaz de responder al problema de parada para cualquier Máquina de Turing. Este concepto del «oráculo» fue relacionado tanto por Turing como por Newman [Nagel 1994] como la intuición matemática en la resolución de teoremas, entendida como la capacidad humana de ver el valor de una proposición formal indecidible como las expresadas por Gödel. Turing definió el «oráculo» matemáticamente como una función incomputable, y afirmó que no podíamos avanzar más allá en la naturaleza de este «oráculo», salvo decir que no puede ser una máquina. El punto esencial del «oráculo» es que realiza acciones no mecánicas.

El filósofo B. J. Copeland ha intentado desarrollar esta idea del «oráculo» en trabajos recientes [Copeland, Proudfoot 1999], insinuando la posibilidad de que pueda ser una máquina. Copeland entiende este último término tal y como lo empleaba Turing. La palabra «máquina» fue empleada por Turing para entidades que era sólo parcialmente mecánicas en su operación, y reservaba el término «máquina automática» para aquellas que eran puramente mecánicas.

En 1936, Turing definió una de esas «máquinas» que no eran puramente mecánicas, la «máquina de elecciones» («choice- machine»). En ella se realizan automáticamente una serie de pasos, mientras que otros requieren de la elección de un operador exterior (generalmente humano). Los trabajos de Copeland van por esta línea, pero tratan de definir la idea cuestionable de «un nuevo tipo de máquina», al contrario de lo que hizo Turing, que solamente expresó la propiedad parcialmente mecánica de estas máquinas. Dado que el problema de parada no tiene solución, varios estudios sobre este tema se centran en «problemas de parada limitados», es decir, encontrar Máquinas de Turing que resuelvan el problema de parada para determinados tipos de Máquinas de Turing. Entre estos se encuentra el desarrollado por M. Najtiv [Najtiv 1998], que trata el problema de parada intentando resolver la «conjetura de Collatz», también conocida como el problema 3n+1, secuencias de Ulam o los números de Hallstone. El problema 3n+1 tiene propiedades reminiscentes de sistemas caóticos. Para tratar de resolver este problema, Najtiv emplea lo que él denomina el «Superset Algorithm», mediante el que describe como cualquier Máquina de Turing puede ser reducida a una Máquina Secuencial Generalizada (Generalized Sequential Machine) y analizarse sus propiedades en cuanto al problema de parada mediante funciones elementales estableciendo principios de clase o grupo.

Otro problema que suele utilizarse como paradigma de los problemas de este tipo es el conocido como el «juego del castor laborioso» (busy beaver), bautizado así por Tibor Rado a principios de los años 60. Rado se preguntaba cuántos unos podrían hacérsele imprimir a una Máquina de Turing antes de que se detuviera. Específicamente, si una Máquina de Turing es capaz de adoptar n estados y comienza a trabajar sobre una cinta totalmente ocupada por ceros, ¿cuál es el número máximo de unos que puede imprimir sobre la cinta antes de detenerse? La respuesta se conoce para los casos en los que n = 1, n = 2; n = 3, y n = 4, pero no para n = 5, ni tampoco para valores superiores de n. En 1983 se celebró en Dortmund, Alemania, un concurso para ver quién lograba diseñar el más afanoso «castor» de cinco estados. A lo largo del año que precedió al concurso se compusieron programas destinados a generar Máquinas de Turing «de competición», y se puso a punto el soporte físico necesario. En el curso de esos trabajos se descubrieron buen número de «castores» de extravagantes conductas.

Conclusiones

En el curso de este artículo hemos podido ver cómo la computación en general no es algo tan práctico como pueda parecer en un principio y sus bases se fundamentan en los cimientos -no tan sólidos, como hemos visto- de la lógica y la matemática. Toda esta diatriba lógica ha tenido como objetivo constatar un hecho que me dejó perplejo cuando lo escuché por primera vez: no todos los problemas son computables, y existen muchos problemas fáciles de formular que nunca encontrarán una solución desde nuestras máquinas. Aterrador para un Ingeniero en Informática, aunque fascinante.

Referencias

Cook, Stephen.[1971]. The complexity of theorem-proving procedures. In Conference Record of Third Annual ACM Symposium on Theory of Computing, páginas 151-158.

B.J. Copeland, D. Proudfoot. [1999]. Alan Turing’s Forgotten Ideas in Computer Science. Scientific American April 1999, páginas 77-81.

Dewdney, A. K. [1990]. Aventuras Informáticas, los mundos del ordenador. Editorial Labor: Barcelona.

Edmonds, J. [1965]. Paths, trees, and owers. Canadian Journal of Mathematics 17, páginas. 449-467

Fernández Ostolaza, Julio; Moreno Bergareche, Álvaro [1992]. Vida artificial. EUDEMA, Ediciones de la Universidad Complutense: Madrid

Garciadiego Dantan, Alejando R. [1992]. Bertrand Russell y los orígenes de las “paradojas” de la teoría de conjuntos. Alianza Editorial: Madrid.

Nagel, Ernest; Newman, James R. [1994]. El Teorema de Gödel (2ª edición). Editorial Tecnos: Madrid.

Najtiv, M. [1998]. The Superset Algorithm paper. The Superset Homepage. http://www8.pair.com/mnajtiv/halt/super.txt

Penrose, Roger [1994]. Shadows of the Mind: A Search for the Missing Science of Consciousness. Oxford Universisty Press: Oxford

Rado, Tibor [1962]. On non-computable functions. The Bell System Technical Journal, vol. 41, no. 3, páginas 877-884.