La Enciclopedia Libre Universal en Español dispone de una lista de distribución pública, enciclo@listas.us.es

Potencias iteradas de Donald Knuth

Artículo de la Enciclopedia Libre Universal en Español.

Saltar a navegación, buscar

Índice

1 Introducción
2 Potencias iteradas de Knuth
- 2.1 Definición
- 2.2 Ejemplos
3 Cadenas de Conway
- 3.1 Definición
- 3.2 Ejemplos

[escribe] Introducción

La operación más sencilla y básica de la aritmética es la que incrementa, es decir añade uno a un entero positivo dado: s(n) = n + 1, lo que se lee el sucesor de n es n + 1.

A partir de s, se define la adición de los enteros positivos aplicando varias veces s, es decir iterándola: m + n se obtiene efectuando n veces la operación de añadir 1 a m:

$\begin{matrix} m + n = m + \underbrace{1_{} + 1 + ... + 1}\\ \qquad\quad\ \qquad \mbox{ n veces + 1} \end{matrix}$

La multiplicación se define a su vez como una iteración de la adición, pues multiplicar m por n es adicionar n veces m:

$\begin{matrix} m \times n = \underbrace{m_{} + m + ... + m}\\ \qquad \quad \mbox{ n veces m} \end{matrix}$

También es bien sabido que la potencia $a b$ es por definición misma una iteración de multiplicaciones:

$\begin{matrix} m^n = \underbrace{m_{}\times m\times ... \times m}\\ \qquad\ \quad \mbox{n veces m} \end{matrix}$

En este punto uno puede preguntarse ¿ Por qué no se ha continuado este proceso de iteración ?

En primer lugar, la adición, la multiplicación y la potenciación corresponden a operaciones intuitivas y de clara ilustración geométrica: se añaden longitudes al juntar dos segmentos, se multiplican longitudes al medir la superficie de un rectángulo, y la superficie de un cuadrado y el volumen de un cubo ilustran perfectamente las potencias dos y tres (pero no las siguientes). No sería el caso de la iterada de la potencia.

En segundo lugar, la necesidad de tener funciones que crecen más rapidamente hacia el infinito que las potencias está cumplida por la exponencial en el campo del análisis y la factorial en la aritmética.

Sin embargo, estos argumentos no son decisivos: Desde finales del siglo XIX los matemáticos saben prescindir de las representaciones geométricas de sus nuevos conceptos, y desde mediados del siglo XX ha aparecido otro dominio, la informática, donde se puede necesitar enteros muy grandes, por ejemplo para medir la complejidad de los algoritmos.

[escribe] Potencias iteradas de Knuth

[escribe] Definición

Se inventó la notación m↑n para designar a mⁿ en los primeros ordenadores por una razón práctica: era mucho más facil escribir en una misma línea las fórmulas - no se habían inventado todavía los editores de ecuaciones. La flecha hacia arriba ilustraba la elevación a la potencia y fue sustituida por el acento circunflejo ^ que es la más usual hoy en día.

El informático Donald Knuth se quedó con la antigua notación y definió en 1976 los operadores que completan naturalmente la serie incrementación, adición, multiplicación, potenciación y que llevan su nombre:

El primer operador nuevo es la potencia iterada, denotada por una doble flecha: ↑↑ :

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

Se conviene que en presencia del símbolo $\uparrow$ se evalua siempre la expresión a partir de la derecha, aplicando la asociatividad a la derecha. Por ejemplo: $m \uparrow n \uparrow p = m \uparrow ( n \uparrow p) = m \uparrow n^p = m^{n^p}$ . Esta convención permite prescindir de los paréntesis.

Se define luego el operador triple flecha como iteración de la doble flecha:

$\begin{matrix} m\uparrow\uparrow\uparrow n = \underbrace{m\uparrow\uparrow m\uparrow\uparrow ... \uparrow\uparrow m}\\ \qquad\qquad\ \,\mbox{n veces m} \end{matrix}$

