Knuths pijlomhoognotatie

In de wiskunde is Knuths pijlomhoognotatie een notatie voor erg grote natuurlijke getallen geïntroduceerd door Donald Knuth in 1976. Het idee is gebaseerd op herhaalde machtsverheffing op dezelfde manier als machtsverheffen herhaalde vermenigvuldiging is, en vermenigvuldiging herhaalde optelling is.

Inleiding

Vermenigvuldiging kan gedefinieerd worden als herhaalde optelling:

$a\times b=\underset{b\mathrm{k}\mathrm{o}\mathrm{p}\mathrm{i}\mathrm{e}\ddot{\mathrm{e}}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{n}a}{\underbrace{a+a+\dots +a}}$

en machtsverheffing kan gedefinieerd worden als herhaalde vermenigvuldiging:

$a^b=a\uparrow b=\underset{b\mathrm{k}\mathrm{o}\mathrm{p}\mathrm{i}\mathrm{e}\ddot{\mathrm{e}}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{n}a}{\underbrace{a\times a\times \dots \times a}}$

wat Knuth inspireerde tot de definitie van een 'dubbele pijl' operator voor herhaalde machtsverheffing of tetratie:

$a\uparrow \uparrow b=\underset{b\mathrm{k}\mathrm{o}\mathrm{p}\mathrm{i}\mathrm{e}\ddot{\mathrm{e}}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{n}a}{\underbrace{a_{}^{a^{{}^{.{}^{.{}^{.{}^a}}}}}}}=\underset{b\mathrm{k}\mathrm{o}\mathrm{p}\mathrm{i}\mathrm{e}\ddot{\mathrm{e}}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{n}a}{\underbrace{a_{}\uparrow a\uparrow \dots \uparrow a}}$

De bewerking moet hier en hieronder beschouwd worden van rechts naar links.

Volgens deze definitie geldt:

$3\uparrow \uparrow 2=3^3=27$

$3\uparrow \uparrow 3=3^{3^3}=3^{27}=7625597484987$

$3\uparrow \uparrow 4=3^{3^{3^3}}=3^{7625597484987}$

$3\uparrow \uparrow 5=3^{3^{3^{3^3}}}$

etc.

Dit leidt al snel tot heel grote getallen, maar Knuth stopte hier niet. Hij ging verder om een 'drievoudige pijl' operator voor herhaalde toepassing van de 'dubbele pijl' operator te definiëren (ook bekend als pentatie):

$a\uparrow \uparrow \uparrow b=\underset{b\mathrm{k}\mathrm{o}\mathrm{p}\mathrm{i}\mathrm{e}\ddot{\mathrm{e}}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{n}a}{\underbrace{a\uparrow \uparrow a\uparrow \uparrow \dots \uparrow \uparrow a}}$

gevolgd door een 'vierpijl' operator:

$a\uparrow \uparrow \uparrow \uparrow b=\underset{b\mathrm{k}\mathrm{o}\mathrm{p}\mathrm{i}\mathrm{e}\ddot{\mathrm{e}}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{n}a}{\underbrace{a\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow \dots \uparrow \uparrow \uparrow a}}$

enzovoorts. De algemene regel is dat een n-pijl operator uit te schrijven is in een reeks (n − 1)-pijl operatoren. Symbolisch,

$a\underset{n}{\underbrace{\uparrow \uparrow \dots \uparrow }}b=\underset{b\mathrm{k}\mathrm{o}\mathrm{p}\mathrm{i}\mathrm{e}\ddot{\mathrm{e}}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{n}a}{\underbrace{a\underset{n-1}{\underbrace{\uparrow \dots \uparrow }}a\underset{n-1}{\underbrace{\uparrow \dots \uparrow }}a\dots a\underset{n-1}{\underbrace{\uparrow \dots \uparrow }}a}}$

Voorbeelden:

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

$3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow 3\uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow 3\uparrow 3)=\underset{3\uparrow 3\uparrow 3\mathrm{k}\mathrm{o}\mathrm{p}\mathrm{i}\mathrm{e}\ddot{\mathrm{e}}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{n}3}{\underbrace{3_{}\uparrow 3\uparrow \dots \uparrow 3}}$$=\underset{\mathrm{7}\mathrm{.}\mathrm{6}\mathrm{2}\mathrm{5}\mathrm{.}\mathrm{5}\mathrm{9}\mathrm{7}\mathrm{.}\mathrm{4}\mathrm{8}\mathrm{4}\mathrm{.}\mathrm{9}\mathrm{8}\mathrm{7}\mathrm{k}\mathrm{o}\mathrm{p}\mathrm{i}\mathrm{e}\ddot{\mathrm{e}}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{n}\mathrm{3}}{\underbrace{3_{}\uparrow 3\uparrow \dots \uparrow 3}}$

Notatie

In uitdrukkingen zoals a^b, de notatie voor machtsverheffing, is het de gewoonte om de exponent b als een superscript van het grondtal a te schrijven.

De superscriptnotatie a^b leende zichzelf slecht voor generalisatie, wat verklaart waarom Knuth verkoos te werken met de notatie a↑b.

Definitie

De pijlomhoognotatie is formeel gedefinieerd door:

