Hyperoperation

Den här artikeln handlar om aritmetikbegreppet. För det gruppteoretiska hyperoperationskonceptet, se Hyperstruktur .

I matematik är hyperoperationssekvensen en oändlig sekvens av aritmetiska operationer (kallade hyperoperationer i detta sammanhang) som börjar med en unär operation ( efterföljarens funktion med n = 0). Sekvensen fortsätter med de binära operationerna addition ( n = 1), multiplikation ( n = 2) och exponentiering ( n = 3) .

Därefter fortsätter sekvensen med ytterligare binära operationer som sträcker sig bortom exponentiering, med hjälp av högerassociativitet . För operationerna bortom exponentiering är den n: te medlemmen av denna sekvens namngiven av Reuben Goodstein efter det grekiska prefixet n med suffixet -ation (såsom tetration ( n = 4), pentation ( n = 5), hexation ( n = 6 ), etc.) och kan skrivas med n − 2 pilar i Knuths upp-pil notation . Varje hyperoperation kan förstås rekursivt i termer av den föregående av:

$a[n]b=\underbrace {a[n-1](a[n-1](a[n-1](\cdots [n) -1](a[n-1](a[n-1]a))\cdots )))} _{\displaystyle b{\mbox{ kopior av }}a},\quad n\geq 2$

Det kan också definieras enligt rekursionsregeldelen av definitionen, som i Knuths uppåtpilsversion av Ackermann-funktionen :

$a[n]b=a[n-1]\left(a[n]\ vänster(b-1\höger)\höger),\quad n\geq 1$

Detta kan användas för att enkelt visa tal som är mycket större än de som vetenskaplig notation kan, såsom Skewes tal och googolplexplex (t.ex. $50[50]50$ är mycket större än Skewes tal och googolplexplex), men det finns några siffror som inte ens de lätt kan visa, som Grahams nummer och TREE(3) .

Denna rekursionsregel är gemensam för många varianter av hyperoperationer.

Definition

Definition, vanligast

