BUD, BUL Y BUM NO SON borbotones electrónicos, explosiones ni sonidos producidos por un pavo atragantado: se trata de lenguajes de computadora, cada uno con su propia finalidad específica. Han sido inventados especialmente para este capítulo, y serán empleados para explicar algunos nuevos sentidos del término “recursividad”: en particular, las nociones de recursividad primitiva y de recursividad generalizada. Estas serán de gran utilidad para el esclarecimiento del mecanismo de la autorreferencia en TNT.

Puede parecer que estamos estableciendo una transición muy abrupta, desde los cerebros y las mentes, a aspectos técnicos de la matemática y de la ciencia de las computadoras. Pese a que, en determinada medida, efectivamente es un salto brusco, tiene su sentido. Ya vimos que en el corazón de la conciencia parece haber un cierto género de autoconciencia; lo que haremos ahora será examinar esta última en el marco de ámbitos más formales, tales como TNT. La brecha entre TNT y la mente es amplia, pero habrá algunas ideas con mayor capacidad inspiradora que tal vez puedan ser recogidas por nuestras reflexiones acerca de la conciencia.

Una de las facetas más asombrosas de la autoconciencia de TNT es que está íntimamente vinculada con la problemática de orden versus el caos dentro de los números naturales. En especial, veremos que un sistema ordenado, dotado de la suficiente complejidad como para poder reflejarse a sí mismo, no puede ser totalmente ordenado: tiene que contener ciertos rasgos extraños y caóticos. Para los lectores que tengan algo de Aquiles, esto será algo difícil de aceptar; pero hay una compensación “mágica”: existe cierto género de orden en el desorden, el cual pasa a ser su propio campo de estudio, bajo el nombre de “teoría recursiva de la función”. Lamentablemente, no podremos hacer mucho más que alusiones a lo fascinante de este tema.

Representabilidad y refrigeradores

Expresiones como “suficientemente complejo”, “suficientemente poderoso”, y otras por el estilo, han aflorado muy a menudo en las páginas precedentes. ¿Qué quieren decir? Podemos retornar a la batalla entre el Cangrejo y la Tortuga, y formular la pregunta: “¿Qué es lo que caracteriza a algo como un fonógrafo?”. El Cangrejo podría aducir que su refrigerador es un fonógrafo “Perfecto”; para demostrarlo, quizá colocase encima de aquél un disco cualquiera, y dijese: “Ya lo ve, lo está ejecutando…”. La Tortuga, si quisiera refutar semejante acto de tipo zen, debería replicar: “No; su refrigerador es de muy baja fidelidad como para ser considerado un fonógrafo: no puede reproducir ninguna clase de sonido (y mucho menos, sonidos autodestructivos)”. La Tortuga puede elaborar un disco que se llame “No puedo ser escuchado mediante el Fonógrafo X” ¡solamente en el caso de que el Fonógrafo X sea efectivamente un fonógrafo! El método de la Tortuga es sumamente capcioso, pues se funda en la fortaleza, y no en la debilidad, del sistema; en consecuencia, ella exige fonógrafos dotados de “fidelidad lo suficientemente alta”.

Lo mismo vale para las versiones formales de la teoría de los números. La razón por la cual TNT es una formalización de N consiste en que sus símbolos funcionan como es debido: es decir, sus teoremas no permanecen en silencio como el refrigerador, sino que permiten escuchar verdades propiamente dichas de N. Por supuesto, también así funcionan los teoremas del sistema mg; ¿debe ser considerado entonces “una formalización de la teoría de los números”, o en realidad se parece más a un refrigerador? Bueno, es algo mejor que un refrigerador, pero no deja de ser bastante débil. El sistema mg no incluye las suficientes verdades nucleares de N como para considerárselo “una teoría de los números”.

¿Cuáles son, pues, tales “verdades nucleares” de N? Son las verdades recursivas primitivas, lo cual significa que involucran sólo cálculos de finalización predictible. Estas verdades nucleares tienen la misma utilidad, para N, que los cuatro primeros postulados de Euclides para la geometría: permiten apostar a ciertos competidores, antes de que comience la carrera, en las pistas de “poder insuficiente”. De aquí en más, el criterio para denominar “suficientemente poderoso” a un sistema será la representabilidad de todas las verdades recursivas primitivas.

El hacha de Gantō en metamatemática

La importancia de la noción anterior es mostrada por el siguiente hecho clave: si se cuenta con una formalización lo suficientemente poderosa de teoría de los números, el método de Gödel, entonces, le será aplicable, y en consecuencia tal sistema será incompleto. Si, en cambio, el sistema no es lo suficientemente poderoso (esto es, no todas las verdades recursivas primitivas son teoremas), el sistema será, entonces, en virtud de tal carencia, incompleto. Tenemos así una nueva formulación de “El hacha de Gantō”, ahora en el campo de la metamatemática: ¡haga lo que haga el sistema, el hacha de Gödel le cortará la cabeza! Adviértase también la perfecta analogía que tiene esto con la contienda alta fidelidad versus baja fidelidad del Contracrostipunctus.

En realidad, resulta que sistemas mucho más débiles son menos vulnerables al método de Gödel; el criterio de que todas las verdades recursivas primitivas deben ser representadas como teoremas es tremendamente rígido. Es algo así como si un ladrón robara nada más que a la gente “suficientemente rica”, y cuyo criterio al efecto fuera el de que la víctima potencial debiera portar, cuanto menos, un millón de dólares en billetes. En el caso de TNT, afortunadamente para nuestra condición de ladrones, el millón contante y sonante está allí, lo cual equivale a decir que contienen, por cierto, todas las verdades recursivas primitivas bajo la forma de teoremas.

Pero antes de sumergirnos en una detallada exposición de las funciones recursivas primitivas y de los predicados, me interesa ligar los temas de este capítulo a los tocados en los capítulos anteriores, a fin de proporcionar una motivación algo más intensa.

El hallazgo del orden mediante la elección del filtro adecuado

Ya vimos, en un momento muy anterior, que los sistemas formales pueden ser bestias díscolas e ingobernables, pues contienen reglas de ampliación y reducción, las cuales encauzan a veces en búsquedas de nunca acabar, en el ámbito de las cadenas. El descubrimiento de la numeración Gödel mostró que toda búsqueda de una cadena dotada de una propiedad tipográfica especial tiene un primo hermano aritmético: una búsqueda isomórfica de un entero dotado de una propiedad aritmética especial, correspondiente a la tipográfica. En consecuencia, la persecución de procedimientos de decisión para los sistemas formales importa la resolución del misterio de las búsquedas impredictiblemente largas. Ahora bien, en el Aria con Variaciones Diversas quizá he concedido demasiada gravitación a las manifestaciones visibles de caos dentro de problemas relativos a enteros. En verdad, hay quienes han conseguido domesticar ejemplares más salvajes de aparente caos que el problema de la “maravillosidad”, descubriendo, a fin de cuentas, que se trataba de bestias sumamente apacibles. La poderosa fe de Aquiles en la regularidad y en la predictibilidad de los números, por consiguiente, es merecedora de algo más de respeto: especialmente, porque refleja la misma fe que caracterizó a casi todos los matemáticos anteriores a la década de los treinta. Con la finalidad de hacer ver por qué el del orden versus caos es un tema tan delicado y sobresaliente, y para vincularlo con cuestiones relativas a la ubicación y a la revelación del significado, me gustaría citar un bello y memorable pasaje de Are Quanta Real?, un diálogo galileano, obra de J. M. Jauch en su último período:

SALVIATI. Supongamos que le presento dos secuencias de números, tales como

