(307) Grandes números (II)

Aviso a navegantes. Conviene prevenir al lector de que el número de palabras en este artículo es así mismo un gran número (eso tras eliminar un apartado de 500 palabras), por lo que es mejor leérselo de dos sentadas en vez de una sola. Aun así, no debe desanimarse el lector, ya que, por suerte, este artículo es tan largo como interesante y embaucador (esperemos).

En la anterior entrada (hace ya un tiempecillo) sobre Grandes números alcanzamos números de tamaño “razonable”, para cierta definición de razonable (que consistiría en que no fue necesario introducir notación especial para expresarlos, nos bastó con una pequeña torre de exponenciales en el peor de los casos). Pero claro, las matemáticas tienen mucho más que ofrecer que una mera torre de exponenciales: durante las siguientes entradas, exploraremos números inmensamente más grandes, de magnitud inimaginable (y para los que sí necesitaremos introducir nueva notación, lo cual siempre inspira respeto, pues indica que nos estamos metiendo en asuntos serios). Siguiendo la mecánica del primer artículo, nos centraremos en números surgidos de la investigación en Matemáticas, pero cuando eventualmente agotemos estos, pasaremos a tratar números creados explícitamente para ser Grandes (con G mayúscula), cuyas construcciones son ejercicios de abstracción y recurrencia que sin duda sorprenderán al lector.

Y tras haber prometido que íbamos a tratar números, debemos confesar que esta segunda entrada no tratará sobre un número, sino sobre una función de crecimiento extraordinariamente rápido, la función de Ackermann (para el propósito de esta serie de los Grandes Números, es evidente que también presentan interés esta clase de funciones).

Esta función φ:N^3->N (lenguaje intimidante que nos gusta emplear a los matemáticos para decir que toma tres números naturales y devuelve uno) se debe a Wilhelm Ackermann, matemático alemán de principios de siglo XX especializado en Lógica matemática. Se define de manera recursiva, es decir, definiendo ciertos valores de la función a partir de los anteriores:

La anterior definición fue la original, pero cuando se habla de la función de Ackermann, es más común estar refiriéndose a la siguiente variante, debida a Rózsa Péter y Raphael M. Robinson:

También en ocasiones se define la función de Ackermann de una sola variable Ack(n)=A(n,n). Durante el resto del artículo nos centraremos en la versión de dos variables, que es la más conocida.

Invitamos al lector a que se detenga un momento a observar la forma de A(m,n). Esta definición, al menos a primera vista, no revela ninguna propiedad especial. ¿Por qué se dice que esta función crece tan rápido? ¿Cómo de rápido crece? Pues bien, un ejercicio instructivo sería, antes de continuar, que el lector escribiera sobre un trozo de papel una función concreta que considera de rápido crecimiento (aquellas cuya gráfica puede ser aproximada por una recta horizontal que se endereza casi instantáneamente a lo que parece una asíntota vertical)...

Gráfica de f(x)=e^(x^x)

¿Es la función elegida una composición finita de funciones como la suma, el producto, la exponencial, el factorial, etc.? Entonces el lector ha perdido: se puede demostrar que para valores de n suficientemente grandes (y seguramente más bien pequeños) la función de Ackermann alcanzará y superará a esa clase de funciones.  No importa el entusiasmo con el que pongamos y compongamos factoriales o exponenciales, la función de Ackermann siempre ganará. Ni siquiera empleando una función más elaborada como f(n)=n^…(n veces)…^n (que veremos más adelante que recibe el nombre de tetración o exponenciación iterada) podríamos hacer frente a la función de Ackermann.

 

Puesto que la afirmación anterior es algo ambigua y poco precisa, como buenos matemáticos, nos corresponde formalizarla adecuadamente (hasta cierto punto, ya que no queremos que el lector huya ante la prospectiva de una clase de matemáticas camuflada de artículo de divulgación). Para ello, definiremos (de manera muy informal) ciertas nociones de Teoría de la computabilidad, concretamente los conceptos de función computable y función recursiva primitiva. Para quienes no queden satisfechos con la breve y superficial explicación que proporcionaremos en este artículo, y quiera conocer el formalismo matemático detrás de estos conceptos, recomendamos que eche un vistazo al siguiente enlace (notas de la asignatura “Teoría Elemental de la Computación” de la Universidad de Maryland).

Comenzaremos examinando uno de los problemas clásicos de Teoría de la computabilidad: formalizar el concepto de función computable. Como primera aproximación intuitiva, diremos que una función computable es una función que podemos calcular sus valores. ¡Pero no hemos definido “calcular”, y es pecado matemático mortal utilizar términos que no se han definido! Nuestra tarea es pues darle al término anterior un significado preciso. Pare ello, la pregunta clave es: ¿qué es exactamente lo que está realizando los cálculos?

Máquina diferencial de Babbage, expuesta en el Museo de la Ciencia de Londres.