Hyperoperationssekvensen ${N} _{0}}$${\displaystyle H_{n}(a,b)\colon (\mathbb {N} _{0})^{3}\rightarrow \$ mathbb är sekvensen av binära operationer $H_{n}\colon (\mathbb {N} _{0})^{2}\rightarrow \ mathbb {N} _{0}$ , definierad rekursivt enligt följande:

$H_{n}(a,b)=a[n]b={\begin{cases}b+1&{\text{if }}n=0 \\a&{\text{if }}n=1{\text{ och }}b=0\\0&{\text{if }}n=2{\text{ och }}b=0\\1&{ \text{if }}n\geq 3{\text{ och }}b=0\\H_{n-1}(a,H_{n}(a,b-1))&{\text{annars} }\end{cases}}$

(Observera att för n = 0 reduceras den binära operationen i huvudsak till en unär operation ( efterföljande funktion ) genom att ignorera det första argumentet.)

För n = 0, 1, 2, 3, återger denna definition de grundläggande aritmetiska operationerna av efterföljare (som är en unär operation), addition , multiplikation och exponentiering , respektive, som

${\begin{aligned}H_{0}(a,b)&=b+1,\\H_{1}(a,b)&=a+b,\\H_{2}(a, b)&=a\ gånger b,\\H_{3}(a,b)&=a\uparrow {b}=a^{b}.\end{aligned}}$

H $H_{n}$ operationerna för n ≥ 3 kan skrivas i Knuths upp-pil .

Så vad blir nästa operation efter exponentieringen? Vi definierade multiplikation så att $H_{2}(a,3)=a[2]3=a\ gånger 3=a+a+a,$ och definierad exponentiering så att $H_{3}( a,3)=a[3]3=a\uparrow 3=a^{3}=a\times a\times a,$ så det verkar logiskt att definiera nästa operation, tetration, så att $H_{4}(a,3)=a[4]3=a\uparrow \uparrow 3=\operatörsnamn {tetration} (a,3)=a^{a^{a}},$ med ett torn på tre 'a'. Analogt kommer pentationen av (a, 3) att vara tetration(a, tetration(a, a)), med tre "a" i den.

${\ displaystyle {\begin{aligned}H_{4}(a,b)&=a\uparrow \uparrow {b},\\H_{5}(a,b)&=a\uparrow \uparrow \uparrow {b} ,\\\ldots &\\H_{n}(a,b)&=a\uparrow ^{n-2}b{\text{ för }}n\geq 3,\\\ldots &\\\end {Justerat}}}$

Knuths notation skulle kunna utökas till negativa index ≥ −2 på ett sådant sätt att det överensstämmer med hela hyperoperationssekvensen, förutom fördröjningen i indexeringen:

$H_{n}(a,b)=a\uparrow ^{n-2}b{\text{ för }}n \geq 0.$

Hyperoperationerna kan alltså ses som ett svar på frågan "vad händer härnäst" i sekvensen : successor , addition , multiplikation , exponentiation , och så vidare. Noterar att

${\begin{aligned}a+b&=(a+(b-1))+1\\a\cdot b&=a+(a\cdot (b-1)) \\a^{b}&=a\cdot \left(a^{(b-1)}\right)\\a[4]b&=a^{a[4](b-1)}\end {Justerat}}$

sambandet mellan grundläggande aritmetiska operationer illustreras, vilket gör att de högre operationerna kan definieras naturligt enligt ovan. Parametrarna för hyperoperationshierarkin hänvisas ibland till med deras analoga exponentieringsterm; så a är basen , b är exponenten (eller hyperexponenten ), och n är rangen (eller betyget ), och dessutom läses $H_{n}(a,b)$ som "den b: te n -ationen av a ", t.ex. $H_{4}(7,9)$ läses som "den 9:e tetrationen av 7", och $H_{123}(456 789)$ läses som "den 789:e 123-ationen av 456".

I vanliga termer är hyperoperationerna sätt att sammansätta siffror som ökar i tillväxt baserat på iterationen av den tidigare hyperoperationen. Begreppen efterföljare, addition, multiplikation och exponentiering är alla hyperoperationer; efterföljande operationen (producerar x + 1 från x ) är den mest primitiva, additionsoperatorn anger antalet gånger 1 ska adderas till sig själv för att producera ett slutvärde, multiplikation anger antalet gånger ett tal ska adderas till sig själv, och exponentiering hänvisar till antalet gånger ett tal ska multipliceras med sig självt.

Definition, med iteration

Definiera iteration av en funktion f av två variabler som

$f^{x}(a,b) ={\begin{cases}f(a,b)&{\text{if }}x=1\\f(a,f^{x-1}(a,b))&{\text{if } }x>1\end{cases}}$

Hyperoperationssekvensen kan definieras i termer av iteration enligt följande. För alla heltal $x,n,a,b\geq 0,$ definiera

${\begin{array} {lcl}H_{0}(a,b)&=&b+1\\H_{1}(a,0)&=&a\\H_{2}(a,0)&=&0\\H_{n +3}(a,0)&=&1\\H_{n+1}(a,b+1)&=&H_{n}^{b+1}(a,H_{n+1}(a, 0))\\H_{n}^{x+2}(a,b)&=&H_{n}(a,H_{n}^{x+1}(a,b))\end{array} }$

Eftersom iteration är associativ kan den sista raden ersättas med

${\begin{array}{lcl}H_{n}^{x+2}( a,b)&=&H_{n}^{x+1}(a,H_{n}(a,b))\end{array}}$

Beräkning

Definitionerna av hyperoperationssekvensen kan naturligtvis överföras till termomskrivningssystem (TRS) .

TRS baserat på definition under 1.1

Den grundläggande definitionen av hyperoperationssekvensen motsvarar reduktionsreglerna

${\begin{array}{lll}{\text{(r1)}}&H(0,a,b)&\högerpil &S(b)\\{\text{(r2)} }&H(S(0),a,0)&\högerpil &a\\{\text{(r3)}}&H(S(S(0)),a,0)&\högerpil &0\\{\text {(r4)}}&H(S(S(S(n))),a,0)&\högerpil &S(0)\\{\text{(r5)}}&H(S(n),a, S(b))&\högerpil &H(n,a,H(S(n),a,b))\end{array}}$

För att beräkna $H_{n}(a,b)$ kan man använda en stack , som initialt innehåller elementen $\langle n,a,b \rangle$ .

Sedan, upprepade gånger tills det inte längre är möjligt, öppnas tre element och ersätts enligt reglerna

${\begin{array}{lllllllll}{\text{(r1)}}&0&,&a&,&b&\ högerpil &(b+1)\\{\text{(r2)}}&1&,&a&,&0&\högerpil &a\\{\text{(r3)}}&2&,&a&,&0&\högerpil &0\\{\text {(r4)}}&(n+3)&,&a&,&0&\högerpil &1\\{\text{(r5)}}&(n+1)&,&a&,&(b+1)&\högerpil &n&,&a&,&(n+1)&,&a&,&b\end{array}}$

Schematiskt, med start från $\langle n,a,b\rangle$ :

 WHILE  stackLength <> 1 {  POP  3 element;  PUSH  1 eller 5 element enligt reglerna r1, r2, r3, r4, r5; }  

Exempel

Beräkna $H_{2}(2,2)\rightarrow _{*}4$ .

Reduktionssekvensen är

${\underline {H(S(S(0)),S(S(0)),S (S(0)))}}$

${\ displaystyle \rightarrow _{r5}H(S(0),S(S(0)),{\underline {H(S(S(0)),S(S(0)),S(0))} })}$

$\rightarrow _{r5}H(S(0),S(S(0)),H(S(0),S(S(0)),{\understryka {H(S(S) (0)),S(S(0)),0)}}))$

$\rightarrow _{r3}H(S(0),S(S(0)),{\underline {H(S(0),S(S(0)),0)}})$

$\rightarrow _{r2}{\underline {H(S(0),S(S(0) )),S(S(0)))}}$

$\ högerpil _{r5}H(0,S(S(0)),{\understryka {H(S(0),S(S(0)),S(0))}})$

$,{\understryka {H(S(0),S(S(0)),0)}}))}$

