La notación de Knuth, o cómo escribir ciertos números sin morir en el intento

Introducción

Los seres humanos tenemos 2 ojos, 5 dedos en cada mano y cada pie y la esperanza de vida en España ronda los 80 años actualmente. Un euro tiene 100 céntimos y un mileurista cobra 1000 euros mensuales. Podemos tener un coche de 12000 euros y una vivienda que nos cueste 200000 y ha habido semanas en las que el premio para la primera categoría del Euromillón ha rondado los 70 millones de euros (70000000 €).

Todas esas cantidades pueden ser escritas utilizando la notación habitual. Pero es evidente que cuanto mayor es el número esta forma de escribirlos se hace cada vez más engorrosa. Por suerte tenemos la potencias, gran arma para simplificar la escritura de ciertos números grandes.

Por ejemplo, si quisiéramos escribir la edad de la Tierra deberíamos escribir este número:

$4550000000$

que es la cantidad (en años) que se estima como edad de nuestro planeta. Utilizando las potencias la forma de escribirlo es más corta:

$4,55 \cdot 10^9$

Para esta cantidad puede que todavía no se perciba en toda su magnitud la utilidad de las potencias para esta tarea. Probemos con otra. Para escribir el número de átomos que se estima que hay en la Tierra tendríamos que escribir un 1 seguido de 51 ceros. Es decir, un número que ya tiene una cierta magnitud y, por qué no decirlo, bastante engorroso de escribir de la manera habitual. Nuestras amigas las potencias nos ayudan a simplificar esta tarea:

$10^{51}$

Hemos escrito el mismo número pero, como es evidente, de una forma bastante más cómoda.

Otro ejemplo más. A estas alturas casi todo sabréis qué es un googol. Sí, exacto, un 1 seguido de cien ceros. Escribir este número con la notación habitual alcanza ya el nivel de tarea insufrible. Otra vez las potencias nos ayudan con ella:

$10^{100}$

Pero, ¿qué ocurre si queremos escribir el número googelplex? Este número es un 1 seguidos de un googol de ceros y tiene ya unas dimensiones inimaginables para el ser humano. Bueno, os echo una mano:

$10^{10^{100}}$

Para representarlo hemos necesitado no sólo una potencia, sino dos. Vamos, una torre de potencias.

Con la ayuda de estas torres de potencias podemos representar número enormes que, como dije antes, escapan a nuestra percepción. La pregunta es: ¿podemos necesitar en algún momento escribir algún número cuya representación no pueda hacerse de forma sencilla con estas notaciones? La respuesta es sí. Y la notación de Knuth es una de las opciones más recomendables.

La notación de Knuth

La forma de representar números que vamos a ver fue introducida por Donald Knuth en 1976 y podemos decir que responde a la necesidad de representar ciertos números tremendamente grandes cuya representación en la forma habitual es extremadamente pesada.

Básicamente utiliza la idea comentada antes sobre torres de potencias, pero introduciendo nuevos símbolos para representarlas, ya que los números a los que está enfocada esta notación necesitan de una torre de potencias que se sale de lo admisible en lo que a escritura se refiere. Veamos cómo se hace todo esto.

Todos sabemos que al elevar un número natural (base) a otro (exponente) lo que hacemos es multiplicar la base tantas veces como indica el exponente, es decir:

$\begin{matrix} m^n = & \underbrace{m \cdot \ldots \cdot m} \\ & n \mbox{ veces} \end{matrix}$

Por ejemplo:

$\begin{matrix} 5^3= & \underbrace{5 \cdot 5 \cdot 5} \\ & 3 \mbox{ veces } 5 \end{matrix}$

Bien, pues Knuth introduce un nuevo símbolo para esta potencia con un único exponente:

$m^n= m \uparrow n$

A partir de aquí comienza la generalización. El siguiente paso sería este:

$\begin{matrix} m \uparrow \uparrow n & = {\ ^{n} m} = & \underbrace{m^{m^{{}^{.\,^{.\,^{.\,^m}}}}}} & = & \underbrace{m \uparrow (m \uparrow(\ldots\uparrow m))} \\ & & n \mbox{ veces } m & & n \mbox{ veces } m \end{matrix}$

Un ejemplo de esto:

$\begin{matrix} 5 \uparrow \uparrow 3 & = {\ ^{3} 5} = & \underbrace{5^{5^5}} & = & \underbrace{5 \uparrow (5 \uparrow 5)} & = & 5^{3125} \approx 1,911012597945478 \cdot 10^{2184} \\ & & 3 \mbox{ veces } 5 & & 3 \mbox{ veces } 5 \end{matrix}$

Fijáos de qué manera tan sencilla hemos escrito un número que tiene la nada despreciable cifra de 154 dígitos.

Vamos a ver unos cuantos ejemplos con el mismo número como base para que se pueda entender de forma más clara cómo van creciendo los resultados con esta doble flecha:

$2 \uparrow \uparrow 2= 2^2=4$
$2 \uparrow \uparrow 3=2^{2^2}=2^4=16$
$2 \uparrow \uparrow 4=2^{2^{2^2}}=2^{16}=65536$
$2 \uparrow \uparrow 5=2^{2^{2^{2^2}}}=2^{65536} \approx 2,003529930406846 \cdot 10^{19728}$

Es decir, al subir una unidad el segundo término lo que hacemos es elevar el primer término al número obtenido antes. Por ello podemos definir esta operación doble flecha por recurrencia de la siguiente forma:

$m \uparrow \uparrow 1=m$
$m \uparrow \uparrow (n+1)=m^{m \uparrow \uparrow n}$

Se puede deducir fácilmente que esta notación doble flecha puede ampliarse, es decir, podemos utilizar más flechas, lo que nos llevará a obtener números cada vez más grandes. Veamos cómo sería la notación triple flecha:

$\begin{matrix} m \uparrow \uparrow \uparrow n = & \underbrace{m\uparrow \uparrow (m \uparrow \uparrow (\ldots \uparrow \uparrow m))} \\ & n \mbox{ veces } m \end{matrix}$

Y, claro está, podemos pasar a cuádruple flecha:

$\begin{matrix} m \uparrow \uparrow \uparrow \uparrow n= & \underbrace{m \uparrow \uparrow \uparrow (m \uparrow \uparrow \uparrow (\ldots \uparrow \uparrow \uparrow m))}\\ & n \mbox{ veces } m \end{matrix}$

Y así sucesivamente. En general, y utilizando el símbolo $\uparrow ^k$ para representar $k$ flechas seguidas, la notación n-flecha se definiría de la siguiente manera:

$m \uparrow ^k n= m \uparrow ^{k-1} m \uparrow ^{k-1} m \ldots m \uparrow ^{k-1} m$

donde $m$ aparece $n$ veces.

Vamos a poner un par de ejemplos de la notación triple flecha:

$3 \uparrow \uparrow \uparrow 2=3 \uparrow \uparrow 3=3 \uparrow 3 \uparrow 3= 3^{3^3}=3^{27}=7625597484987$

Ahora

$\begin{matrix} 3 \uparrow \uparrow \uparrow 3=3 \uparrow \uparrow 3 \uparrow \uparrow 3=3 \uparrow \uparrow (3 \uparrow 3 \uparrow 3) = & \underbrace{3 \uparrow 3 \uparrow \ldots \uparrow 3} \\ & 3 \uparrow 3 \uparrow 3 \mbox{ veces } 3 \end{matrix}$

que da un número de repeticiones del $3$ que se sale del rango del Mathematica (podéis imaginar qué cantidad números $3$ puede tener esta expresión).

Utilidad de la notación de Knuth

Hemos comentado que esta notación sirve principalmente para representar de una forma relativamente simple ciertos números tremendamente grandes. Y habíamos hecho la siguiente pregunta:

¿Podemos necesitar en algún momento escribir algún número cuya representación no pueda hacerse de forma sencilla con estas notaciones?