7 8 5 3 9 8 1 6 3 3 9 7 4 4 8 3 0 9 6 1 5 6 6 0 8 4…

1, −1/3, +1/5, −1/7, +1/9, −1/11, +1/13, −1/15,…

Si le pregunto, Simplicio, cuál es el número que sigue en la primera secuencia, ¿qué me responde?

SIMPLICIO. No sabría qué decirle. Creo que es una secuencia caprichosa, no ajustada a ninguna ley.

SALVIATI. ¿Y en la segunda secuencia?

SIMPLICIO. Esto es fácil. Tiene que seguir +1/17.

SALVIATI. Correcto. Pero, ¿si le digo que también la primera secuencia obedece a una ley, y que esta ley es, en realidad, idéntica a la que acaba usted de descubrir con respecto a la segunda secuencia?

SIMPLICIO. No lo creo probable.

SALVIATI. Ciertamente es así, empero, puesto que la primera secuencia es, simplemente, el comienzo de la fracción decimal [expansión] de la suma de la segunda. Su valor es π/4.

SIMPLICIO. Usted está lleno de trucos matemáticos así, pero no veo qué relación tienen con la abstracción y la realidad.

SALVIATI. Las relaciones con la abstracción son fáciles de ver. La primera secuencia parece azarosa, a menos que uno haya desarrollado, a través de un proceso de abstracción, cierta clase de filtro al cual le es posible percibir una estructura simple por detrás de la aparente casualidad.

Es exactamente de esta manera que son descubiertas las leyes de la naturaleza. La naturaleza nos pone enfrente de una multitud de fenómenos que nos impresionan principalmente por su arbitrariedad caótica, hasta que seleccionamos determinados hechos significativos y los abstraemos de las circunstancias particulares y nada significativas que los rodean, de modo de llegar a convertirlos en ideas. Solamente así es que pueden exhibir su verdadera estructura en todo su esplendor.

SAGREDO. ¡Es un concepto maravilloso! Propone que, cuando tratemos de comprender la naturaleza, observemos los fenómenos como si fuesen mensajes que deben ser comprendidos. Con la advertencia de que todos los mensajes parecerán casuales hasta que establezcamos un código para leerlos. Este código adopta la forma de una abstracción, esto es, optamos por ignorar ciertas cosas a causa de que no son pertinentes, y en consecuencia seleccionamos en parte el contenido del mensaje mediante una elección libre. Tales señales no significativas constituyen el "ruido de fondo’’ que limita la precisión de nuestro mensaje.

Ahora bien, como el código no es absoluto, puede haber diversos mensajes en la materia prima de los datos, por lo cual, cambiando el código, surgirá un mensaje de significación igualmente profunda desde algo que antes no era sino ruido, y a la inversa: en un nuevo código, un mensaje anterior puede carecer de significación.

Así, un código presupone una libre elección entre aspectos diferentes y complementarios, cada uno de los cuales tienen un idéntico reclamo de realidad, si es que puedo utilizar esta dudosa palabra.

Algunos de esos aspectos pueden sernos completamente desconocidos ahora, pero tal vez se revelen a un observador que aplique un sistema diferente de abstracciones.

Pero dígame, Salviati, ¿cómo podemos entonces sostener que hacemos algún descubrimiento acerca del mundo real objetivo? ¿No será que tan sólo estamos creando cosas de acuerdo a nuestras propias imágenes, y que la realidad está únicamente dentro de nosotros mismos?

SALVIATI. No creo que sea así necesariamente, pero son interrogantes que merecen una reflexión más profunda.^[1]

Jauch habla aquí de mensajes provenientes, no de un “ser consciente”, sino de la naturaleza misma. Las preguntas que planteamos en el Capítulo VI acerca del vínculo entre significación y mensajes pueden ser igualmente planteadas ahora con referencia a los mensajes procedentes de la naturaleza. ¿La naturaleza es caótica o responde a estructuras? Y, ¿qué papel cumple la inteligencia en la determinación de la respuesta que cabe a tal pregunta?

Dejando a un lado la filosofía, sin embargo, podemos considerar el problema de la profunda regularidad existente en una secuencia aparentemente azarosa. ¿La función Q(n) del Capítulo V también podría tener una explicación simple, no recursiva? ¿Todos los problemas, al igual que un huerto, podrán ser mirados desde un ángulo tal que revele su secreto? ¿O hay ciertos problemas, dentro de la teoría de los números, que permanecen en el misterio cualquiera sea el ángulo desde el que los observemos?

Luego de esta introducción, presiento que es hora de ponemos a definir la significación precisa de la expresión “búsqueda impredictiblemente larga”. Lo haremos a través del lenguaje BuD.

Pasos primordiales del lenguaje BuD

Nuestro objetivo serán las búsquedas de números naturales dotados de diversas propiedades. Para hablar de la longitud de cualquier búsqueda, tendremos que definir ciertos pasos primordiales, a partir de los cuales sea organizada toda búsqueda, de modo que la longitud pueda ser medida en función de la cantidad de pasos requeridos. Algunos de los pasos que podemos considerar primordiales son los siguientes:

Bucles y límites superiores

Si probamos formular una verificación para, digamos, la primidad, en función de tales pasos, pronto veremos que nos es necesario incluir una estructura de control; es decir, descripciones del orden en que se deben hacer las cosas cuando bifurcamos para retroceder, a ñn de intentar algo por segunda vez, o cuando saltamos por encima de un conjunto de pasos, cuando nos detenemos, y decisiones de esta clase.

Lo típico de cualquier algoritmo —o sea, de un diseño específico para dirigir la realización de una tarea— es que incluya una combinación de, (1) especificación de las operaciones que han de ser realizadas, y (2) instrucciones de control. Como consecuencia, cuando desarrollemos nuestro lenguaje mediante la enunciación de cálculos predictiblemente extensos, deberemos también incorporar estructuras primordiales de control. En realidad, la garantía de calidad de BuD es su limitado conjunto de estructuras de control. Este impide saltar hacia pasos arbitrariamente elegidos, o repetir sin limitaciones determinados grupos de pasos; en BuD, esencialmente, la única estructura de control es el bucle delimitado: un conjunto de instrucciones que pueden ser ejecutadas una y otra vez, hasta llegar a una cantidad máxima y preestablecida de veces, llamada límite superior, o techo, del bucle. Si el techo es 300, el bucle puede ser ejecutado 0, 7 o 300 veces, pero no 301 veces.

Ahora bien, los valores exactos de todos los límites superiores, dentro de un programa, no necesitan ser fijados numéricamente por el programador: ciertamente, puede que no sean conocidos con anticipación. Por el contrario, cualquier límite superior puede ser determinado mediante cálculos que se realicen antes de que complete su bucle. Por ejemplo, si se quiere calcular el valor de 2^3ⁿ habría dos bucles. Primero se evalúa 3ⁿ, lo cual implica n multiplicaciones. Luego, se eleva 2 a esa potencia, lo cual implica 3ⁿ multiplicaciones. Así, el límite superior del segundo bucle es el resultado del cálculo del primer bucle.

Convenciones de BuD

La capacidad de observar un algoritmo formulado en lenguaje de computadora, y comprender lo que expresa, es algo que constituye una adquisición especial. De todos modos, espero que este algoritmo sea lo suficientemente sencillo como para que tenga sentido sin necesidad de mayor examen. Se ha definido un procedimiento, que tiene un parámetro de entrada, N; su salida es el valor buscado.