${\displaystyle \rightarrow _{r5}H(0,S( S(0)),H(0,S(S(0)$

$\rightarrow _{r2}H(0,S(S(0)),{\underline {H(0,S(S(0)),S(S(0)))}})$

$displaystyle \rightarrow _{r1}{\understryka {H(0,S(S(0)),S(S(S(0))))}}} → r$

${$

$\rightarrow _{r1}S(S(S(S(0))))$

När det implementeras med en stack, på ingång $\langle 2,2,2\rangle$

stackkonfigurationerna	representera ekvationerna
${\underline {2,2,2}}$	$H_{2}(2,2)$
$\rightarrow _{r5}1,2,{\underline {2,2,1}}$	$=H_{1}(2,H_{2}(2,1))$
$\rightarrow _{r5}1,2,1,2,{\underline {2,2,0}}$	$=H_{1}(2,H_{1}(2,H_{2}(2,0)))$
$\rightarrow _{r3}1,2,{\underline {1,2,0}}$	$=H_{1}(2,H_{1}(2,0))$
$\rightarrow _{r2}{\underline {1,2,2}}$	$=H_{1}(2,2)$
$\rightarrow _{r5}0,2,{\underline {1,2,1}}$	$=H_{0}(2,H_{1}(2,1))$
$\rightarrow _{r5}0,2,0,2,{\underline {1,2,0}}$	$=H_{0}(2,H_{0}(2,H_{1}(2,0)))$
$\rightarrow _{r2}0,2,{\underline {0,2,2}}$	$=H_{0}(2,H_{0}(2,2))$
$\rightarrow _{r1}{\underline {0,2,3}}$	$=H_{0}(2,3)$
$\rightarrow _{r1}4$	$=4$

TRS baserat på definition under 1.2

Definitionen med iteration leder till en annan uppsättning reduktionsregler

${\begin{array}{lll}{\text{(r6)}}&H(S (0),0,a,b)&\högerpil &S(b)\\{\text{(r7)}}&H(S(0),S(0),a,0)&\högerpil &a\\ {\text{(r8)}}&H(S(0),S(S(0)),a,0)&\högerpil &0\\{\text{(r9)}}&H(S(0), S(S(S(n))),a,0)&\högerpil &S(0)\\{\text{(r10)}}&H(S(0),S(n),a,S(b) ))&\högerpil &H(S(b),n,a,H(S(0),S(n),a,0))\\{\text{(r11)}}&H(S(S( x)),n,a,b)&\högerpil &H(S(0),n,a,H(S(x),n,a,b))\end{array}}$

Eftersom iteration är associativ kan man istället för regel r11 definiera

${\begin {array}{lll}{\text{(r12)}}&H(S(S(x)),n,a,b)&\högerpil &H(S(x),n,a,H(S(0) ),n,a,b))\end{array}}$

Liksom i föregående avsnitt är beräkningen av $H_{n}(a,b)=H_{n}^{1}(a,b)$ kan implementeras med en stack.

Till att börja med innehåller stacken de fyra elementen $\langle 1,n,a,b\rangle$ .

Sedan, tills det avslutas, skjuts fyra element ut och ersätts enligt reglerna

${\begin{array}{lllllllll}{\text{(r6)}}&1&,0&,a&,b& \rightarrow &(b+1)\\{\text{(r7)}}&1&,1&,a&,0&\rightarrow &a\\{\text{(r8)}}&1&,2&,a&,0&\rightarrow &0 \\{\text{(r9)}}&1&,(n+3)&,a&,0&\högerpil &1\\{\text{(r10)}}&1&,(n+1)&,a&,(b +1)&\högerpil &(b+1)&,n&,a&,1&,(n+1)&,a&,0\\{\text{(r11)}}&(x+2)&,n& ,a&,b&\högerpil &1&,n&,a&,(x+1)&,n&,a&,b\end{array}}$

Schematiskt, med start från $\langle 1,n,a,b\rangle$ :

 WHILE  stackLength <> 1 {  POP  4 element;  PUSH  1 eller 7 element enligt reglerna r6, r7, r8, r9, r10, r11; }  

Exempel

Beräkna $H_{3}(0,3)\rightarrow _{*}0$ .

På ingång $\langle 1,3,0,3\rangle$ är de successiva stackkonfigurationerna

$displaystyle {\begin{aligned}&{\underline {1,3,0,3}}\rightarrow _{r10}3,2,0,{\underline {1,3,0,0}}\rightarrow _{r9}{\underline {3,2,0 ,1}}\rightarrow _{r11}1,2,0,{\underline {2,2,0,1}}\rightarrow _{r11}1,2,0,1,2,0,{\underline {1,2,0,1}}\\&\rightarrow _{r10}1,2,0,1,2,0,1,1,0,{\underline {1,2,0,0}} \rightarrow _{r8}1,2,0,1,2,0,{\underline {1,1,0,0}}\rightarrow _{r7}1,2,0,{\underline {1,2 ,0,0}}\rightarrow _{r8}{\underline {1,2,0,0}}\rightarrow _{r8}0.\end{aligned}}}$

Motsvarande jämlikheter är

${\begin{aligned}&H_{3}(0,3)=H_{2}^{3}(0,H_{3}(0,0 ))=H_{2}^{3}(0,1)=H_{2}(0,H_{2}^{2}(0,1))=H_{2}(0,H_{2} (0,H_{2}(0,1))\\&=H_{2}(0,H_{2}(0,H_{1}(0,H_{2}(0,0))))) =H_{2}(0,H_{2}(0,H_{1}(0,0)))=H_{2}(0,H_{2}(0,0))=H_{2}( 0,0)=0.\end{aligned}}$

När reduktionsregeln r11 ersätts med regeln r12, transformeras stacken i enlighet med

${\begin{array}{llllllll}{\text{(r12 )}}&(x+2)&,n&,a&,b&\högerpil &(x+1)&,n&,a&,1&,n&,a&,b\end{array}}$

De successiva stackkonfigurationerna blir då

${\begin{aligned}&{\underline {1,3,0,3}}\rightarrow _{r10}3,2,0,{\underline {1,3,0,0}}\rightarrow _{r9}{\underline {3,2,0,1}}\rightarrow _{r12}2,2,0,{\underline {1,2,0,1}}\rightarrow _{r10}2,2,0,1,1,0,{\underline {1,2,0,0}}\\&\rightarrow _{r8}2,2,0,{\underline {1,1,0,0}}\rightarrow _{r7}{\underline {2,2,0,0}}\rightarrow _{r12}1,2,0,{\underline {1,2,0,0}}\rightarrow _{r8}{\underline {1,2,0,0}}\rightarrow _{r8}0\end{aligned}}$

Motsvarande jämlikheter är

${\begin{ aligned}&H_{3}(0,3)=H_{2}^{3}(0,H_{3}(0,0))=H_{2}^{3}(0,1)=H_{ 2}^{2}(0,H_{2}(0,1))=H_{2}^{2}(0,H_{1}(0,H_{2}(0,0)))\ \&=H_{2}^{2}(0,H_{1}(0,0))=H_{2}^{2}(0,0)=H_{2}(0,H_{2} (0,0))=H_{2}(0,0)=0\end{aligned}}$

Anmärkningar

• $H_{3}(0,3)=0$ är ett specialfall. Se nedan.
• Beräkningen av $H_{n}(a,b)$ enligt reglerna {r6 - r10, r11} är kraftigt rekursiv. Boven är den ordning i vilken iterationen utförs: $H^{n}(a,b)=H(a) ,H^{n-1}(a,b))$ . Den första $H$ försvinner först efter att hela sekvensen har vecklats ut. Till exempel $H_{4}(2,4)$ till 65536 i 2863311767 steg, det maximala rekursionsdjupet är 65534.
• Beräkningen enligt reglerna {r6 - r10, r12} är mer effektiv i det avseendet. Implementeringen av iterationen $H^{n}(a,b)$ som $H^{n-1} (a,H(a,b))$ efterliknar den upprepade exekveringen av en procedur H. Rekursionsdjupet, (n+1), matchar slingkapslingen. Meyer & Ritchie (1967) formaliserade denna korrespondens. Beräkningen av $H_{4}(2,4)$ enligt reglerna {r6-r10, r12} behöver också 2863311767 steg för att konvergera till 65536, men det maximala rekursionsdjupet är endast 5, eftersom tetration är den 5:e operatorn i hyperoperationssekvensen.
• Övervägandena ovan gäller endast rekursionsdjupet. Båda sätten att iterera leder till samma antal reduktionssteg, som involverar samma regler (när reglerna r11 och r12 anses vara "samma"). Som exemplet visar reduktionen av $H_{3}(0,3)$ i 9 steg: 1 X r7, 3 X r8, 1 X r9, 2 X r10, 2 X r11 /r12. Modus iterandi påverkar endast i vilken ordning reduktionsreglerna tillämpas.

