En matemàtiques, la notació de fletxa de Knuth és un mètode de notació per a grans nombres enters, introduïda per Donald Knuth el 1976.[1]
En el seu article de 1947,[2] R. L. Goodstein introdueix la seqüència especifíca d'operacions que avui en dia es coneixen com hiperoperacions. Goodstein també suggereix els noms grecs tetració, pentació, etc., per a l'extensió de les operacions més enllà de l'exponenciació. La seqüència comença amb una operació unària (la funció successor amb n = 0), i continua amb les operacions binàries d'addició (n = 1), multiplicació (n = 2), exponenciació (n = 3), tetració (n = 4), pentació (n = 5), etc. Diverses notacions han estat emprades per representar les hiperoperacions. Una d'elles és la notació
, així com també ho és la notació de fletxa de Knuth
.
Per exemple:
- una única fletxa
representa exponenciació (multiplicació iterada) 
- la doble fletxa
representa tetració (exponenciació iterada) ![{\displaystyle 2\uparrow \uparrow 4=2[4]4=2\uparrow (2\uparrow (2\uparrow 2))=2^{2^{2^{2}}}=2^{16}=65,536}](https://wikimedia.org/api/rest_v1/media/math/render/svg/18a269e3f7c8538a9618619d9fba8e417f2c8b09)
- la triple fletxa
representa pentació (tetració iterada) 
La definició general de la notació de fletxa és la següent (per
):
Aquí,
denota n fletxes,
així com per exemple
Els parèntesis quadrats són una altra notació per a hiperoperacions.
Les hiperoracions estenen naturalment les operacions aritmètiques d'addició i multiplicació de la següent manera. L'addició per un nombre natural es defineix com un increment iterat:

La multiplicació per un nombre natural es defineix com addició iterada:

Per exemple,

L'exponenciació a una potència natural
es defineix com multiplicació iterada, la qual Knuth denota amb una sola fletxa:

Per exemple,

La tetració es defineix com exponenciació iterada, la qual Knuth denota amb "dues fletxes":

Per exemple,

Les expressions s'avaluen de dreta a esquerra, ja que els operadors es defineixen de manera associativa per la dreta.
D'acord amb aquesta definició,




- etc.
Això ja dona lloc a nombres notablement grans, però la seqüència d'hiperoperadors no s'atura aquí.
La pentació, definida com a tetració iterada, es representa amb "tres fletxes":

L'hexació, definida com a pentació iterada, es representa amb "quatre fletxes":

i així successivament. La regla general és que l'operador amb
fletxes s'expandeix de manera associativa per la dreta en una sèrie d'operadors amb
fletxes. De manera simbòlica,

Exemples:


En expressions tals com
, la notació per exponenciació consisteix habitualment a escriure l'exponent
com un superíndex a la base del nombre
. Ara bé, en molts entorns — tals com llenguatges de programació i text simple en correu electrònic — no admeten l'escriptura amb superíndexs. La gent ha adoptat la notació lineal
per a tals entorns; on la fletxa cap amunt suggereix 'elevar a la potència de'. Si el conjunt de caràcters no conté una fletxa cap amunt, el símbol caret (^) és usat en el seu lloc.
La notació amb superíndex
no permet una fàcil generalització, motiu que explica per què Knuth va decidir treballar, en canvi, amb la notació
.
és una alterntavia més breu per a denotar n fletxes cap amunt. Per exemple,
.
Expressió de la notació de fletxa en termes de potències
[modifica]
Intentar escriure
usant la notació superíndex familiar dona lloc a una torre de potències.
- Per exemple:

Si b és una variable (o és massa gran), la torre de potències pot escriure's usant punts suspensius i una nota indicant l'altura de la torre.

Continuant amb aquesta notació,
pot ser reescrit com una pila de tals torres de potències, cadascuna descrivint l'altura de la torre que té just a sobre.

De nou, si b és una variable o és massa gran, la pila pot escriure's mitjançant punts suspensius i una nota indicant l'altura.

Encara més,
pot ser escrit usant diverses columnes de tals piles de torres de potències, amb cada columna descrivint el nombre de torres de potències en la pila de la seva esquerra:

I més generalment:

Això pot ser dut a terme de manera indefinida per representar
com una exponenciació iterada d'una exponenciació iterada per qualssevol a, n i b (malgrat que és evident que esdevé ràpidament feixuc).
La notació de Rudy Rucker
per a la tetració permet simplificar lleugerament els diagrames anteriors, alhora que encara dona una representació geomètrica (que podríem anomenar torres de tetració).



Finalment, com a exemple, el quart nombre d'Ackermann
pot ser representat com:

Alguns nombres són tan grans que múltiples fletxes de la notació de Knuth esdevenen massa feixugues; aleshores un operador n-fletxa
és útil (i també per a descripcions amb un nombre variable de fletxes), o equivalentment, hiperoperadors.
Alguns nombres són tan grans que fins i tot aquesta notació no és suficient. La notació de fletxes encadenades de Conway pot ser usada en aquest cas: una cadena de tres elements és equivalent a altres notacions, mentre que una cadena amb quatre és encara més potent.
Les funcions que creixen encara més ràpid poden ser categoritzades fent ús d'una anàlisis ordinal anomenat jerarquia de ràpid creixement. La jerarquia de ràpid creixement utilitza iteracions successives de funcions i diagonalització per tal de crear sistemàticament funcions que creixin més ràpidament que una funció base
. Per a la jerarquia de creixement ràpid estàndard, usant
,
ja presenta creixement exponencial,
és comparable al creixement de tetració i està acotada per sobre per una funció que involucra els quatre primers hiperoperadors. Aleshores,
és comparable a la funció d'Ackermann,
ja està més enllà de l'abast de les fletxes indexades, però pot ser emprada per aproximar el nombre de Graham, i
és comparable a cadenes arbitràriament llargues en la notació de fletxes encadenades de Conway.
Aquestes funcions són totes computables. Algunes funcions computables encara més ràpides, com la seqüència de Goodstein i la seqüència TREE requereixen l'ús de grans ordinals, i poden aparèixer en certs contextos combinatòrics i de teoria de demostracions. Existeixen també funcions que creixen ràpidament de manera no computable, com la Busy Beaver, la naturalesa de la qual està fora de l'abast de la notació de fletxes, o fins i tot de cap anàlisi basada en ordinals.
Sense fer referència a les hiperoperacions, els operadors de fletxa poden ser definits formalment per

per a tots els enters
amb
[nb 1].
Aquesta definició usa exponenciació
com a cas base, i tetració
com a exponenciació repetida. Això és equivalent a la seqüència d'hiperoperacions llevat que omet les tres operacions més bàsiques successió, addició i multiplicació.
Alternativament, hom pot triar la multiplicació
com a cas base, i iterar a partir d'aquest. Aleshores, l'exponenciació esdevé multiplicació repetida. La definició formal seria doncs

per a tots els enters
amb
.
Notem, però, que Knuth no va definir la "fletxa-buida" (
). Hom podria estendre la notació a índexs negatius (n ≥ -2) de tal manera que estigués d'acord amb tota la seqüència d'hiperoperacions, llevat per al desplaçament en la indexació:
![{\displaystyle H_{n}(a,b)=a[n]b=a\uparrow ^{n-2}b{\text{ per a }}n\geq 0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c2354985f3f3381788cd5ed9a8348973d01e340)
L'operació de fletxa és una operació associativa per la dreta, això és,
s'entén que correspon a
, en lloc de
. Si l'ambigüitat no és un problema, els parèntesis sovint no s'escriuen.
Avaluar
resulta en
- 0, quan n = 0 [nb 2]
- 1, quan n = 1 i b = 0 [nb 1][nb 3]
- 0, quan n = 1 i b > 0 [nb 1][nb 3]
- 1, quan n > 1 i b és parell (inclòs 0)
- 0, quan n > 1 i b és senar
Avaluar
pot ser expressat en termes d'una taula infinita. Si col·loquem els nombres
a la fila superior i omplim la columna de l'esquerra amb els valors 2. Per determinar un nombre a la taula, agafem el nombre immediatament a l'esquerra i, a continuació, cerquem el nombre requerit a la fila anterior, a la posició donada pel número que acabem de prendre.
Valors de
=
=
= 2 → b → n
b ⁿ
|
1
|
2
|
3
|
4
|
5
|
6
|
fórmula
|
1
|
2 |
4 |
8 |
16 |
32 |
64 |
|
2
|
2 |
4 |
16 |
65536 |
 |
 |
|
3
|
2 |
4 |
65536 |
 |
 |
 |
|
4
|
2 |
4 |
 |
 |
 |
|
|
La taula és la mateixa que la de la funció d'Ackermann, malgrat que està desplaçada en
i
, i cal afegir 3 a tots els valors.
Col·loquem els nombres
a la fila superior, i omplim la columna esquerra amb els valors 3. Per determinar un nombre de la taula, prenem el nombre immediatament a l'esquerra, llavors mirem el nombre requerit a la fila anterior, a la posició donada pel número que acabem de prendre.
Valors de
=
=
= 3 → b → n
b ⁿ
|
1
|
2
|
3
|
4
|
5
|
fórmula
|
1
|
3 |
9 |
27 |
81 |
243 |
|
2
|
3 |
27 |
7,625,597,484,987 |
 |
 |
|
3
|
3 |
7,625,597,484,987 |
 |
 |
 |
|
4
|
3 |
 |
 |
 |
|
|
Col·loquem els nombres
a la fila superior, i omplim la columna esquerra amb els valors 4. Per determinar un nombre de la taula, prenem el nombre immediatament a l'esquerra, llavors mirem el nombre requerit a la fila anterior, a la posició donada pel número que acabem de prendre.
Valors de
=
=
= 4 → b → n
b ⁿ
|
1
|
2
|
3
|
4
|
5
|
fórmula
|
1
|
4 |
16 |
64 |
256 |
1024 |
|
2
|
4 |
256 |
 |
 |
 |
|
3
|
4 |
 |
 |
 |
 |
|
4
|
4 |
 |
 |
 |
|
|
Col·loquem els nombres
a la fila superior, i omplim la columna esquerra amb els valors 10. Per determinar un nombre de la taula, prenem el nombre immediatament a l'esquerra, llavors mirem el nombre requerit a la fila anterior, a la posició donada pel número que acabem de prendre.
Valors de
=
=
= 10 → b → n
b ⁿ
|
1
|
2
|
3
|
4
|
5
|
fórmula
|
1
|
10 |
100 |
1,000 |
10,000 |
100,000 |
|
2
|
10 |
10,000,000,000 |
 |
 |
 |
|
3
|
10 |
 |
 |
 |
 |
|
4
|
10 |
 |
 |
 |
|
|
Per a 2 ≤ b ≤ 9 l'ordre numèric dels nombres
és l'ordre lexicogràfic amb n el nombre més significant, així que per als números d'aquestes 8 columnes l'ordre numèric és senzillament línia per línia. El mateix aplica per als números en les 97 columnes amb 3 ≤ b ≤ 99, i si comencem per n = 1 inclús per 3 ≤ b ≤ 9,999,999,999.
- ↑ 1,0 1,1 1,2 Per a més detalls, vegeu Potències de zero.
- ↑ Tinguem present que Knuth no va definir l'operador
, i s'ha pres l'extensió de la definició per a concordar amb la seqüència d'hiperoperadors.
- ↑ 3,0 3,1 Per a més detalls, vegeu Zero a la potència de zero.
|
---|
Primari | |
---|
Inversa per a l'argument esquerre | |
---|
Inversa per a l'argument dret | |
---|
Vegeu també | |
---|