luego, sin sorpresa:

$\begin{matrix} m\uparrow\uparrow\uparrow\uparrow n= \underbrace{m\uparrow\uparrow\uparrow m\uparrow\uparrow\uparrow ... \uparrow\uparrow\uparrow m}\\ \qquad\qquad\quad \mbox{n veces m} \end{matrix}$

y así sucesivamente. Para escribir la fórmula general, utilizemos la notación siguiente:

$\begin{matrix} \uparrow^{{ }^p} = \underbrace{\uparrow\uparrow ... \uparrow } \\ \quad \ \ \ \mbox{p flechas} \end{matrix}$

Entonces el p-ésimo operador se define iterando él de rango inmediatamente inferior:

$\begin{matrix} m \uparrow^{{ }^p} n = \underbrace{m_{} \uparrow^{{ }^{p-1}} m \uparrow^{{ }^{p-1}} \dots \uparrow^{{ }^{p-1}} m}\\ \qquad\qquad\quad \mbox{n veces m} \end{matrix}$

Si n = 1, lo anterior vale m pues no queda flecha en el miembro derecho (esta justificación esconde una convención), y si n = 0, lo anterior vale 1, elemento neutro de la multiplicación. Esto permite también definir estos operadores por inducción sobre n y p utilizando la relación siguiente (que se obtiene separando el primer m de los siguientes en la definición anterior):

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

[escribe] Ejemplos

El 1 siempre simplifica los cálculos: Ya se ha dicho que $m \uparrow^{{ }^p} 1 = m$ ; también tenemos $1 \uparrow^{{ }^p} n = 1$ para cualquier natural n, pues al fin y al cabo $m \uparrow^{{ }^p} n$ es una potencia de m, en este caso de 1. Y claro, $m \uparrow^{{ }^1} n = m^n$ por definición misma.

Otro resultado general es $2 \uparrow^{{ }^p} 2 = 4$ para cualquier natural p ≥ 1, lo que se establece por inducción, pues $2 \uparrow^{{ }^p} 2 = 2 \uparrow^{{ }^{p-1}} 2$ . Lo utilizamos en el último ejemplo numérico.

$10 \uparrow \uparrow 2 = 10 \uparrow 10 = 10^{10} = 10.000.000.000$

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

$2 \uparrow^{{ }^4} 3 = 2 \uparrow^{{ }^3} ( 2 \uparrow^{{ }^3} 2 ) = 2 \uparrow^{{ }^3} 4 = 2\uparrow^{{ }^2} 2 \uparrow^{{ }^2}( 2 \uparrow^{{ }^2} 2) = 2 \uparrow \uparrow 2 \uparrow \uparrow 4 = 2 \uparrow \uparrow (2 \uparrow 2 \uparrow 2 \uparrow 2) = 2 \uparrow \uparrow 2^{16}$

$= \begin{matrix} \underbrace{2^{2^{{}^{.\,^{.\,^{.\,^2}}}}}} \\ \mbox{65 536 veces 2} \end{matrix}$

El cálculo efectivo se puede realizar mediante el algoritmo siguiente, que define una función recursiva (es decir que se llama a si misma) Knuth: (a ← b significa que se da a a el valor de b)

función Knuth(m, p, n) que calcula m↑^{^p}n

inicio m, n y p son naturales no nulos

si p = 1 entonces r ← mⁿ

sino r ← 1 luego:

repetir n veces: r ← Knuth(m, p-1, r)

devolver r (la respuesta momentánea es r)

fin

El valor de m↑^{^p}n se encuentra en r

[escribe] Cadenas de Conway

[escribe] Definición

John Horton Conway, matemático británico, propuso escribir las potencias iteradas con cadenas de números: m↑^{^p}n se reescribe m → n → p. (nótese bien el orden de las letras).

Esta notación sugiere que es posible definir el valor numérico de cadenas de otras longitudes:

Una cadena de longitud uno es un número (no hay flecha),
Una cadena de longitud dos es: m → n y vale mⁿ pues es una costumbre muy general no escribir los exponientes que valen 1: de la misma manera que m↑n significa m↑^¹n, m → n es lo mismo que m → n → 1, que vale mⁿ.
Lo novedoso son las cadenas de longitud superior a 3, como: a → b → c → d. ¿Cómo calcularlas?

La fórmula fundamental de las potencias iteradas:

$\begin{matrix} m \uparrow^{{ }^p} n = \underbrace{m_{} \uparrow^{{ }^{p-1}} m \uparrow^{{ }^{p-1}} \dots \uparrow^{{ }^{p-1}} m}\\ \qquad\qquad\quad \mbox{n veces m} \end{matrix}$

se escribe con las cadenas de Conway así:

$\begin{matrix} m\rightarrow n\rightarrow p = & \underbrace{m\rightarrow ( m\rightarrow ( \ldots m\rightarrow (m)} & \underbrace{\rightarrow p-1 \ldots ) \rightarrow p-1 ) \rightarrow p-1} \\ & \mbox{n veces m} & \mbox{n-1 veces p-1} \end{matrix}$

Para verlo, basta con reintroducir los paréntesis en la expresión de Knuth y remplazar poco a poco la notación de Knuth por la de Conway.

Como Conway quería generalizar las potencias iteradas, decidió que la relación anterior sería válida si se remplazara el número m (que es una cadena de longitud uno) por una cadena cualquiera C. La regla fundamental de las cadenas de Conway es entonces:

$\begin{matrix} C\rightarrow n\rightarrow p = & \underbrace{C\rightarrow ( C\rightarrow ( \ldots C\rightarrow (C)} & \underbrace{\rightarrow p-1 \ldots ) \rightarrow p-1 ) \rightarrow p-1} \\ & \mbox{n veces C} & \mbox{n-1 veces p-1} \end{matrix}$

A primera vista, uno puede dudar de su utilidad: el miembro derecho parece mucho más complicado que el izquierdo. Si se mira mejor, cada par de paréntesis contiene una cadena de longitud igual que la de C → n → p (salvo la (C) central, de longitud menor), y se ha disminuido el último número de cada cadena (se llama la cabeza de la cadena), de p a p - 1.
Reiterando este proceso se logra obtener cabezas que valen 1 que se pueden suprimir: En efecto C → 1 equivale a C por la misma razón que m → n → 1 vale m → n. Se obtiene así una cadena de longitud inferior - el proceso se llama reducción de la cadena - y, otra vez repitiéndolo, se logra obtener una cadena de longitud dos, lo que da su valor.
Más generalmente se pueden truncar toda cadena que contiene un 1: C → 1 → D vale C.

Con estas tres reglas se puede, en teoría y con muchísima paciencia, calcular cualquier cadena. Sin embargo, son muy escasas las cadenas cuyo valor es accesible a una calculadora de bolsillo.

La reducción de la cadena C → n → p da otra de la forma C → q (el número q es en general mucho mayor que n y p). Por tanto las cadenas son una potencia de su primer número (a la izquierda): al fin y al cabo, a → C se reducirá a a → n y valdrá aⁿ. En particular las que empiezan por 1 valen 1, y las que empiezan por 2 → 2 valen 4 pues 2 → 2 → C = 2 → 2 → n = 2↑^ⁿ2 = 4 como ya se ha visto.

[escribe] Ejemplos

$\begin{matrix} \underbrace{3 \rightarrow 2} & \rightarrow 2 \rightarrow 2 = C \rightarrow 2 \rightarrow 2 = C \rightarrow (C \rightarrow 1) = C \rightarrow ( 3 \rightarrow 2) = C \rightarrow 9 = 3 \rightarrow 2 \rightarrow 9 \\ C & \end{matrix}$ $= 3 \uparrow^{{ }^9} 2 = 3 \uparrow^{{ }^8} 3 = 3 \uparrow^{{ }^7} 3 \uparrow^{{ }^7} 3 = ...$