Esta definición de procedimientos cuenta con lo que ha sido denominado estructura de bloques, lo cual quiere decir que ciertas porciones de aquél tienen que ser consideradas como si fuesen unidades, o bloques. Todas las instrucciones incluidas en un bloque son ejecutadas como si se tratase de una unidad. Cada bloque tiene un número (el del extremo es el BLOQUE 0), y está delimitado por un COMIENZO y un FIN. En nuestro ejemplo, los BLOQUES 1 y 2 contienen únicamente una instrucción cada uno, pero pronto veremos bloques más extensos. Una instrucción de BUCLE significa siempre que el bloque ubicado inmediatamente debajo ha de ser ejecutado repetidamente. Tal como se aprecia en el ejemplo, los bloques pueden estar incluidos unos dentro de otros.

La estrategia del algoritmo anterior es como ya se describió. Se comienza por tomar una variable auxiliar, llamada CELDA(0); se le incluye inicialmente 1, y luego, en un bucle, se la multiplica repetidamente por 3 exactamente N veces. A continuación, se hace la misma cosa con la CELDA(1): introducirle 1, multiplicarla por 2 exactamente CELDA(0) veces, y ahí cesar. Finalmente, se inscribe como SALIDA el valor de CELDA(1). Éste es el valor que se devuelve al mundo exterior: el único comportamiento visible del procedimiento.

Haremos algunas puntualizaciones acerca de la notación. Digamos, primero, que la flecha orientada a la izquierda —‘←’— significa:

Evaluar la expresión ubicada a su derecha, luego tomar el resultado e inscribir a su izquierda, con ese valor, la CELDA (o SALIDA).

De esta manera, la interpretación de una orden como por ejemplo CELDA(1) ← 3 × CELDA(1) consiste en triplicar el valor almacenado en CELDA(1). Se puede considerar cada CELDA como una palabra separada, dentro de la memoria de una computadora. La única diferencia entre una CELDA y una palabra propiamente dicha es que esta última sólo puede contener enteros dentro de un determinado límite finito, en tanto que nuestra CELDA está habilitada para contener cualquier número natural, por enorme que sea.

Todo procedimiento de BuD a que se apele produce un valor: el valor de la variable llamada SALIDA. En el principio de la ejecución de todo procedimiento se da por supuesto, como opción subsidiaria, que el valor de SALIDA es 0. Así aun cuando el procedimiento no consiga generar ninguna SALIDA, ésta tendrá siempre un valor bien definido.

Instrucciones SI y bifurcación

Veamos ahora otro procedimiento, que nos mostrará algunos rasgos nuevos de BuD, los cuales le aportan mayor generalidad. ¿Cómo hallar el valor de M – N, sabiendo solamente cómo sumar? El truco estriba en sumar diversos números a N, hasta encontrar el que produce M. Pero, ¿qué pasa si M es menor que N? ¿Si resulta que estamos tratando de restarle 5 a 2? En el dominio de los números naturales, no hay respuesta. Sin embargo, querríamos que nuestro procedimiento BuD diese, de todos modos, una respuesta: digamos 0. Sigue, entonces, un procedimiento BuD para la sustracción:

Estamos haciendo uso, en este caso, del aspecto implícito de que SALIDA principia en 0. Si M es menor que N, la sustracción es entonces imposible, por lo cual simplemente brincamos en forma directa al fondo BLOQUE 0, y la respuesta es 0. Éste es el significado de la línea CESAR BLOQUE 0. Pero si M no es menor que N, tenemos que hacer caso omiso de la instrucción CESAR y ejecutar la orden que sigue en la secuencia (aquí, una instrucción de BUCLE). Así es como funcionan siempre las instrucciones SI en BuD.

En consecuencia, insertamos BUCLE 1, identificado de tal modo porque el bloque que nos indica repetirlo es el BLOQUE 1. Estamos tratando de sumar 0 a N, luego 1, 2, etc., hasta que encontremos un número que dé por resultado M. En ese punto, procederemos a INTERRUMPIR el bucle que estamos ejecutando, lo cual significa que brincamos hasta la instrucción inmediatamente siguiente al FIN que marca el fondo del bloque al que pertenece el bucle. En este caso, ese brinco nos lleva exactamente debajo de BLOQUE 1: FIN, es decir, a la última instrucción del algoritmo, y ahí terminamos. Ahora, SALIDA contiene la respuesta correcta.

Adviértase que hay dos instrucciones distintas para brincar hacia adelante: CESAR e INTERRUMPIR. La primera se aplica a los bloques, la segunda a los bucles. CESAR BLOQUEn significa brincar hasta la última línea de BLOQUEn, mientras que INTERRUMPIR BUCLEn significa brincar hasta exactamente debajo de la última línea de BLOQUEn. Esta distinción interesa únicamente cuando se están ejecutando bucles y se desea seguir haciéndolo pero sin el marco del bloque circundante; se dice entonces CESAR, y así sucederá.

Tómese nota también de que aquí el límite superior es precedido por la expresión A LO SUMO, la cual es una advertencia de que el bucle puede ser interrumpido antes de ser alcanzado el límite superior.

Articulación en bloques automática

Explicaremos ahora otros dos aspectos, ambos sumamente importantes, de BuD. El primero consiste en que, una vez definido un procedimiento, se pueda apelar a él dentro de definiciones posteriores de procedimientos. La consecuencia es que, una vez que se ha definido una operación en un procedimiento, es considerada igualmente simple que un paso primordial. Así, BuD imprime articulaciones en bloques automáticas. Esto se podría comparar al modo en que un avezado patinador sobre hielo adquiere nuevos movimientos: no mediante su definición bajo la forma de largas secuencias de acciones musculares primordiales, sino en función de movimientos ya aprendidos, los cuales, a su vez, fueron aprendidos como componentes de movimientos aprendidos con anterioridad, etc., de modo tal que la inclusividad sucesiva, o emblocamiento, puede reconocer muchas capas previas hasta llegar al punto donde es posible encontrar las acciones musculares primordiales. De la misma forma, el repertorio de los programas BuD crece, como el repertorio de las habilidades del patinador, a bucles agigantados.

Verificaciones BuD

El otro aspecto de los mencionados es que ciertos procedimientos de BuD pueden tener SI o NO como salida, en lugar de un valor entero. Tales procedimientos son verificaciones, antes que funciones. Para indicar la diferencia, el nombre de la verificación deberá estar entre signos de interrogación. Además, en una verificación, la opción subsidiaria de SALIDA no es 0, por supuesto, sino NO.

Veamos un ejemplo de estos dos aspectos de BuD, en un algoritmo que verifica su fundamentación de la primidad:

Adviértase que a los dos procedimientos que hay en el interior del algoritmo los he denominado MENOS y RESIDUO. (Se supone que este último ha sido definido con anterioridad; el lector puede encargarse de definirlo). Ahora bien, esta verificación actúa mediante la puesta a prueba, uno por uno, de los factores potenciales de N, principiando en 2 y subiendo hasta el máximo de N – 1. En el caso de que cualquiera de ellos divida exactamente a N (es decir, que dé el residuo 0), entonces brincamos hasta el fondo, y como SALIDA, en este estadio, conserva su opción subsidiaria, la respuesta es NO. Únicamente en el caso de que N no tenga divisores exactos BUCLE 1 se mantendrá en su totalidad; si es así, emergeremos lisa y llanamente en la instrucción SALIDA ← SI, la cual será ejecutada, y con ello el procedimiento habrá llegado a su fin.

Los programas BuD contienen series de procedimientos