Exempel

Nedan är en lista över de första sju (0:e till 6:e) hyperoperationerna ( 0⁰ definieras som 1).

n	Operation, H n ( a , b )	Definition	Namn	Domän
0	$1+b$ eller $a[0]b$	$1+\underbrace {1+1+1+\cdots +1+1+1} _{\displaystyle b{\ mbox{ kopior av 1}}}$	hyper0, inkrement, efterföljare , nollställning	Slumpmässig
1	$a+b$ eller $a[1]b$	$a+\underbrace {1+1+1+\cdots +1+1+1} _{\displaystyle b{\mbox { kopior av 1}}}$	hyper1, tillägg	Slumpmässig
2	$a\cdot b$ eller $a[2]b$	$\displaystyle \underbrace {a+a+a+\cdots +a+a+a} _{\displaystyle b{\mbox{ kopior av } }a}}$	hyper2, multiplikation	Slumpmässig
3	$a^{b}$ eller $a[3]b$	$\displaystyle \underbrace {a\cdot a\cdot a\cdot \;\cdots \;\cdot a\cdot a\cdot a} _ {\displaystyle b{\mbox{ kopior av }}a}}$	hyper3, exponentiering	b real, med några flervärdiga tillägg till komplexa tal
4	$^{b}a$ eller $a[4]b$	$\displaystyle \underbrace {a[3 ](a[3](a[3](\cdots [3](a[3](a[3]a))\cdots )))} _{\displaystyle b{\mbox{ kopior av }}a }}$	hyper4, tetration	a ≥ 0 eller ett heltal, b ett heltal ≥ −1 (med några föreslagna tillägg)
5	$a[5]b$	$\displaystyle \underbrace {a[4 ](a[4](a[4](\cdots [4](a[4](a[4]a))\cdots )))} _{\displaystyle b{\mbox{ kopior av }}a }}$	hyper5, pentation	a , b heltal ≥ −1
6	$a[6]b$	$\displaystyle \underbrace {a[5 ](a[5](a[5](\cdots [5](a[5](a[5]a))\cdots )))} _{\displaystyle b{\mbox{ kopior av }}a }}$	hyper6, hexation	a , b heltal ≥ −1

