La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

Posts Tagged ‘Donald Knuth’

Donald Knuth cumple hoy 70 años

Posted by Carlos en enero 10, 2008

Donald E. Knuth

“Ciencia es aquello que conocemos lo suficientemente bien para explicárselo a un computador. El resto de lo que hacemos es Arte.

Donald Ervin Knuth (1938-), informático estadounidense

Hoy cumple 70 años Donald E. Knuth, uno de los padres fundadores de la algorítmica. A él debemos The Art of Computer Programming y el TeX, gracias al cual toda la comunidad científica no está a estas horas en las manos de Microsoft Word. Además de científico genial, Knuth siempre ha tenido un humor y un punto geek fantásticos. Por ejemplo, la versión i-ésima de TeX se identifica con la expansión en i dígitos de π, al igual que hace con METAPOST y el número e. También tiene la ocurrencia de emitir cheques por 2.56$ (1 dólar hexadecimal) a favor de quien encuentre un error en algún libro suyo (estos cheques son un trofeo cotizadísimo).

Su padre tenía una imprenta, y por ahí quizás venga el desarrollo de TeX, y su obsesión por la tipografía, que le ha hecho afirmar que no puede ir a comer a un restaurante, ya que no deja de mirar las fuentes tipográficas de la carta del menú. De todas formas, además de con la cita de más arriba, me quedo con otra suya sobre las matemáticas:

“¡Una fórmula matemática no debería ser nunca propiedad de nadie! Las matemáticas pertenecen a Dios.”

y con otra bastante irónica sobre la verificación formal:

Ten cuidado con este código. He demostrado su corrección, pero no lo he llegado a probar.”

{\cal FELICIDADES} , Profesor Knuth.

Posted in Algorítmica, Citas, Geek, Informática, Personajes, Programación | Etiquetado: | 11 Comments »

Números grandes, pero que muy grandes

Posted by Carlos en marzo 8, 2007

Hablemos de números grandes, y no me refiero por supuesto a millones, billones, o trillones. entonces, ¿decillones, undecillones, duodecillones, …? Esos están mejor, y el patrón con el que se construyen sus nombres está claro, con lo que podemos en principio pensar en números tan grandes como queramos; el problema es que el sistema no es cómodo, y lo nombres se hacen kilométricos eventualmente. Necesitamos entonces otra forma de describir estos números de manera más compacta, y para eso la notación matemática resulta ideal. El primer recurso del que podemos echar mano es de la operación de exponenciación. Por ejemplo,

10^{10^{10}}

o ya puestos

e^{e^{e^{79}}} \simeq 10^{10^{8.85\cdot 10^{33}}}

cantidad esta última conocida como el número de Skewes, y que es enormemente mayor que un googolplex. Por supuesto, nada nos impide continuar apilando exponentes para conseguir números increíblemente grandes, pero nuevamente la notación empieza a hacerse engorrosa. Necesitamos dar otro paso, y para ello vamos a recurrir a la notación sagital de Knuth. Esta notación es una generalización de la exponenciación, que podemos definir recursivamente como sigue:

  1. a\uparrow b= a^b
  2. \begin{matrix}    a\ \underbrace{\uparrow_{}\uparrow\!\!\dots\!\!\uparrow}\ b=     a\ \underbrace{\uparrow\!\!\dots\!\!\uparrow}     \ a\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow}     \ a\ \dots     \ a\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow}     \ a   \\    \quad\ \ \,n\qquad\ \ \ \underbrace{\quad n_{}\!-\!\!1\quad\ \,n\!-\!\!1\qquad\quad\ \ \ \,n\!-\!\!1\ \ \ }   \\    \qquad\qquad\quad\ \ b\mbox{ copias de }a   \end{matrix}

De acuerdo con esta definición,

a\uparrow\uparrow b = a\uparrow a \uparrow a \uparrow \cdots \mbox{(\emph{b} veces)} \cdots \uparrow a = a^{a^{a^{\cdots^a}}}