Ya hemos visto cómo se definen los procedimientos en BuD; sin embargo, la definición de un procedimiento no es más que una parte de un programa. Un programa consiste en una serie de definiciones de procedimientos (cada una de las cuales apela sólo a los procedimientos definidos previamente), seguida, si se desea, por una o más llamadas a los procedimientos definidos. Así, una muestra de un programa BuD completo la daría la definición del procedimiento DOS A LA TRES A LA, seguido por la apelación, o llamada

Si se cuenta exclusivamente con una serie de definiciones de procedimiento, jamás se conseguirá ejecutar nada: éstas se limitan a esperar algún llamado, con valores numéricos específicos, para ponerse en movimiento. Es algo así como un aparato de picar carne, a la espera de carne para picar, o más bien de una serie de picacarnes reunidos, cada uno de los cuales es surtido por el anterior… Esta imagen tal vez no sea muy exquisita, pero es muy ilustrativa de un rasgo sumamente importante de la elaboración de los programas BuD, al cual llamaremos “programa con llamado menor”, noción que es ilustrada en la figura 72.

Ahora bien, BuD es nuestro lenguaje para la definición de cálculos de finalización predictible. El nombre uniforme de las funciones que son procesables según las normas de BuD es funciones recursivas primitivas, y el de las propiedades que pueden ser detectadas mediante las verificaciones BuD es predicados recursivos primitivos.

Así, la función 2^3ⁿ es una función recursiva primitiva; y el enunciado “n es un número primo” es un predicado recursivo primitivo.

Está claro, intuitivamente, que la propiedad Goldbach es de tipo recursivo primitivo, y que llevar ello a un plano enteramente explícito es tarea aquí de una definición de procedimientos en los marcos de BuD, la cual mostrará cómo verificar su presencia o ausencia:

Como de costumbre, damos por supuesto NO hasta que probemos que SI, y llevamos adelante una búsqueda, basada en la fuerza bruta, entre pares de números a los cuales sumamos hasta obtener N. Si ambos son primos, hacemos cesar el bloque exterior; en caso contrarío, nos limitamos a volver atrás e intentar de nuevo hasta agotar todas las posibilidades.

(Advertencia: El hecho de que la propiedad Goldbach sea recursiva primitiva no convierte en simple la pregunta: “¿Todos los números tienen la propiedad Goldbach?”. ¡Lejos de ello!).

Ejercicios sugeridos

¿Se puede formular un procedimiento BuD similar, a fin de verificar la presencia o ausencia de la propiedad Tortuga (o de la propiedad Aquiles)? Si el lector estima que sí, hágalo. Si estima que no, ¿será porque desconoce los límites superiores, o por la existencia de algún obstáculo fundamental que impida expresar un algoritmo semejante en BuD? ¿Y qué diremos frente a las mismas preguntas, aplicadas a la maravillosidad definida en el Diálogo?

Más abajo incluyo una lista de funciones y propiedades, y el lector deberá dedicarse a determinar si, a su parecer, son recursivas primitivas (programables en BuD) o no. Esto significa que debe analizar cuidadosamente qué clase de operaciones involucrarán los cálculos requeridos y si pueden establecerse techos para todos los bucles abarcados.

PERFECTO [N] = el número “perfecto” N (un número como 28, cuyos divisores, sumados, dan 28: 28 = 1 + 2 + 4 + 7 + 14)

¿TRIVIAL? [A,B,C,N] = SI, si A^N + B^N = C^N es correcto; NO, en caso contrario.

¿PIERRE? [A,B,C] = SI, si A^N + B^N = C^N puede ser satisfecho por un valor de N mayor que 1; NO, en caso contrario.

¿FERMAT? [N] = SI, si A^N + B^N = C^N puede ser satisfecho por valores positivos de A, B, C; NO, en caso contrario.

¿PAR TORTUGA? [M, N] = SI, si tanto M como M + N son primos; NO, en caso contrario.

¿TORTUGA? [N] = SI, si N es la diferencia entre dos primos; NO, en caso contrario.

¿MIU BIEN FORMADA? [N] = SI, si N, considerada como una cadena del sistema MIU, está bien formada; NO, en caso contrario.

¿PAR DE PRUEBA MIU? [M, N] = SI, si M, considerada como una cadena del sistema MIU, es una derivación de N, considerada como una cadena del sistema MIU; NO, en caso contrario.

¿TEOREMA MIU? [N] = SI, si N, considerada como una cadena del sistema MIU, es un teorema; NO, en caso contrario.

¿FALSA? [N] = SI, si N, considerada como una cadena TNT, es un enunciado falso de teoría de los números; NO, en caso contrario.

Los siete últimos ejemplos tienen particular importancia en relación con nuestras exploraciones metamatemáticas venideras, de modo que merecen un atento examen.

Expresabilidad y representabilidad

Pero antes de plantearnos algunas interesantes cuestiones acerca de BuD y de ser conducidos a su pariente, BuL, retornemos a los motivos que tuvimos para presentar a BuD en primer lugar, y conectarlo con TNT. Dije más atrás que la masa crítica para que el método de Gödel pueda aplicarse a un sistema formal se alcanza cuando todas las nociones recursivas primitivas son representares dentro de tal sistema. ¿Qué significa ello, exactamente? En primer término, debemos distinguir entre la noción de representabilidad y la de expresabilidad. Expresar un predicado es un simple problema de traducir lo idiomático a un formalismo estricto; no tiene nada que ver con la teoremidad. Representar un predicado, en cambio, es algo mucho más arduo; esto significa que

Llamo “caso” a la cadena producida cuando todas las variables libres son sustituidas por numerales. Por ejemplo, el predicado m + n = k está representado en el sistema mg, porque cada caso verdadero del predicado es un teorema, y cada caso falso es un no teorema. Así, cualquier suma específica, sea verdadera o falsa, se traduce a cadena decidible del sistema mg. Sin embargo, el sistema mg es incapaz de expresar —mucho menos representar— cualquier otra propiedad de los números naturales. Por consiguiente, sería un candidato muy flojo en una competencia de sistemas que hagan teoría de los números.

Pero TNT, por su parte, tiene la virtud de poder expresar prácticamente cualquier predicado teórico-numérico; por ejemplo, es sencillo formular una cadena TNT que exprese el predicado “b tiene la propiedad Tortuga”. Así pues, desde el punto de vista del poder expresivo, no necesitamos más que TNT.

Sin embargo, la pregunta “¿qué propiedades están representadas en TNT?” equivale precisamente a preguntar: “¿Cuán poderoso sistema axiomático es TNT?”. ¿Todo posible predicado está representado en TNT? Si es así, TNT puede entonces responder a cualquier interrogación de teoría de los números; es completo.

Los predicados recursivos primitivos están representados en TNT

Ahora bien, pese a que la completitud resultará ser una quimera, TNT es completo, al menos con respecto a los predicados recursivos primitivos. En otras palabras, cualquier enunciado de teoría de los números cuya verdad o falsedad pueda ser decidida por una computadora, dentro de un lapso predictible, también es decidible en TNT. O, para hacer una reafirmación final de la misma cosa:

Si es posible formular una verificación BuD para determinada propiedad de los números naturales, entonces esa propiedad está representada en TNT.

¿Hay funciones que no son recursivas primitivas?

Las clases de propiedades que pueden ser detectadas mediante las verificaciones BuD son ampliamente variadas, incluyendo la determinación de si un número es primo o perfecto, si cuenta con la propiedad Goldbach, si es una potencia de 2, etc., etc. No sería absurdo preguntarse si todas las propiedades de los números no podrán ser detectadas mediante el programa BuD adecuado. El hecho de que, hasta el momento actual, no tengamos forma de verificar si un número es maravilloso o no, no tiene por qué preocuparnos demasiado, pues ello puede explicarse simplemente por nuestra ignorancia acerca de la maravillosidad, lo cual podría resolverse a través de indagaciones más profundas que permitieran establecer una fórmula universal que determine el límite superior del bucle pertinente. En tal caso, una verificación BuD de la maravillosidad podría ser formulada de inmediato, y lo mismo puede decirse de la propiedad Tortuga.