Speciella fall

Hn _b (0, ) =

b + 1, när n = 0

b , när n = 1

0, när n = 2

1, när n = 3 och b = 0

0, när n = 3 och b > 0

1, när n > 3 och b är jämnt (inklusive 0)

0, när n > 3 och b är udda

Hn ₍ 1, b ) =

b , när n = 2

1, när n ≥ 3

Hn ₍ a , 0) =

0, när n = 2

1, när n = 0, eller n ≥ 3

a , när n = 1

Hn ₍ a , 1) =

a, när n ≥ 2

Hn ₍ a , a ) =

Hn ₊₁ ( a , 2), när n ≥ 1

H _n ( a , -1) =

0, när n = 0, eller n ≥ 4

a − 1, när n = 1

− a , när n = 2

1 / a , när n = 3

Hn ₍ 2,2) =

3, när n = 0

4, när n ≥ 1, lätt påvisbar rekursivt.

Historia

En av de tidigaste diskussionerna om hyperoperationer var den av Albert Bennett 1914, som utvecklade en del av teorin om kommutativa hyperoperationer (se nedan ). Cirka 12 år senare Wilhelm Ackermann funktionen $\phi (a,b,n)$ som något liknar hyperoperationssekvensen.

I sin artikel från 1947 introducerade Reuben Goodstein den specifika sekvensen av operationer som nu kallas hyperoperationer , och föreslog också de grekiska namnen tetration , pentation, etc., för de utökade operationerna bortom exponentiering (eftersom de motsvarar indexen 4, 5, etc. .). Som en funktion med tre argument, t.ex. ${\displaystyle G(n,a,b)=H_{n}(a,b)} ,$ hyperoperationen sekvensen som helhet ses vara en version av den ursprungliga Ackermann-funktionen $\phi (a,b,n)$ — rekursiv men inte primitiv rekursiv — som modifierad av Goodstein för att inkorporera primitiv efterföljare fungerar tillsammans med de andra tre grundläggande aritmetikens operationer ( addition , multiplikation , exponentiering ), och att göra en mer sömlös förlängning av dessa bortom exponentiering.

Den ursprungliga Ackermann-funktionen $\phi$ använder samma rekursionsregel som Goodsteins version av den (dvs hyperoperationssekvensen), men skiljer sig från den på två sätt. Först $\phi (a,b,n)$ en sekvens av operationer som börjar från addition ( n = 0) snarare än efterföljarfunktionen , sedan multiplikation ( n = 1), exponentiering ( n = 2), etc. För det andra resulterar initialvillkoren för ${\displaystyle \phi } i$${\displaystyle \phi (a,b,3)=G(4,a,b+1)=a[4](b+1)} , vilket skiljer sig från hyperoperationerna bortom exponentiering$ . Betydelsen av b + 1 i föregående uttryck är att $\phi (a,b,3)$ = $a^{a^{ \cdot ^{\cdot ^{\cdot ^{a}}}}}$ , där b räknar antalet operatorer (exponentieringar), snarare än att räkna antalet operander ("a"s) som b i $a[4]b$ och så vidare för operationer på högre nivå. (Se Ackermanns funktionsartikel för detaljer.)

Noteringar

Detta är en lista över notationer som har använts för hyperoperationer.

namn	Notation motsvarande $H_{n}(a,b)$	Kommentar
Knuths upp-pil notation	$a\uparrow ^{n-2}b$	Används av Knuth (för n ≥ 3), och finns i flera uppslagsböcker.
Hilberts notation	$\phi _{n}(a,b)$	Används av David Hilbert .
Goodsteins notation	$G(n,a,b)$	Används av Reuben Goodstein .
Original Ackermann funktion	${\begin{matrix}\phi (a,b,n- 1)\ {\text{ för }}1\leq n\leq 3\\\phi (a,b-1,n-1)\ {\text{ för }}n\geq 4\end{matris}}$	Används av Wilhelm Ackermann (för n ≥ 1)
Ackermann–Péter funktion	$A(n,b-3)+3\ {\text{för }}a=2$	Detta motsvarar hyperoperationer för bas 2 ( a = 2)
Nambiars notation	$a\otimes ^{n-1}b$	Används av Nambiar (för n ≥ 1)
Upphöjd notation	$a{}^{(n)}b$	Används av Robert Munafo.
Subscript notation (för lägre hyperoperationer)	$a{}_{(n)}b$	Används för lägre hyperoperationer av Robert Munafo.
Operatörsbeteckning (för "extended operations")	$aO_{n-1}b$	Används för lägre hyperoperationer av John Doner och Alfred Tarski (för n ≥ 1).
Notation med fyrkantsparentes	$a[n]b$	Används i många onlineforum; bekvämt för ASCII .
Conway kedjad pil notation	$a\to b\to (n-2)$	Används av John Horton Conway (för n ≥ 3)

Variant från a

Huvudartikel: Ackermann-funktion