(Hablamos de necesidad en el sentido de que dicho número sea útil, es decir, que sirva de algo, que aparezca en algún lugar de las matemáticas realizando una función.

Nuestra respuesta fue un rotundo sí, pero no habíamos dado nombre a este engendro. Y no hay mejor momento que éste para hacerlo. Hay al menos un número que ejerce una función concreta dentro de las matemáticas que sólo se puede escribir de manera mínimamente razonable utilizando una notación tipo la notación de Knuth. Nuestro protagonista se llama número de Graham y aparece en la demostración de un teorema haciendo la función de cota. Pero la descripción de este monstruo numérico (junto con la de otros monstruos de este tipo, aunque más modestos) la dejamos para otro momento (que no tardará mucho en llegar).

Fuente:

Knuth’s up-arrow notation en la Wikipedia inglesa.

14 comentarios

Trackback | 26 Jan, 2010

Bitacoras.com
Omar-P | 26 de January de 2010 | 11:47

Knuth y Graham asistieron este mes a la reunión anual de la AMS y la MAA en San Francisco, California.
Américo Tavares | 26 de January de 2010 | 18:07

Parece ser antes

$2\uparrow \uparrow 3=2^{2^{2}}=2^{4}=16$
gaussianos | 26 de January de 2010 | 18:22

Sí, falta un símbolo $=$ . Gracias Américo.
Rober | 26 de January de 2010 | 18:59

Te falta un = pero no te voy a decir dónde (je je)
…
Bueno, vale. Es en el ejemplo de 2^^3.
Rober | 26 de January de 2010 | 19:04

¡¡ se me adelantaron !! eso me pasa por abrir la página y dejar la lectura para después

Se me olvidó alabar el artículo. No es sólo por educación, es que me ha parecido muy interesante esta notación que desconocía.

¿Tiene sentido en esta operación usar números reales? En las potencias (sí se puede, pero también parece que no cuando se explica como “n” veces la factorización.
Jonas Castillo Toloza | 26 de January de 2010 | 21:57

Se puede operar con la notaciòn de Knuth?
Es decir, podemos sumar,multiplicar, etc?
Trackback | 26 Jan, 2010

Twitter Trackbacks for La notación de Knuth, o cómo escribir ciertos números sin morir en el intento | Gaussianos [gaussianos.com] on Topsy.com
^DiAmOnD^ | 26 de January de 2010 | 22:49

Se te adelantaron Rober .

Sobre lo de los números reales me da que la cosa va a ser difícil, ya que al definir la operación de forma recurrente nos ceñimos a números naturales.

Jonas, no había pensado en eso, pero me da que va a ser complicado. ¿Alguien tiene algún dato sobre operaciones con números expresados con esta notación?
Trackback | 27 Jan, 2010

Aleatoriedad sin azar | Gaussianos
Trackback | 28 Jan, 2010

Monstruos numéricos | Gaussianos
Marcos | 29 de January de 2010 | 04:19

Perdón, ya sé que no tiene mucho que ver, pero…
¿Alguien sabría explicarme cómo se desarrolla la Serie de Taylor de una función con dos variables?
Gracias
Dani | 29 de January de 2010 | 12:36

Te lo haré para orden 2 y te dejo a ti generalizarlo para mayores órdenes. Sea $f:\Omega \subset \mathbb{R}^2 \rightarrow \mathbb{R}$ una función $f \in \mathcal{C}^3$ definida en un abierto $\Omega$ convexo (es decir, dados dos puntos del conjunto el segmento que los une también pertenece al conjunto) y un punto $p_0=(x_0,y_0) \in \Omega$ . Sea $h=(h_1,h_2) \in \mathbb{R}^2$ tal que $p_0 + h \in \Omega$ . Definimos entonces la función (de una variable) $g:[0,1] \rightarrow \mathbb{R}$ por $g(t)=f(p_0 + th)$ , o $g=f \circ \phi$ para $\phi(t)=p_0 + th$ si se quiere. Como $f \in \mathcal{C}^3 \Rightarrow g \in \mathcal{C}^3$ , por el Teorema de Taylor en una variable se tiene
$g(t)=g(0)+g^{\prime}(0)t+\frac{1}{2}g^{\prime \prime}(0)t^2+\mathcal{R}(t), \qquad \qquad \lim_ {t \rightarrow 0} \frac{\mathcal{R}(t)}{t^2}=0$

Ahora bien, derivando $g$ por la regla de la cadena se obtiene $g^{\prime}(t)=Df_{\phi(t)} \circ D\phi_{t}=\nabla f _{\phi(t)} \cdot \phi^{\prime}(t)=\nabla f _{\phi(t)} \cdot h= \sum_{i=1}^{2}\frac{\partial f}{\partial x_i}\Big|_{\phi(t)}\cdot h_i$ .
De igual manera se comprueba (ejercicio ) usando la regla de la cadena, que:
$g^{\prime \prime}(t)= \sum_{j=1}^{2} \sum_{i=1}^{2} \frac{ \partial^2 f}{\partial x_j \partial x_i} \Big |_{\phi(t)} \cdot h_i h_j$ . Sustituyendo en la ecuación con $t=1$ obtenemos:

$f(p_0 + h)=f(p_0)+\sum_{i=1}^{2}\frac{\partial f}{\partial x_i}\Big|_{p_0}\cdot h_i \, \, + \, \, \frac{1}{2}\sum_{j=1}^{2} \sum_{i=1}^{2} \frac{ \partial^2 f}{\partial x_j \partial x_i} \Big |_{p_0} \cdot h_i h_j + \mathcal{R}(h)$

donde $\lim_{||h||\rightarrow 0 } \frac{R(h)}{||h||^2} =0$ (sabrías justificar esto? ) Si quieres hallar el polinomio de Taylor simplemente trunca el resto haciendo $P=f-\mathcal{R}$

Ej: $f(x,y)=\cos(x)\cos (y)$
$\frac{\partial f}{\partial x}=-\sin(x)\cos(y),\quad \frac{\partial f}{\partial y}=-\cos(x)\sin(y), \quad \frac{ \partial^2 f}{\partial x^2}=-\cos(x)\cos(y)$
$\quad \frac{ \partial^2 f}{\partial x \partial y}=\frac{ \partial^2 f}{\partial y \partial x}=\sin(x)\sin(y), \quad \frac{ \partial^2 f}{\partial y^2}=-\cos(x)\cos(y)$
con lo cual el polinomio de Taylor de orden 2 en el origen es:
$P_{f,2,(0,0)}(x,y)= 1 - \frac{1}{2}x^2 - \frac{1}{2}y^2$
que es lo que esperábamos pues es lo que sale multiplicando los polinomios de taylor de orden dos de $\cos(x)$ y $\cos(y)$ y truncando los términos de mayor grado.
Jonas Castillo Toloza | 30 de January de 2010 | 19:42

Cuando la notaciòn de knuth sea usada ampliamente, entonces nos daremos cuenta que existen nùmeros tan grandes que no podremos representar con esta notaciòn y nos veremos obligados a crear una nueva.