Luego, la pregunta, realmente, es: “¿Pueden establecerse siempre límites superiores para la extensión de los cálculos, o bien es inherente al sistema de los números naturales cierto tipo de mescolanza confusa que, en ocasiones, impide predecir la extensión de los cálculos?”. Lo sorprendente es que se trata de lo segundo, e inmediatamente veremos por qué es así. Es la clase de cosa que debe haber sacado de sus cabales a Pitágoras, que fue quien primero demostró que la raíz cuadrada de 2 es irracional. En nuestra exposición, utilizaremos el célebre método diagonal, descubierto por Georg Cantor, el fundador de la teoría de conjuntos.

Buzón D, números índices y Programas Azules

Comenzaremos por imaginamos una extraña noción: un buzón con todos los programas BuD posibles. Obviamente, este buzón —“Buzón D”— es infinito. Necesitamos contar con un subbuzón del Buzón D, obtenido gracias a tres operaciones sucesivas de filtrado. El primer filtro retendrá exclusivamente los programas con llamado menor. De este subbuzón eliminamos luego todas las verificaciones, dejando sólo las funciones. (A propósito: en los programas con llamado menor el último procedimiento de la serie determina si el programa, en su conjunto, es considerado una verificación o una función). El tercer filtro retendrá únicamente las funciones que tienen exactamente un parámetro de entrada. (Con referencia, otra vez, al procedimiento final de la serie). ¿Qué nos queda?

Un buzón completo con todos los programas BuD con llamado menor que calculan funciones de exactamente un parámetro de entrada

Lo que querríamos hacer ahora es asignar un número índice inequívoco a cada Programa Azul. ¿Cómo conseguirlo? El modo más sencillo —es el que emplearemos— consiste en enumerarlos por orden de extensión: el Programa Azul más corto posible será el # 1, el que le siga en brevedad será el # 2, y así sucesivamente. Por supuesto, habrá muchos programas de longitud empatada; para romper el empate, utilizaremos el orden alfabético. Aquí, “orden alfabético” es tomado en sentido amplio, pues incluye todos los signos especiales de BuD, en orden arbitrario, de la manera siguiente:

¡Antes del punto de interrogación invertido, un humilde espacio en blanco! En total, cincuenta y seis signos. Por razones de conveniencia, podemos ubicar todos los Programas Azules de longitud 1 en un Volumen 1, los programas de dos signos en el Volumen 2, etc. No hace falta decir que los primeros volúmenes estarán totalmente vacíos, mientras que los posteriores tendrán muchas, muchísimas entradas (a pesar de que cada volumen podrá contener sólo una cantidad finita). El indiscutible Programa Azul inicial sería éste:

Este picacarne más bien bobo nos devuelve un valor de O, cualquiera que fuere su entrada. Esto sucede en el Volumen 56, puesto que hay allí 56 signos (contados los espacios en blanco, como también los blancos que separan entre sí las líneas sucesivas).

Poco más allá del Volumen 56, los volúmenes alcanzarán notable corpulencia porque, lisa y llanamente, hay millones y millones de formas de combinar símbolos que construyan Programas BuD Azules. Pero no nos preocupemos, pues no estamos intentando la enunciación de este catálogo infinito. Sólo nos interesa que, en forma abstracta, quede bien definido, y que cada Programa Azul, en consecuencia, tenga un único y preciso número índice. Ésta es la idea central.

Designaremos la función calculada por el Programa Azul número k de la siguiente forma:

Aquí, k es el número índice del programa, y N es el único parámetro de entrada. Por ejemplo, el Programa Azul # 12 podría retornar un valor que duplique el de su entrada:

El significado de la ecuación anterior es que el programa identificado a la izquierda produciría el mismo valor que calcularía un ser humano, basándose en las expresiones algebraicas comunes que se han inscripto a la derecha. Para dar otro ejemplo: tal vez el Programa Azul # 5000 calcule el cubo de su parámetro de entrada:

El método diagonal

Bien, ahora “ajustaremos la tuerca”: el método diagonal de Cantor. Tomaremos nuestro catálogo de Programas Azules y lo utilizaremos para definir una nueva función de una variable —Diagazul [N]—, la cual no aparecerá en la lista (porque está impresa en tipo itálico). Empero, Diagazul será indudablemente una función bien definida y calculable de una variante, por lo cual deberemos concluir que existen funciones de este tipo, las cuales, simplemente, no son programables en BuD.