$a{\uparrow }^{n}b=\{\begin{array}{cc}1,& \text{als }b=0;\\ a^b,& \text{als }n=1;\\ a{\uparrow }^{n-1}(a{\uparrow }^n(b-1)),& \text{anders}\end{array}$

voor alle natuurlijke getallen a, b en n met b ≥ 0 en n ≥ 1.

Alle pijlomhoogoperatoren (inclusief normale machtsverheffing, a↑b) zijn rechts associatief, dat wil zeggen dat de waardebepaling plaatsvindt van rechts naar links in een uitdrukking die meer dan twee van zulke operatoren bevat. Bijvoorbeeld, a↑b↑c = a↑(b↑c), niet (a↑b)↑c; bijvoorbeeld
$3\uparrow \uparrow 3=3^{3^3}\text{ is }{3}^{(3^3)}=3^{27}=7.625.597.484.987\text{, niet }{\left(3^3\right)}^3=27^3=19.683$.

Voorbeeld bij definitie

$3\uparrow \uparrow \uparrow 2$

• $3\uparrow \uparrow (3\uparrow \uparrow \uparrow 1)$
• $3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow \uparrow 0))$
• $3\uparrow \uparrow (3\uparrow \uparrow 1)$
• $3\uparrow \uparrow (3\uparrow (3\uparrow \uparrow 0))$
• $3\uparrow \uparrow (3\uparrow 1)$
• $3\uparrow \uparrow (3^1)$

$3\uparrow \uparrow 3$

• $3\uparrow (3\uparrow \uparrow 2)$
• $3\uparrow (3\uparrow (3\uparrow \uparrow 1))$
• $3\uparrow (3\uparrow (3\uparrow (3\uparrow \uparrow 0)))$
• $3\uparrow (3\uparrow (3\uparrow 1))$

$3\uparrow (3\uparrow 3)$

• $3\uparrow (3^3)$
• $3\uparrow 27$
• $3^{27}$

$7.625.597.484.987$

Tabel met waarden

Berekening 2↑^m n

Waarden van $2{\uparrow }^{m}n$ = hyper(2, m+2, n) = 2 → n → m

m\n	1	2	3	4	5	6	7	formule
0	2	4	6	8	10	12	14	$2n$
1	2	4	8	16	32	64	128	$2^n$
2	2	4	16	65.536	$2^{65.536}$$\approx 2,0\times 10^{19.728}$	$2^{2^{65.536}}$$\approx 10^{6,0\times 10^{19.728}}$	$2^{2^{2^{65.536}}}$$\approx 10^{10^{6,0\times 10^{19.728}}}$	$2\uparrow \uparrow n$
3	2	4	65.536	$\underset{65.536\mathrm{k}\mathrm{o}\mathrm{p}\mathrm{i}\mathrm{e}\ddot{\mathrm{e}}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{n}2}{\underbrace{2^{2^{{}^{.{}^{.{}^{.{}^2}}}}}}}$$\approx (10\uparrow {)}^{65.531}(6,0\times 10^{19.728})$				$2\uparrow \uparrow \uparrow n$
4	2	4	$\underset{65.536\mathrm{k}\mathrm{o}\mathrm{p}\mathrm{i}\mathrm{e}\ddot{\mathrm{e}}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{n}2}{\underbrace{2^{2^{{}^{.{}^{.{}^{.{}^2}}}}}}}$					$2\uparrow \uparrow \uparrow \uparrow n$

Opmerking: $(10\uparrow {)}^k$ is de notatie voor een functionele macht van de functie $f(n)=10^n$, zodat

• $(10\uparrow {)}^1(n)=10^n$
• $(10\uparrow {)}^2(n)=10^{10^n}$

enzovoorts.

Berekening 3↑^m n

Waarden van $3{\uparrow }^{m}n$ = hyper(3, m+2, n) = 3 → n → m

m\n	1	2	3	4	5	formule
0	3	6	9	12	15	$3n$
1	3	9	27	81	243	$3^n$
2	3	27	7.625.597.484.987	$3^{7.625.597.484.987}$		$3\uparrow \uparrow n$
3	3	7.625.597.484.987	$\underset{7.625.597.484.987\mathrm{k}\mathrm{o}\mathrm{p}\mathrm{i}\mathrm{e}\ddot{\mathrm{e}}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{n}3}{\underbrace{3_{}^{3^{{}^{.{}^{.{}^{.{}^3}}}}}}}$			$3\uparrow \uparrow \uparrow n$
4	3	$\underset{7.625.597.484.987\mathrm{k}\mathrm{o}\mathrm{p}\mathrm{i}\mathrm{e}\ddot{\mathrm{e}}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{n}3}{\underbrace{3_{}^{3^{{}^{.{}^{.{}^{.{}^3}}}}}}}$				$3\uparrow \uparrow \uparrow \uparrow n$

Berekening 10↑^m n

Waarden van $10{\uparrow }^{m}n$ = hyper(10, m+2, n) = 10 → n → m

m\n	1	2	3	4	5	formule
0	10	20	30	40	50	$10n$
1	10	100	1000	10.000	100.000	$10^n$
2	10	10.000.000.000	$10^{10.000.000.000}$	$10^{10^{10.000.000.000}}$		$10\uparrow \uparrow n$
3	10	$\underset{10\mathrm{k}\mathrm{o}\mathrm{p}\mathrm{i}\mathrm{e}\ddot{\mathrm{e}}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{n}10}{\underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}}$				$10\uparrow \uparrow \uparrow n$
4	10					$10\uparrow \uparrow \uparrow \uparrow n$

Andere notatie en naam, en generalisatie

$a{\uparrow }^{n}b$ is een niet-dalende functie van de drie niet-negatieve gehele getallen $a$, $b$, $n$, met niet-negatieve geheeltallige functiewaarden die extreem sterk stijgen bij toenemende functiewaarden. De functie wordt ook geschreven als relatief eenvoudig geval (met slechts twee pijlen) van Conways geketende pijlnotatie, in dit geval $a\to b\to n$. Deze is ook gedefinieerd met meer pijlen, dit zijn ook niet-dalende functies van een aantal niet-negatieve gehele getallen, die nog sneller stijgen.

Zie ook

• getal van Graham
• Tetratie
• Ruckers notatie

Externe links

• MathWorld: Arrow Notatie
• Robert Munafo's Grote Getallen