La respuesta a dicha pregunta es la máquina de Turing, que será siempre nuestra herramienta (conceptual) de cálculo. Esta máquina imaginaria juega un papel central en Teoría de la computación, por lo que nos entristece no darle un tratamiento adecuado (aunque siempre nos quedamos con la conciencia tranquila al poner el link a Wikipedia). Nos limitaremos a decir que una máquina de Turing es el modelo matemático simplificado de un ordenador ideal que ejecuta instrucciones y escribe datos, ambas tareas sobre una única cinta. Se puede probar que este modelo es en cierto sentido equivalente en capacidades a los ordenadores actuales. Por supuesto, en este modelo nunca se nos acabará la memoria para almacenar un número (esto puede causar problemas), ni tendremos fallos de hardware provocados por rayos cósmicos, ni será detenido por la muerte térmica del universo (que en otras condiciones sería un ligero inconveniente para los largos cálculos a los que someteremos nuestra máquina imaginaria).

Concepción artística de una máquina de Turing.

Dicho esto, ahora nos podemos poner manos a la obra: hablando de modo informal, se dice que una función f:N^k->N es μ-recursiva o computable si existe un algoritmo que, a partir de unas funciones y operadores elementales (que vienen listadas en el artículo en Wikipedia), devuelva el valor de la función en un número finito de pasos.

Además, existe otra noción de computabilidad más débil, la recursión primitiva. Si quitamos una de las operaciones básicas, el operador μ, obtenemos la clase de las funciones recursivas primitivas. El operador μ permitía obtener el menor número natural con una propiedad dada, y al quitarlo, en cierto sentido, “perdemos potencia”. La siguiente analogía deja más claro lo que perdemos.

En términos de programación, las funciones recursivas primitivas solo pueden utilizar  bucles for (que itera un número determinado de veces) mientras que, por otra parte, las funciones μ-recursivas también pueden utilizar bucles while (que iteran hasta que se cumple una condición). Por supuesto, se entiende que no hacemos “trampas” (no utilizamos recursión, sentencias goto, ni nada por el estilo).

Antes de continuar, debemos insistir en que estas nociones de computabilidad y de recursión primitiva son informales (como todo el artículo, y ya es largo aun así), y dejamos al lector interesado en informarse más a fondo una gran lista de enlaces interesantes.

Una vez que ha quedado de nuevo tranquila la conciencia del redactor, continuemos. Como hemos dado a entender, dadas ambas definiciones, y al contrario de lo que pudiera indicarnos la intuición (y de lo que se pensaba a principios de siglo XX), existen funciones computables que no son recursivas primitivas. Es decir, existen funciones que pueden ser  programadas utilizando bucles while, pero no solamente con bucles for. Y es aquí donde (por fin) entra nuestra función: la función de Ackermann fue la primera función computable que se demostró  que no era recursiva primitiva (y por si una demostración no fuera suficiente, incluimos otras dos más:  la demostración original, publicada de 1928, y una demostración comprobada por ordenador, bastante más reciente). Esto demuestra que la clase de funciones recursivas primitivas es menor que (está contenida estrictamente en) la clase de funciones computables. Por si al lector le interesan otras demostraciones más elegantes de la contención, dejamos un enlace a este argumento diagonal.

De todas las demostraciones anteriores, nos interesa la original. Y, seamos sinceros, el lector seguramente no tenga tiempo ni ganas para leer el viejo artículo en alemán. Así que, ¿cuál es la idea de la demostración? Pues curiosamente, el truco consiste en probar que la función de Ackermann crece de manera más rápida que cualquier función recursiva primitiva, sea n+1, 42*n^2, ((n^2^n^3^n)!)!, o la función f f(n)=n^…(n veces)…^n (es sencillo comprobar que todas estas se pueden implementar utilizando solamente bucles for, es decir, son recursivas primitivas).  Y para nosotros, que nos interesan las funciones que crecen rápido,  la función de Ackermann ha pasado de ser una mera curiosidad a tener toda nuestra atención.

Antes de que nos pongamos a admirar la velocidad de crecimiento de la función de Ackermann, debemos destacar que, además de cautivar la imaginación de los cazadores de Grandes Números y de ser el ejemplo canónico de función computable pero no recursiva primitiva, esta función tiene otros muchos usos. Sin ir más lejos, sirve para tomarles el pelo a los alumnos de primer curso de Matemáticas: en la llamada “prueba inicial de nivel” (que es un examen de broma que realizan los alumnos de tercero a los que llegan a primero), uno de los problemas planteado fue calcular A(4,3). Esta pregunta fue responsable de la pérdida de grandes extensiones de papel ocupado por amplios e inacabados desarrollos de la función de Ackermann.  Pero todos estos esfuerzos fueron en vano. Pese a su diligencia, estos nuevos alumnos estaban abocados al fracaso desde el principio, pues no existe papel (ni átomos) en el universo como para escribir siquiera el número de dígitos de A(4,3), y ya ni hablemos del número en sí. 