La estrategia seguida es: alimentar a cada picacarne con su propio número índice; luego, sumar 1 a la salida. Para ilustrarlo, busquemos Diagazul [12]. Ya vimos que el Programazul {#12} es la función 2N; en consecuencia, Diagazul [12] debe tener el valor 1 + 2 × 12, o 25. De igual modo, Diagazul [5000] tendría el valor 125.000.000.001, puesto que es el cubo de 5000 más 1. De manera análoga, se puede hallar el Diagazul del desarrollo que se desee en particular.

Lo peculiar de Diagazul [N] es que no está representado en el catálogo de Programas Azules. No puede estarlo, por lo siguiente: para ser un Programa Azul, tendría que tener un número índice: por ejemplo, sería el Programa Azul # X. Esta suposición se expresa mediante la formulación

Pero hay una incoherencia entre las ecuaciones (1) y (2). Se hace evidente en el momento en que tratamos de calcular el valor de Diagazul [X], pues podemos efectuarlo haciendo que N tome el valor de X en cualquiera de las dos ecuaciones. Si sustituimos dentro de la ecuación (1), tenemos:

Ahora bien, Diagazul [X] no puede ser igual a un número y al mismo tiempo el número subsiguiente a ese número. Pero eso es lo que dice la ecuación, de modo que deberemos retroceder y suprimir alguna suposición que dé base a la incoherencia. El único candidato a la supresión es el supuesto expresado por la ecuación (2): el de que la función Diagazul [N] puede ser codificada como un programa BuD Azul. Y ésta es la prueba de que Diagazul tiene su asiento fuera del reino de las funciones recursivas primitivas. De esta manera, hemos cumplido con nuestro propósito de destruir la entrañable pero ingenua noción de Aquiles, según la cual toda función teórico-numérica ha de ser calculable en el marco de un número predecible de pasos.

Hay algunos aspectos sutiles para desarrollar. Se podría analizar éste, por ejemplo: el número de pasos comprendidos por el cálculo de Diagazul [N], para cada valor específico de N, es predictible… pero los diferentes métodos de predicción no pueden ser reunidos en su totalidad dentro de una fórmula genérica que prediga la extensión del cálculo de Diagazul [N]. Ésta es una “trama infinita”, asociada a la noción de la Tortuga de “coincidencias infinitas”, y también a la ω-incompletitud. Pero no rastrearemos en detalle tales asociaciones.

El original argumento diagonal de Cantor

¿Por qué se lo llama argumento diagonal? La terminología proviene de la fundamentación diagonal original de Cantor, sobre la cual se han basado (también nosotros) muchas otras exposiciones. Explicar la argumentación diagonal original de Cantor nos sacaría un poco de tema, pero vale la pena hacerlo. También Cantor se interesó por mostrar que determinado ítem no estaba incluido en cierta lista. Específicamente, lo que Cantor quiso mostrar fue que si se hiciera un “directorio” de números reales inevitablemente dejaría fuera algunos números reales: en consecuencia, la noción de directorio completo de números reales es una contradicción en los términos.

Se debe entender que esto abarca no sólo los directorios de dimensión finita, sino también los de dimensión infinita. Se trata de algo mucho más profundo que enunciar: “el número de los reales es infinito, de modo que, por supuesto, no pueden ser enumerados en un directorio finito”. La esencia de la conclusión de Cantor es que hay (por lo menos) dos tipos distintos de infinito: uno describe cuántas entradas puede haber en un directorio o listado infinitos, y el otro dice cuántos números reales hay (es decir, cuántos puntos hay sobre una línea, o semirrecta): y este último es “más grande”, en el sentido de que los números reales no pueden ser comprimidos dentro de un listado cuya longitud es descripta por el primer tipo de infinito. Veamos cómo la argumentación de Cantor involucra la noción de diagonal, en un sentido literal.

Consideremos nada más que los números reales entre 0 y 1. Supongamos, en beneficio de la argumentación, que se podría aportar una lista infinita donde cada entero positivo N se equipare a un número real r(N), ubicado entre 0 y 1, y donde todos los números reales, entre 0 y 1, aparezcan. Como los números reales están integrados por infinitos decimales, podemos imaginar que el comienzo del listado es así:

Los dígitos alineados en diagonal aparecen en letra destacada: 1, 3, 8, 2, 0. Usaremos ahora esta diagonal de dígitos para formar un número real específico, d, ubicado entre 0 y 1, el cual, como veremos, no está en la lista. Para obtener d, se toman los dígitos diagonales en su orden, y se cambia cada uno de ellos por algún otro dígito. Haciendo preceder esta secuencia de dígitos por un punto decimal, se tiene d. Por cierto, hay muchas formas de cambiar un dígito por otro y, consecuentemente, muchos d diferentes. Supongamos, por ejemplo, que procedemos a sustraer 1 de los dígitos diagonales (ajustándonos a la convención de que 0 menos 1 es nueve). Nuestro número d será, entonces:

¿Qué demuestra una argumentación diagonal?

Ahora aparece la diferencia crucial entre la prueba de Cantor y la nuestra, en cuanto a qué supuesto anterior cabe cuestionar. En la argumentación de Cantor, el supuesto atacado es el de que puede elaborarse una tabla como ésa. En consecuencia, la conclusión garantizada por la construcción de d es que, a fin de cuentas, no puede elaborarse ninguna tabla exhaustiva de números reales… lo cual equivale a decir que el conjunto de los enteros no es lo suficientemente grande como para servir de índice al conjunto de los reales. En cambio, en nuestra prueba, sabemos que el directorio de los programas BuD Azules puede ser elaborado: el conjunto de los enteros es lo suficientemente grande como para servir de índice al conjunto de los programas BuD Azules. Entonces, debemos retroceder y anular alguna idea más cuestionable, de entre las que hayamos utilizado. Y esa idea es la de que Diagazul [N] puede ser calculada por algún programa de BuD. He aquí una sutil diferencia en el empleo del método diagonal.

Esto puede hacerse más claro si lo aplicamos a la ya mencionada “Lista Completa de los Grandes Matemáticos”, vista en el Diálogo: será un ejemplo más concreto. La diagonal dice allí “Dboups”; si efectuamos la sustracción indicada, obtendremos “Cantor”.^† Dos conclusiones son posibles: si se tiene la convicción férrea de que la lista es completa, la conclusión es que Cantor no es un Gran Matemático, pues su nombre difiere de todos los incluidos en la lista; por el contrario, si se tiene la convicción férrea de que Cantor es un Gran Matemático, ¡se debe concluir que la “Lista Completa de los Grandes Matemáticos” es incompleta, porque el nombre de Cantor no figura en ella! (¡Ay de aquellos que estén férreamente convencidos de ambas cosas!). El primer caso corresponde a nuestra demostración de que Diagazul [N] no es recursiva primitiva; el segundo, a la demostración de Cantor de que la lista de los reales es incompleta.

La demostración de Cantor emplea una diagonal en el sentido literal de la palabra. Otras demostraciones “diagonales” están basadas en una noción más genérica, abstraída del sentido geométrico del término. La esencia del método diagonal reside en el hecho de que usa un entero de dos maneras diferentes, o bien, podría decirse, en dos diferentes niveles, y que, gracias a ello, puede construirse un ítem que está fuera de cierta lista predeterminada. En una oportunidad, el entero sirve como índice vertical; en la otra, como índice horizontal. En la explicación de Cantor esto se ve muy claro. En lo que se refiere a la función Diagazul [N], ésta involucra la utilización de un entero en dos niveles diferentes: primero, como número índice de un Programa Azul; segundo, como parámetro de entrada.

La capciosa repetibilidad de la argumentación diagonal

Al principio, la argumentación de Cantor puede parecer no del todo convincente. ¿No hay alguna forma de refutarla? Quizá continuando el número diagonalmente construido d podría obtenerse una lista exhaustiva. Si se pone a prueba tal idea, se verá que no es de ninguna utilidad extender el número d, pues ni bien se le asigna un lugar específico en la tabla el método diagonal pasa a ser aplicable a la nueva tabla, con el resultado de la construcción de un nuevo número d’, ausente de la nueva tabla. Por más veces que se repita la operación de construir un número mediante el método diagonal, y de continuarlo para elaborar una tabla “más completa”, siempre se morderá el ineludible anzuelo del método de Cantor. Se podría, inclusive, tratar de confeccionar una tabla de reales que trate de adelantarse al método diagonal de Cantor, y de ser más lista, de alguna manera, que todos los trucos de éste, incluida su insidiosa repetibilidad. Sería un ejercicio interesante, pero si se lo aborda, se verá que por muchos giros y piruetas que se describan para escapar al “anzuelo” de Cantor, éste terminará pescando su presa. Se puede decir que cualquier autoproclamada “tabla de todos los reales” es cogida en sus propias redes.

La repetibilidad del método diagonal de Cantor es similar a la repetibilidad del diabólico método de la Tortuga, destinado a destruir, uno a uno, todos los fonógrafos del Cangrejo, en la medida en que éstos iban teniendo cada vez más alta fidelidad e iban siendo —por lo menos, eso esperaba el Cangrejo— cada vez más “Perfectos”. Este método implica la obtención, para cada fonógrafo, de un sonido específico que ese fonógrafo no puede reproducir. No es una coincidencia que el truco de Cantor y el truco de la Tortuga compartan esta curiosa repetibilidad; ciertamente, el Contracrostipunctus podría muy bien haber sido denominado también “Cantorcrostipunctus”. Por otra parte, tal como la Tortuga se lo insinúa sutilmente al inocente Aquiles, los acontecimientos del Contracrostipunctus son una paráfrasis del desarrollo seguido por Gödel para demostrar su Teorema de la Incompletitud; se sigue de ello que el desarrollo de Gödel es sumamente semejante a una construcción diagonal. Esto se hará del todo manifiesto en los dos siguientes capítulos.

De BuD a BuL

Hemos ya definido la clase de las funciones recursivas primitivas y de las propiedades recursivas primitivas de los números naturales, por medio de programas formulados en lengua BuD. Hemos mostrado, también, que BuD no captura todas las funciones de los números naturales que podemos definir mediante palabras. Inclusive, hemos construido también una función “imBuDable”, Diagazul [N], a través del método diagonal de Cantor. ¿Qué es lo que pasa en BuD, que Diagazul es irrepresentable en él? ¿Cómo se podría mejorar BuD para que Diagazul sea representable?

El rasgo distintivo de BuD es la limitación de sus bucles. ¿Qué ocurre si abandonamos ese requerimiento con respecto a los bucles, e inventamos un segundo lenguaje, llamado “BuL” (‘L’ por “libre”)? BuL será idéntico a BuD excepto en un aspecto: podemos tener bucles sin techo al mismo tiempo que bucles con techo (pese a que la única razón por la cual se incluiría un techo, al formular una instrucción de bucle en BuL, sería la persecución de elegancia). Estos nuevos bucles serán denominados BUCLES MU, siguiendo la convención de la lógica matemática, donde las búsquedas “libres” (búsquedas sin límites) son indicadas por un símbolo llamado “operador n” (operador mu). Así, las instrucciones de bucle en BuL pueden ser como ésta:

Esta característica nos permitirá formular verificaciones en BuL de propiedades tales como la maravillosidad o la propiedad Tortuga: verificaciones que no tenemos cómo programar en BuD a causa de la carencia potencial de límites definidos por parte de las búsquedas abarcadas. Dejaré que los lectores interesados formulen una verificación BuL de la maravillosidad, dentro del siguiente marco:

La paradoja del caso 3 es que SALIDA tiene siempre el valor NO, pero es siempre inaccesible porque el programa sigue girando. Esta enojosa alternativa tercera es el precio que nos cuesta el derecho de formular bucles libres. En todos los programas BuL que incorporen la opción BUCLE MU, siempre existirá la posibilidad teórica de la inacababilidad. Por supuesto, habrá muchos programas BuL con terminación efectiva, cualquiera que sea el valor de entrada. Por ejemplo, como ya dije, muchas personas que han estudiado la maravillosidad presumen que un programa BuL del tipo sugerido más atrás siempre terminará, y además con la respuesta SI en todos los casos.

Programas BuL con finalización y sin finalización

Sería muy conveniente poder separar los procedimientos BuL en dos clases: finalizables y no finalizables. Un finalizable terminará por de temerse, cualquiera que fuere su entrada, a pesar de la “MUidad” de sus bucles. Un no finalizable seguirá marchando por siempre, para cuando menos una opción de entrada. Si estuviéramos en condiciones, siempre, de indicar a qué clase pertenece cada programa BuL, mediante alguna suerte de complicado análisis, se producirían ciertas repercusiones notables (según veremos a la brevedad). Obviamente, la operación de determinación de clase tendría que ser, por su parte, una operación finalizable; de lo contrario, nada habríamos ganado…

El recurso de Turing

Nos surge la idea de que podríamos encargar el citado análisis a un procedimiento BuD. ¡Pero los procedimientos BuD admiten exclusivamente entradas numéricas, no programas! Aun así, podríamos eludir esta restricción… ¡codificando programas en números! Este astuto ardid no es más que otra de las tantas manifestaciones de la numeración Gödel. Asignemos a los cincuenta y siete signos del alfabeto BuL los “codones” 901, 902,… 956, respectivamente. De modo que ahora, todo programa BuL cuenta con un muy extenso número Gödel. Por ejemplo, la función BuD más breve (que también es un programa BuL con terminación) era la siguiente:

Ahora bien, nuestro proyecto consistiría en formular una verificación BuD denominada ¿FINALIZABLE?, la cual diga SI cuando su número de entrada codifica un programa BuL con terminación, y NO en caso contrario. De esta forma, podríamos transferirle la tarea a una máquina y, con suerte, distinguir entre finalizables y no finalizables. Sin embargo, una ingeniosa argumentación aportada por Alan Turing muestra que ningún programa BuD puede efectuar tal distinción de modo infalible. Su invención es realmente muy similar a la de Gödel, y en consecuencia se vincula muy estrechamente con la invención diagonal de Cantor. No lo desarrollaremos ahora; bastará con decir que su idea básica es alimentar al verificador de terminación con su propio número Gödel. Pero ello no es tan simple, pues se asemeja al intento de citar una oración entera dentro de sí misma; se tiene que citar la cita, y así siguiendo, lo cual pareciera conducir a una regresión infinita. No obstante, Turing descubrió un expediente para alimentar un programa con su propio número de Gödel. En el capítulo siguiente presentaremos una solución del mismo problema, en un contexto distinto. En este capítulo tomaremos una ruta diferente para arribar a esa meta, la cual consiste en demostrar que un verificador de terminación es imposible. A los lectores que deseen conocer una presentación simple y precisa del enfoque de Turing, les recomiendo el artículo de Hoare y Allison mencionado en la Bibliografía.

Un verificador de terminación sería algo mágico

Antes de destruir la noción, diremos escuetamente por qué el hecho de contar con un verificador de terminación sería una cosa notable. En un sentido, seria como disponer de una varita mágica que ¡BuL! fuera capaz de resolver todos los problemas de teoría de los números, de un golpe. Supongamos, por ejemplo, que queremos saber si la Variación Goldbach es una conjetura verdadera o no. Es decir, ¿todos los números tienen la propiedad Tortuga? Comenzaríamos por formular una verificación BuL llamada ¿TORTUGA?, la cual determine si su entrada tiene la propiedad Tortuga. Ahora bien, el defecto de este procedimiento —consistente en que no termina, si la propiedad Tortuga está ausente— ¡se transforma aquí en una virtud! Procedemos a procesar el verificador de terminación para el procedimiento ¿TORTUGA? Si dice SI, ello significa que ¿TORTUGA? finaliza, para todos los valores de su entrada: en otras palabras, todos los números tienen la propiedad Tortuga. Si dice NO, entonces sabemos que existe un número que tiene la propiedad Aquiles. La paradoja reside en que en ningún momento hicimos uso efectivo del programa ¿TORTUGA?: ¡Sólo estábamos inspeccionando!

Esta idea de resolver cualquier problema de teoría de los números codificándolo como programa, y luego aplicándole un verificador de terminación, no difiere de la idea de verificar la genuinidad de un kōan codificándolo en un cordón plegado, pasando luego a verificar si el cordón tiene naturaleza de Buda, en lugar de seguir adelante con el primer propósito. Como sugirió Aquiles, tal vez la información buscada está más cerca de la superficie en una representación que en otra.

Buzón L, números índices y Programas Verdes

Bueno, ya basta de quimeras. ¿Cómo podemos probar que el verificador de terminación es imposible? Nuestra fundamentación de la imposibilidad tiene como eje el intento de aplicar el argumento diagonal a BuL, tal como lo hicimos con BuD. Veremos que hay ciertas sutiles y básicas diferencias entre ambos casos.

Igual que con BuD, imaginemos el buzón con todos los programas BuL. Lo llamaremos “Buzón L”. Luego, realizamos las mismas tres operaciones de filtrado en Buzón L, al final de las cuales, tenemos:

Un buzón completo con todos los programas BuL con llamado menor que calculan funciones de exactamente un parámetro de entrada.

Llamaremos, a estos especiales programas BuL, Programas Verdes (ya que pueden marchar por siempre).

Así como asignamos números índices a todos los Programas Azules, podemos asignar números índices a los Programas Verdes, a través de su distribución en un catálogo, cada uno de cuyos volúmenes contendrá todos los Programas Verdes de determinada extensión, ordenados con criterio alfabético.

Hasta aquí, el traslado de BuD a BuL ha sido directo; veremos ahora si también podemos trasladar la última parte: el truco diagonal. ¿Qué ocurre si tratamos de definir una función diagonal?

Súbitamente, aparece un obstáculo: esta función Diagoverde [N] no puede tener un valor de salida bien definido para todos los valores N de entrada. Esto se debe, simplemente, a que no hemos eliminado, en el filtrado, los programas no finalizables de “Buzón L”, y por consiguiente no tenemos ninguna garantía de poder calcular Diagoverde [N] para todos los valores de N. En ocasiones, podemos iniciar cálculos que no van a terminar nunca. Y el argumento diagonal no puede ser aplicado en este caso, pues depende de que la función diagonal tenga un valor para todas las entradas posibles.

El verificador de terminación nos brinda Programas Rojos

Para resolver esto, deberíamos hacer uso de un verificador de terminación, si es que existe alguno. De modo que, de manera deliberada, introduciremos el supuesto cuestionable de que existe un verificador, y lo haremos servir como cuarto filtro. Atacamos pues la lista de los Programas Verdes, eliminando uno por uno todos los no finalizables, para quedarnos por último con:

Un buzón completo de todos los programas BuL con llamado menor que calculan funciones de exactamente un parámetro de entrada, y que terminen para todos los valores de su entrada.

Llamaremos, a estos especiales programas BuL, Programas Rojos (ya que todos ellos deben detenerse). Ahora sí se aplicará la argumentación diagonal. Definimos

y, en exacta simetría con Diagazul, estamos obligados a concluir que Diagorroja [N] es una función bien definida y calculable de una variable que no está en el catálogo de los Programas Rojos, y por consiguiente ni siquiera es calculable en el poderoso lenguaje BuL. ¿Será hora de llegarnos hasta BuM?

BuM…

Sí, pero ¿qué es BuM? Si BuL es BuD liberado, entonces BuM tendrá que ser BuL liberado. ¿Pero cómo es posible duplicar aquella misma liberación? ¿Cómo elaborar un lenguaje cuyo poder supere al de BuL? En Diagorroja, hemos descubierto una función cuyos valores los seres humanos sabemos calcular —el método para hacerlo ha sido descripto diplomáticamente, en forma explícita—, pero que, aparentemente, no puede ser programada en lenguaje BuL. Se trata de un dilema grave, porque nadie ha descubierto jamás un lenguaje de computadora más poderoso que BuL.

Ha sido efectuada una cuidadosa investigación sobre el poder de los lenguajes de computadora. No ha sido necesario que la realizáramos nosotros mismos; basta con que se diga que hay una vasta clase de lenguajes de computadora que, según se puede demostrar, tiene exactamente el mismo poder expresivo que BuL, en este sentido: cualquier cálculo que pueda ser programado en cualquiera de los lenguajes puede ser programado en todos ellos. Lo curioso es que prácticamente todo ensayo sensato de diseño de un lenguaje de computadora termina por crear un miembro de esa clase, es decir, un lenguaje de poder equivalente al de BuL. Lo que requiere cierto esfuerzo es inventar un lenguaje de computadora, razonablemente interesante, el cual sea más débil que los de dicha clase. BuD es, por supuesto, un ejemplo de lenguaje más débil, pero es la excepción antes que la regla. La cuestión es que hay determinadas formas extremadamente comunes de emprender la invención de lenguajes algorítmicos: personas diferentes, siguiendo caminos independientes, por lo común terminan produciendo lenguajes equivalentes, distintos entre sí por razones de estilo, únicamente, y no de poder.

… es un mito

De hecho, se acepta ampliamente que no puede haber lenguaje más poderoso para describir cálculos que el género de lenguaje equivalente a BuL. Esta hipótesis fue formulada en la década de los treinta por dos personas, independientemente una de otra: Alan Turing —acerca de quien hablaremos más adelante— y Alonzo Church, lógico eminente de nuestro siglo. Es conocida como la Tesis Church-Turing. Si aceptamos la Tesis CT, debemos concluir que “BuM” es un mito: no hay restricciones para suprimir en BuL, ni formas de incrementar su poder mediante la “emancipación”, como se hizo con BuD.

Esto nos lleva a la incómoda situación de afirmar que la gente puede calcular Diagorroja [N] para cualquier valor de N, pero que no hay medio de programar una computadora para que haga lo mismo: si, de alguna manera, esto último pudiera conseguirse, se podría hacerlo a través de BuL… pero, por motivos de construcción, no podría hacerse a través de BuL. Esta conclusión es tan singular que debería llevarnos a investigar muy esmeradamente los pilares sobre los cuales se asienta. Y uno de éstos, como se recordará, en nuestro supuesto cuestionable de que hay un procedimiento de decisión capaz de discriminar entre programas BuL finalizables y no finalizables. La noción de semejante procedimiento de decisión ya merecía sospechas cuando vimos que su existencia permitiría resolver, de una manera uniforme, todos los problemas de teoría de los números. Ahora tenemos doble fundamento para creer que todo verificador de terminación es un mito: que no hay forma de poner los programas BuL en una máquina centrifugadora que separe los finalizables de los no finalizables.

Los escépticos pueden sostener que esto no es una demostración rigurosa de que tal verificación de finalización no existe. Se trataría de una objeción válida; sin embargo, el enfoque de Turing prueba con mayor rigor que no puede formularse ningún programa de computadora en un lenguaje de la clase BuL, que sea capaz de viabilizar una verificación de finalización de todos los programas BuL.

La Tesis Church-Turing

Volvamos por un instante a la Tesis Church-Turing. Nos dedicaremos a ella —y a variaciones sobre ella, y con gran detalle— en el Capítulo XVII. Por ahora bastará con plantearla a través de unas pocas versiones, y postergar la discusión de sus méritos y alcances hasta entonces. He aquí, pues, tres formas relacionadas de plantear la Tesis-CT:

Terminología: recursivo general y parcial

En este capítulo, hemos hecho un estudio bastante extenso de algunas nociones de teoría de los números y sus relaciones con la teoría de las funciones computables. Éste es un campo amplio y floreciente, una combinación intrigante de ciencia de las computadoras y matemática moderna. No podemos cerrar este capítulo sin referirnos a la terminología habitualmente aplicada a las nociones que hemos estado manejando.

Como ya dijimos, “computable a través de BuD” es sinónimo de ‘recursivo primitivo”. Por su parte, las funciones computables a través de BuL pueden separarse en dos ámbitos: (1) el de las computables mediante programas BuL que finalizan: de éstas se dice que son recursivas generales; (2) el de las computables únicamente mediante programas BuL que no finalizan: de éstas se dice que son recursivas parciales. (Lo mismo vale para los predicados). Frecuentemente, se habla de “recursivo” cuando se quiere significar “recursivo general”.

El poder de TNT

Es interesante señalar que TNT es tan poderoso, que no sólo están representados en él todos los predicados recursivos primitivos, sino además todos los predicados recursivos generales. No demostraremos estos hechos, porque tal tipo de demostraciones no está comprendido en nuestro objetivo, el cual consiste en mostrar que TNT es incompleto. Si TNT no pudiera representar ciertos predicados primitivos o generales, sería incompleto de una manera carente de interés; suponemos entonces que sí puede, para mostrar luego que es incompleto de una manera interesante.

r(1):	,1 4 1 5 9 2 6 5 3 . . . . . . .
r(2):	,3 3 3 3 3 3 3 3 3 . . . . . . .
r(3):	,7 1 8 2 8 1 8 2 8 . . . . . . .
r(4):	,4 1 4 2 1 3 5 6 2 . . . . . . .
r(5):	,5 0 0 0 0 0 0 0 0 . . . . . . .

CAPÍTULO XIII

Autoconciencia y caos