År 1928 definierade Wilhelm Ackermann en 3-argumentfunktion $\phi (a,b,n)$ som gradvis utvecklades till en 2-argumentfunktion känd som Ackermann-funktionen . Den ursprungliga Ackermann-funktionen $\phi$ var mindre lik moderna hyperoperationer, eftersom hans initiala villkor börjar med $\phi (a,0,n)=a$ för alla n > 2. Han tilldelade också addition till n = 0, multiplikation till n = 1 och exponentiering till n = 2, så de initiala förhållandena producerar mycket olika operationer för tetration och därefter.

n	Drift	Kommentar
0	$F_{0}(a,b)=a+b$
1	$F_{1}(a,b)=a\cdot b$
2	$F_{2}(a,b)=a^{b}$
3	$F_{3}(a,b)=a[4](b+1)$	En offset form av tetration . Iterationen av denna operation är annorlunda än iterationen av tetration.
4	$F_{4}(a,b)=(x\mapsto a[4](x+1 ))^{b}(a)$	Ej att förväxla med pentation .

Ett annat initialvillkor som har använts är $A(0,b)=2b+1$ (där basen är konstant $a=2$ ), på grund av Rózsa Péter, som inte bildar en hyperoperationshierarki.

Variant från 0

1984 inledde CW Clenshaw och FWJ Olver diskussionen om att använda hyperoperationer för att förhindra översvämningar med flyttal . Sedan dess har många andra författare förnyat intresset för tillämpningen av hyperoperationer på flyttalsrepresentation . (Eftersom Hn _diskuterade ( a , b ) alla är definierade för b = -1.) Medan vi diskuterade tetration , Clenshaw et al. antog initialvillkoret $F_{n}(a,0)=0$ , vilket gör ännu en hyperoperationshierarki. Precis som i den tidigare varianten är den fjärde operationen väldigt lik tetration , men kompenseras med en.

n	Drift	Kommentar
0	$F_{0}(a,b)=b+1$
1	$F_{1}(a,b)=a+b$
2	$F_{2}(a,b)=a\cdot b=e^{\ln(a) +\ln(b)}$
3	$F_{3}(a,b)=a^{b}$
4	$F_{4}(a,b)=a[4](b-1)$	En offset form av tetration . Iterationen av denna operation är mycket annorlunda än iterationen av tetration .
5	$F_{5}(a,b)=\left(x\mapsto a[4 ](x-1)\höger)^{b}(0)=0{\text{ if }}a>0$	Ej att förväxla med pentation .

Lägre hyperoperationer

Ett alternativ för dessa hyperoperationer erhålls genom utvärdering från vänster till höger. Eftersom

${\begin{ aligned}a+b&=(a+(b-1))+1\\a\cdot b&=(a\cdot (b-1))+a\\a^{b}&=\left(a^{ (b-1)}\right)\cdot a\end{aligned}}$

definiera (med ° eller nedsänkt)

$a_{(n+1)}b=\left(a_{(n+1)}( b-1)\right)_{(n)}a$

med

${\begin{aligned}a_{(1)}b&=a+b\\a_{( 2)}0&=0\\a_{(n)}1&=a&{\text{för }}n>2\\\end{aligned}}$

Detta utökades till ordningstal av Doner och Tarski, av:

${\begin{aligned}\alpha O_{0}\beta &=\alpha +\beta \\\alpha O_{\gamma }\beta &=\sup \limits _{\eta <\beta ,\xi <\gamma }(\alpha O_{\gamma }\eta )O_{\xi } \alpha \end{aligned}}$

Det följer av definition 1(i), konsekvens 2(ii) och sats 9, att för a ≥ 2 och b ≥ 1, att

$aO_{n}b=a_{(n+1)}b$

Men detta lider av ett slags kollaps, och misslyckas med att bilda det "krafttorn" som traditionellt förväntas av hyperoperatörer:

$\alpha _{(4)}(1+\beta )=\alpha ^{\left(\alpha ^{\beta}\right)}.$

Om α ≥ 2 och γ ≥ 2, ^{[Korollary 33(i)]}

$\alpha _{(1+2\gamma +1)}\beta \leq \alpha _{(1+2\gamma )}(1+3\alpha \beta ).$

n	Drift	Kommentar
0	$F_{0}(a,b)=a+1$	inkrement, efterföljare, zeration
1	$F_{1}(a,b)=a+b$
2	$F_{2}(a,b)=a\cdot b$
3	$F_{3}(a,b)=a^{b}$
4	$F_{4}(a,b)=a^{\left(a^{(b-1)}\right)}$	Ej att förväxla med tetration .
5	$F_{5}(a,b)=\left(x\mapsto x^{x^{ (a-1)}}\höger)^{b-1}(a)$	Ej att förväxla med pentation . Liknar tetration .

Kommutativa hyperoperationer

Kommutativa hyperoperationer övervägdes av Albert Bennett så tidigt som 1914, vilket möjligen är den tidigaste anmärkningen om någon hyperoperationssekvens. Kommutativa hyperoperationer definieras av rekursionsregeln

$F_{n+1}(a,b)=\exp(F_{n }(\ln(a),\ln(b)))$

som är symmetrisk i a och b , vilket betyder att alla hyperoperationer är kommutativa. Denna sekvens innehåller inte exponentiering och bildar därför ingen hyperoperationshierarki.

