Notação de Knuth para números inteiros gigantes

Na matemática, a notação de Knuth é um sistema de representação para números inteiros muito grandes. Foi desenvolvida pelo matemático americano Donald Knuth em 1976. Está fortemente relacionada com a função Ackermann e seu conceito é baseado em exponenciação iterativa, do mesmo modo que exponenciação é semelhante à multiplicação iterativa e multiplicação é similar à adição iterativa.

A notação utiliza setas apontando para cima (↑) entre os números, daí o nome original em inglês "Knuth's up-arrow notation". Neste texto usarei o caractere | para representar a seta para cima.

Um operador de uma única seta para cima é o mesmo que exponenciação. Uma multiplicação de n termos do número m:

m|n = m x m x ... x m = m^n

Duas setas para cima juntas representam uma torre de potências. Uma torre de altura n, ou simplesmente m elevado à potência por ele mesmo, n vezes, incluindo a base até o expoente mais superior:

m||n = m|m|m|...|m = m^m^m^...^m

A operação de duas setas é uma função exponencial iterada conhecida como tetração que rapidamente gera números enormes. Por exemplo:

2||2 = 2|2 = 4
2||3 = 2|2|2 = 2|4 = 16
2||4 = 2|2|2|2 = 2|16 = 65536
3||2 = 3|3 = 27
3||3 = 3|3|3 = 3|27 = 7625597484987
3||4 = 3|3|3|3 = 3|3|27 = 3^7625597484987

Três setas para cima juntas representam uma operação vastamente mais poderosa, é uma torre de potências de uma torre de potências, é uma iteração de n termos m em uma operação de tetração:

m|||n = m||m||...||m

Por exemplo:

2|||2 = 2||2 = 4
2|||3 = 2||2||2 = 2||4 = 65 536
2|||4 = 2||2||2||2 = 2||65536 = 2|2|...|2 (65 536 termos)
3|||2 = 3||3 = 7625597484987
3|||3 = 3||3||3 = 3||7625597484987 = 3|3|...|3 (uma torre de 7625597484987 camadas de altura)
3|||4 = 3||3||3||3 = 3||3||7625597484987 = 3||3|...|3 (uma torre de 3||7625597484987 camadas de altura)

Similarmente avança-se para um operador quatro setas para cima, onde seguindo a regra geral, um operador n-setas se expande em operadores (n-1)-setas, com n termos m:

m||||n = m|||m|||...|||m

Por exemplo:

2||||2 = 2|||2 = 4
2||||3 = 2|||2|||2 = 2|||4 = 2|2|...|2 (65536 termos)
2||||4 = 2|||2|||2|||2 = 2|||2|2|...|2 (65536 termos)
3||||2 = 3|||3 = 3|3|...|3 (7625597484987 termos)
3||||3 = 3|||3|||3 = 3|||3|3|...|3 (7625597484987 termos) = 3||3|3|...|3 (3|3|...|3 (7625597484987 termos) termos)

A notação de Knuth pode se expandir de uma forma incrivelmente longa, se tornando maçante, mas é uma forma mais prática de representar números inteiros extremamente grandes, como os que são retornados pela função de Ackermann:

A(4,2) = 2||5 - 3 = 2^65536 - 3 = um número com 19729 dígitos decimais!