donde en la pila de exponentes hay b-1 aes. Como esta notación nos puede hacer perder la noción del tamaño de los números que estamos manejando, consideremos por ejemplo que

3\uparrow\uparrow\uparrow 3 = 3\uparrow\uparrow 3\uparrow\uparrow 3 = 3\uparrow\uparrow( 3\uparrow 3 \uparrow 3) = 3\uparrow \uparrow 7,625,597,484,987

o lo que es lo mismo, una torre de 7,625,597,484,986 exponentes anidados. Se trata de un número que ya no tiene connotación física, y que apenas podemos concebir. Sin embargo, podemos por supuesto ir más allá, y definir números todavía mayores y -lo que es más importante- con relevancia matemática. Para ello, vamos a usar la siguiente abreviatura de la notación sagital:

\begin{matrix} a \uparrow ^{n} b = a\underbrace{\uparrow\uparrow\cdots\uparrow}b \\ \qquad\qquad\quad\ \ n \end{matrix}

Hecho esto, vamos a considerar la siguiente serie:

  1. g_1 = 3\uparrow\uparrow\uparrow\uparrow 3
  2. g_{n+1} = 3\uparrow^{g_n} 3

Para ver en qué términos se mueve esta serie, observemos g1, el primer valor de la misma:
g_1  = 3 \uparrow \uparrow \uparrow (3 \uparrow \uparrow \uparrow 3)  = 3 \uparrow \uparrow \uparrow    \left(      \begin{matrix}        \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}} \\        3^{3^3}      \end{matrix}   \right) = \left.     \begin{matrix}       \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}} & \  \\       \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}  \\       \vdots & \vdots \\       \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}  \\       3^{3^3} \\     \end{matrix}   \right \}   \begin{matrix}     \ & \ \\     \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}} & \mbox{ niveles} \\      3^{3^3} &    \end{matrix}

donde cada llave horizontal indica la altura de la columna de símbolos. De acuerdo con esto, el tamaño de la columna de exponentes final es tal que podemos considerar en primer lugar una torre de 7,625,597,484,986 exponentes. Este número sería a su vez el número de exponentes que consideraríamos en el siguiente nivel, y así sucesivamente durante un número de niveles equivalente a una torre de 7,625,597,484,986 exponentes. Este número no es que escape a nuestra compresión; ni siquiera puede decirse que sea monstruosamente grande. Tendríamos que considerar que dicha monstruosidad es en sí misma absurdamente grande, y aplicar dicha consideración un número brutalmente grande de veces.

Si el paso de tres a cuatro flechas ha sido tan irracionalmente grande, me empiezo a quedar sin adjetivos para describir lo que pasa con g2, esto es, cuando el número de flechas es g1. Nada de lo que diga puede posiblemente describir dicho número de manera comprensible más allá de su propia definición matemática, lo cual es un hecho estremecedor, teniendo en cuenta que existe una aberración denominada el número de Graham, definido como… ¡g64! Lo realmente increíble es que este número ha aparecido en la resolución de un problema del área conocida como Teoría de Ramsey. En dicha área se plantean cuestiones del tipo “¿cuántos elementos ha de tener una cierta estructura para que forzosamente tenga una cierta propiedad?” Para una de estas preguntas relacionada con el coloreado de las aristas de un hipercubo se obtiene una cota superior igual al número de Graham (la cota inferior -mejorada recientemente- es 11, por lo que como apuntaban en 1971 los descubridores del número con indudable gracejo, “hay margen de mejora entre ambas cotas”).

La forma más adecuada para representar números de la magnitud del número de Graham no es ya la notación sagital de Knuth, sino la notación sagital encadenada de Conway. En cualquier caso, quien quiera una descripción sucinta de un número grande puede darle vueltas a la siguiente: “uno más que el mayor número expresable con menos de cien símbolos“.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Matemáticas | Etiquetado: , , , , | 9 Comments »