n	Drift	Kommentar
0	$F_{0}(a,b)=\ln \left(e^{a}+e^{b}\right)$	Smidigt max
1	$F_{1}(a,b)=a+b$
2	$F_{2}(a,b)=a\cdot b=e^{\ln(a) +\ln(b)}$	Detta beror på egenskaperna hos logaritmen .
3	$F_{3}(a,b)=a^{\ln(b)}=e ^{\ln(a)\ln(b)}$
4	$F_{4}(a,b)=e^{e^{\ln( \ln(a))\ln(\ln(b))}}$	Ej att förväxla med tetration .

Numreringssystem baserade på hyperoperationssekvensen

RL Goodstein använde sekvensen av hyperoperatorer för att skapa numereringssystem för de icke-negativa heltalen. Den så kallade fullständiga ärftliga representationen av heltal n , på nivå k och bas b , kan uttryckas på följande sätt med endast de första k hyperoperatorerna och med endast 0, 1, ..., b − 1 som siffror tillsammans med basen b själv:

• För 0 ≤ n ≤ b − 1 representeras n helt enkelt av motsvarande siffra.
• För n > b − 1 hittas representationen av n rekursivt, först representerar n i formen

b [ k ] x _k [ k − 1] x _{k − 1} [ k - 2] ... [2] x ₂ [1] x ₁

där x _k , ..., x ₁ är de största heltal som uppfyller (i sväng)

b [ k ] x _k ≤ n

b [ k ] x _k [ k − 1] x _{k − 1} ≤ n

...

b [ k ] x _k [ k − 1] x _{k − 1} [ k - 2] ... [2] x ₂ [1] x ₁ ≤ n

Alla x _i som överstiger b − 1 återuttrycks sedan på samma sätt, och så vidare, upprepa denna procedur tills den resulterande formen endast innehåller siffrorna 0, 1 , ..., b − 1, tillsammans med basen b .

Onödiga parenteser kan undvikas genom att ge operatörer på högre nivå högre prioritet i utvärderingsordningen; Således,

nivå-1 representationer har formen b [1] X, med X också av denna form;

nivå-2 representationer har formen b [2] X [1] Y, med X , Y också av denna form;

nivå-3 representationer har formen b [3] X [2] Y [1] Z, med X , Y , Z också av denna form;

nivå-4 representationer har formen b [4] X [3] Y [2] Z [1] W, med X , Y , Z , W också av denna form;

och så vidare.

I denna typ av bas- b ärftlig representation förekommer själva basen i uttrycken, liksom "siffror" från mängden {0, 1, ..., b − 1}. Detta kan jämföras med vanlig bas-2-representation när den senare skrivs ut i termer av basen b ; t.ex. i vanlig bas-2-notation, 6 = (110) ₂ = 2 [3] 2 [2] 1 [1] 2 [3] 1 [2] 1 [1] 2 [3] 0 [2] 0, medan nivå-3 bas-2 ärftlig representation är 6 = 2 [3] (2 [3] 1 [2] 1 [1] 0) [2] 1 [1] (2 [3] 1 [2] 1 [ 1] 0). De ärftliga representationerna kan förkortas genom att utelämna alla instanser av [1] 0, [2] 1, [3] 1, [4] 1, etc.; till exempel, ovan nivå-3 bas-2 representation av 6 förkortar till 2 [3] 2 [1] 2.

Exempel: De unika bas-2-representationerna av talet 266 på nivåerna 1, 2, 3, 4 och 5 är följande:

Nivå 1: 266 = 2 [1] 2 [1] 2 [1] ... [1] 2 (med 133 2s)

Nivå 2: 266 = 2 [2] (2 [2] (2 [2] (2) [2] 2 [2] 2 [2] 2 [2] 2 [1] 1)) [1] 1) Nivå 3: 266

= 2 [3] 2 [3] (2 [1] 1) [1] 2 [3] (2 [1] 1) [1] 2

Nivå 4: 266 = 2 [4] (2 [1] 1) [3] 2 [1] 2 [4] 2 [2] 2 [1] 2

Nivå 5: 266 = 2 [5] 2 [4] 2 [1] 2 [5] 2 [2] 2 [1] 2

Se även

• Stora nummer

Bibliografi

•   Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen" . Matematiska Annalen . 99 : 118–133. doi : 10.1007/BF01459088 . S2CID 123431274 .

•   Bennett, Albert A. (dec 1915). "Anteckning om en operation av tredje klass". Annals of Mathematics . Andra serien. 17 (2): 74–75. doi : 10.2307/2007124 . JSTOR 2007124 .

•   Bezem, Marc; Klop, Jan Willem; De Vrijer, Roel (2003). "Första ordningens termomskrivningssystem". Term Rewriting Systems av "Terese" . Cambridge University Press. s. 38–39. ISBN 0-521-39115-6 .

• Black, Paul E. (2009-03-16). "Ackermanns funktion" . Ordbok över algoritmer och datastrukturer . US National Institute of Standards and Technology (NIST) . Hämtad 2021-08-29 .

• Campagnola, Manuel Lameiras; Moore, Cristopher ; Félix Costa, José (dec 2002). "Transfinita ordinaler i rekursiv talteori" . Journal of Complexity . 18 (4): 977–1000. doi : 10.1006/jcom.2002.0655 .