Sin embargo, con algo de astucia (más bien mucha), el problema puede ser resuelto. De hecho, fue el Problema 6 de la Vigesimosegunda Olimpiada Internacional de Matemáticas (el Problema 6 es tradicionalmente el problema más difícil de la ya durísima prueba en la que compiten los jóvenes talentos matemáticos de todos el mundo, por lo que no deben desanimarse los alumnos de primer año que no dieron con la “idea feliz”). En dicho problema, se pidió calcular A(4,1981) (1981 fue el año en que se celebró la competición, pero aumentar el tamaño del segundo argumento no afecta  a la dificultad de la cuestión). Dejamos el problema en el aire, quizás el lector desee hacer un intento, pero le advertimos que hacia el final del artículo, cuando escribamos la forma general de la función de Ackermann, se dará indirectamente la clave de la solución. Si el lector abandona el artículo para enfrentarse al problema, le rogamos que no olvide volver después, que así cuanta doble en el contador de visitas.

Cada problema más trivial que el anterior...

Como último ejemplo más relacionado con la vida real, la función de Ackermann también  rendimiento asintótico de ciertos algoritmos. El rendimiento asintótico de un algoritmo mide (de manera informal) como varía el tiempo de cálculo frente a la magnitud de la entrada. En el artículo enlazado se demuestra que aparece una especie de función inversa de una versión de la función de Ackermann en la expresión de lo que podría llamarse cota inferior del rendimiento asintótico de cierta clase de algoritmos de búsqueda en un tipo determinado de árboles en función de su tamaño y el número de comparaciones. Si el lector no entiende la frase anterior y/o piensa que es vaga, le tranquilizará saber que ha sido escrita así a propósito (y quizás con una gota de maldad), ya que el redactor de este artículo lo ha intentado y es incapaz de explicar de forma precisa el abstract del artículo sin multiplicar el tamaño de este otro artículo. El lector interesado siempre puede leérselo por su cuenta, lectura “ligerita”. Para nosotros, resulta curiosa la aparición de la “inversa” de nuestra querida función. Debido al rápido crecimiento de la función de Ackermann, su inversa es una función de crecimiento muy lento, tan lento que para cualquier entrada razonable su valor es menor que 4, por lo que realmente no tiene demasiada importancia en la expresión para propósitos prácticos.

En la tabla, aparte de en la enorme magnitud de los términos en la cuarta fila, llama la atención el uso de extrañas flechas apuntando hacia arriba que aparecen en la quinta y sexta fila. Y es que el problema es que las torres de exponenciales se nos están quedando pequeñas, por lo que necesitamos una nueva notación.  Esta notación recibe el nombre de notación de flechas de Knuth, debida como su nombre indica al famoso matemático y científico de la computación Donald Knuth. Su propósito es exactamente el que buscamos, expresar números absurdamente grandes. Gaussianos tiene un artículo entero dedicado al asunto, pero para quien se fíe más de mí (craso error) dejo una explicación en este mismo artículo.

Empezaremos por las operaciones básicas: todo el mundo conocemos la operación suma, la operación producto, y la operación exponenciación. También se conoce la relación entre estas operaciones, multiplicar es sumar repetidas veces, elevar a un exponente es multiplicar repetidas veces, etc. El siguiente paso lógico es pues considerar una operación que consista en elevar a un exponente repetidas veces (más concretamente, elevar la base al número obtenido en el paso anterior repetidas veces). Como comentamos antes, eso ya está inventado, y se llama tetración. Funciona exactamente como un lector se puede imaginar, para a real y n natural estas cuatro operaciones se definen como:

Por supuesto, siempre podemos ir más allá, y definir la pentación, la hexación, etc. (a estas alturas entramos en el terreno de la terminología no estándar, más que nada porque no parece existir una terminología estándar). De modo más abstracto, la generalización de estas operaciones se llama sucesión de hiperoperaciones. Existen muchas notaciones para expresar los elementos de esta sucesión, de entre las cuales la más popular es la notación de flechas de Knuth.

Metámonos con la definición (pobre definición): se escribe a↑…(n)...↑b, donde n, el número de flechas, es el orden de la hiperoperación menos 2 (el orden de la suma es 1, el del producto es 2, el de la exponenciación es 3, etc.), para denotar la siguiente operación definida recursivamente:

Es evidente que para n=2-2=0 tenemos el producto, y el lector podrá comprobar fácilmente que para n=3-2=1 tenemos la exponenciación y para n=4-2=2 la tetración. Esta definición recuerda sin duda en cierto modo a la de la función de Ackermann, y es que, como ya hemos mencionado en otras ocasiones, la recursión es una herramienta esencial en este tema de los grandes números.

Pero el parecido no acaba ahí: la notación de flechas de Knuth nos permite dar una forma general a la función de Ackermann. Para que el lector no se aburra este fin de semana, se deja como ejercicio demostrar que

, identidad que indudablemente habría resultado muy útil para los alumnos de primero en la “prueba inicial de nivel”, y por supuesto también resuelve el Problema 6 del que hablábamos antes. Eso sí, los lectores parten con la gran ventaja de conocer la expresión, por lo que el mítico Problema 6 se convierte en un ejercicio sencillo de inducción, para suerte de todos aquellos que nos hemos querido sentir olímpicos alguna vez.

Con este ejercicio nos despedimos por el momento. Con suerte, la próxima entrada de Grandes Números llegará pronto, esperemos que antes de A(4,3) años.