•   Clenshaw, CW; Olver, FWJ (april 1984). "Bortom flytande punkt". Journal of the ACM . 31 (2): 319–328. doi : 10.1145/62.322429 . S2CID 5132225 .

•   Cornelius, BJ; Kirby, GH (1975). "Rekursionsdjup och ackermannfunktionen". BIT Numerisk matematik . 15 (2): 144–150. doi : 10.1007/BF01932687 . S2CID 120532578 .

• Cowles, J.; Bailey, T. (1988-09-30). "Flera versioner av Ackermanns funktion" . Inst. för datavetenskap, University of Wyoming, Laramie, WY . Hämtad 2021-08-29 .

• Doner, John; Tarski, Alfred (1969). "En utökad aritmetik av ordningstal" . Fundamenta Mathematicae . 65 : 95–127. doi : 10.4064/fm-65-1-95-127 .

• Friedman, Harvey M. (juli 2001). "Långa ändliga sekvenser" . Journal of Combinatorial Theory . Serie A. 95 (1): 102–144. doi : 10.1006/jcta.2000.3154 .

• Galidakis, IN (2003). "Matematik" . Arkiverad från originalet den 20 april 2009 . Hämtad 2009-04-17 .

• Geisler, Daniel (2003). "Vad ligger bortom exponentieringen?" . Hämtad 2009-04-17 .

•    Goodstein, Reuben Louis (dec 1947). "Transfinita ordinaler i rekursiv talteori". Journal of Symbolic Logic . 12 (4): 123–129. doi : 10.2307/2266486 . JSTOR 2266486 . S2CID 1318943 .

•   Hilbert, David (1926). "Über das Unendliche". Matematiska Annalen . 95 : 161–190. doi : 10.1007/BF01206605 . S2CID 121888793 .

• Holmes, WN (mars 1997). "Komposit aritmetik: Förslag till en ny standard" . Dator . 30 (3): 65–73. doi : 10.1109/2.573666 . Hämtad 2009-04-21 .

•    Knuth, Donald Ervin (dec 1976). "Mathematics and Computer Science: Coping with Finiteness" . Vetenskap . 194 (4271): 1235–1242. Bibcode : 1976Sci...194.1235K . doi : 10.1126/science.194.4271.1235 . PMID 17797067 . S2CID 1690489 . Hämtad 2009-04-21 .

•    Littlewood, JE (juli 1948). "Stora nummer". Matematisk tidning . 32 (300): 163–171. doi : 10.2307/3609933 . JSTOR 3609933 . S2CID 250442130 .

• Meyer, Albert R .; Ritchie, Dennis MacAlistair (1967). Komplexiteten i loopprogram . ACM '67: Proceedings of the 1967 22nd National Conference. doi : 10.1145/800196.806014 .

• Müller, Markus (1993). "Reihenalgebra" (PDF) . Hämtad 2021-11-06 .

• Munafo, Robert (1999a). "Versioner av Ackermanns funktion" . Stora siffror på MROB . Hämtad 2021-08-28 .

• Munafo, Robert (1999b). "Uppfinna nya operatörer och funktioner" . Stora siffror på MROB . Hämtad 2021-08-28 .

• Nambiar, KK (1995). "Ackermann-funktioner och transfinita ordinaler" . Tillämpade matematikbokstäver . 8 (6): 51–53. doi : 10.1016/0893-9659(95)00084-4 .

•    Pinkiewicz, T.; Holmes, N.; Jamil, T. (2000). "Design av en sammansatt aritmetisk enhet för rationella tal". Proceedings of the IEEE Southeast Con 2000. "Förberedelser för det nya millenniet" (kat. nr. 00CH37105) . IEEE:s förfarande. s. 245–252. doi : 10.1109/SECON.2000.845571 . ISBN 0-7803-6312-4 . S2CID 7738926 .

• Robbins, AJ (november 2005). "Tetrationens hem" . Arkiverad från originalet den 13 juni 2015 . Hämtad 2009-04-17 .

• Romerio, GF (2008-01-21). "Hyperoperationsterminologi" . Tetration Forum . Hämtad 2009-04-21 .

• Rubtsov, CA; Romerio, GF (december 2005). "Ackermanns funktion och ny aritmetisk operation" . Hämtad 2009-04-17 .

•   Weisstein, Eric W. (2003). CRC kortfattad encyklopedi av matematik, 2nd Edition . CRC Tryck. s. 127–128. ISBN 1-58488-347-2 .

•   Wirz, Marc (1999). "Karakterisera Grzegorczyk-hierarkin genom säker rekursion". CiteSeer. CiteSeerX 10.1.1.42.3374 . {{ citera journal }} : Citera journal kräver |journal= ( hjälp )

• Zimmermann, R. (1997). "Datoraritmetik: principer, arkitekturer och VLSI-design" (PDF) . Föreläsningsanteckningar, Integrated Systems Laboratory, ETH Zürich. Arkiverad från originalet (PDF) 2013-08-17 . Hämtad 2009-04-17 .

•   Zwillinger, Daniel (2002). CRC-standard matematiska tabeller och formler, 31:a upplagan . CRC Tryck. sid. 4. ISBN 1-58488-291-3 .