Кнутова нотација

У математици, Кнутова нотација је нотација за записивање врло великих целих бројева. Увео ју је Доналд Кнут 1976. године. Идеја је заснована на поновљеном степеновању на сличан начин на који је степеновање поновљено множење, а множење је поновљено сабирање.

Увод

Множење природним бројем се може дефинисати као поновљено сабирање:

${\begin{matrix}ab&=&\underbrace {a_{} a \dots a} \\&&b{\mbox{ primeraka }}a\end{matrix}}$

а степеновање природним степеном $b$ се може дефинисати као поновљено множење:

${\begin{matrix}a\uparrow b=a^{b}=&\underbrace {a_{}\times a\times \dots \times a} \\&b{\mbox{ primeraka }}a\end{matrix}}$

што је инспирисало Кнута да дефинише оператор 'двоструке стрелице' за поновљено степеновање:

${\begin{matrix}a\uparrow \uparrow b&=&\underbrace {a_{}^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} &=&\underbrace {a_{}\uparrow a\uparrow \dots \uparrow a} \\&&b{\mbox{ primeraka }}a&&b{\mbox{ primeraka }}a\end{matrix}}$

Овде и надаље израчунавање се спроводи здесна улево (као таква, операција је десно асоцијативна):

Према овој дефиницији,

$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}}}}=3^{3^{7625597484987}}\,\!$

итд.

Ово већ води до прилично великих бројева, али Кнут је проширио своју нотацију. Дефинисао је оператор 'троструке стрелице' за поновљену примену оператора 'двоструке стрелице':

${\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow a\uparrow \uparrow \dots \uparrow \uparrow a} \\&b{\mbox{ primeraka }}a\end{matrix}}$

даље имамо оператор 'четири стрелице':

${\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow \dots \uparrow \uparrow \uparrow a} \\&b{\mbox{ primeraka }}a\end{matrix}}$

и тако даље. Опште правило је да се оператор $n$ стрелица разлаже у серију оператора $n-1$ стрелица. Симболички,

${\begin{matrix}a\ \underbrace {\uparrow _{}\uparrow \!\!\dots \!\!\uparrow } \ b=a\ \underbrace {\uparrow \!\!\dots \!\!\uparrow } \ a\ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } \ a\ \dots \ a\ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } \ a\\\quad \ \ \,n\qquad \ \ \ \underbrace {\quad n_{}\!-\!\!1\quad \ \,n\!-\!\!1\qquad \quad \ \ \ \,n\!-\!\!1\ \ \ } \\\qquad \qquad \quad \ \ b{\mbox{ primeraka }}a\end{matrix}}$

Примери:

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

${\begin{matrix}3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow 3\uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow 3\uparrow 3)=&\underbrace {3_{}\uparrow 3\uparrow \dots \uparrow 3} \\&3\uparrow 3\uparrow 3{\mbox{ primeraka }}3\end{matrix}}{\begin{matrix}=&\underbrace {3_{}\uparrow 3\uparrow \dots \uparrow 3} \\&{\mbox{7.625.597.484.987 primeraka 3}}\end{matrix}}$

Нотација

У изразима као што је $a^{b}$, нотација за степеновање обично подразумева да се експонент $b$ записује изнад са десне стране од базног броја $a$. Међутим, многа окружења – као што су програмски језици – не подржавају такав дводимензиони запис. Због тога је усвојена линеарна нотација $a\uparrow b$ за оваква окружења; стрелица нагоре представља 'дизање на степен'. Ако у скупу карактера не постоји стрелица нагоре, користи се симбол ^.

Нотација са записивањем експонента изнад броја који се диже на степен, $a^{b}$ није погодна за генерализацију, што објашњава зашто је Кнут изабрао да ради са стрелицом нагоре, $a\uparrow b$.

У контексту програмског језика C, карактер ^ означава ексклузивно или XOR. ** је уобичајена алтернатива за $\uparrow$ па је у овом контексту могуће користити два симбола за понављање оператора. Могуће је узети да је *** еквивалентно са $\uparrow \uparrow$, али ова употреба није уобичајена.

Генерализације

Неки бројеви су толико велики да чак и запис са вишеструким стрелицама нагоре постаје прегломазан: тада је од користи оператор $n$-стрелица $\uparrow ^{n}$ (као и за описе са променљивим бројем стрелица), или еквивалентно, хипер оператори.

Неки бројеви су толико велики да ни оваква нотација није довољна. Пример за ово је Грејемов број. У овим случајевима се може користити Конвејева ланчана нотација: ланац од три елемента је еквивалентан осталим нотацијама, али ланац од четири елемента је још већи.

${\begin{matrix}a\uparrow ^{n}b&=&{\mbox{hyper}}(a,n 2,b)&=&a\to b\to n\\{\mbox{(Knut)}}&&&&{\mbox{(Konvej)}}\end{matrix}}$

Обично се Кнутова нотација користи за бројеве релативно мање магнитуде, а ланчане стрелице или хипер оператори за веће бројеве.

Дефиниција

Кнутова нотација се формално дефинише на следећи начин

$a\uparrow ^{n}b=\left\{{\begin{matrix}a^{b},&{\mbox{ako }}n=1;\\1,&{\mbox{ako }}b=0;\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1)),&{\mbox{u suprotnom}}\end{matrix}}\right.$

за све целе бројеве $a,b,n$ и $b\geq 0,n\geq 1$.

Сви оператори стрелице нагоре (укључујући класично степеновање, $a\uparrow b$) су десно асоцијативни, то јест, израчунавање се спроводи здесна улево уколико израз садржи два или више таквих оператора. На пример, $a\uparrow b\uparrow c=a\uparrow (b\uparrow c)$, не $(a\uparrow b)\uparrow c$; на пример
$3\uparrow \uparrow 3=3^{3^{3}}$ је $3^{(3^{3})}=3^{27}=7625597484987$ а не $\left(3^{3}\right)^{3}=27^{3}=19683.$

Постоји добар разлог зашто је изабран овакав редослед израчунавања. Да је коришћено израчунавање слева удесно, тада би $a\uparrow \uparrow b$ било једнако $a\uparrow (a\uparrow (b-1))$, па $\uparrow \uparrow$ суштински не би било нова операција. Десна асоцијативност је такође природна јер можемо да препишемо поновљени са стрелицама $a\uparrow ^{n}\cdots \uparrow ^{n}a$ који се понавља у развоју $a\uparrow ^{n 1}b$ као $a\uparrow ^{n}\cdots \uparrow ^{n}a\uparrow ^{n}1$, па је свако $a$ леви операнд оператора стрелице. Ово је значајно јер оператори стрелице нису комутативни.

Таблица вредности

Рачунање $2\uparrow ^{m}n$ се може записати у бесконачној таблици. Записујемо бројеве 2 $n$ у првој врсти, и пунимо десну колону вредностима 2. Како би се одредила нека вредност у таблици, узима се број одмах лево од ње, а затим се тражи број у претходној врсти на позицији означеној овим бројем.

Вредности $2\uparrow ^{m}n$ = хипер(2, m   2, n) = 2 → n → m

m\n	1	2	3	4	5	6	7	формула
0	2	4	6	8	10	12	14	$2n$
1	2	4	8	16	32	64	128	$2^{n}$
2	2	4	16	65536	$2^{65536}\approx 2,0\times 10^{19.729}$	$2^{2^{65536}}\approx 10^{6,0\times 10^{19.728}}$	$2^{2^{2^{65536}}}\approx 10^{10^{6,0\times 10^{19.728}}}$	$2\uparrow \uparrow n$
3	2	4	65536	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\65536{\mbox{ primeraka }}2\end{matrix}}\approx (10\uparrow )^{65531}(6,0\times 10^{19.728})$				$2\uparrow \uparrow \uparrow n$
4	2	4	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\65536{\mbox{ primeraka }}2\end{matrix}}$					$2\uparrow \uparrow \uparrow \uparrow n$

Напомена: $(10\uparrow )^{k}$ означава функционални степен функције $f(n)=10^{n}$ (функција се такође означава суфиксом -плекс, као код гуголплекс).

Таблица је иста као код Акерманове функције, осим замене $m$ и $n$, и додатка 3 свим вредностима.

Рачунање $3\uparrow ^{m}n$

Ставимо бројеве 3 $n$ у горњу врсту, и попунимо леву колону тројкама. Како би одредили неку вредност у табели, узмемо број одмах лево до њега, и потражимо број у претходној врсти, на позицији коју означава број који смо узели.

Вредности $3\uparrow ^{m}n$ = хипер(3, m   2, n) = 3 → n → m

m\n	1	2	3	4	5	формула
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	${\begin{matrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}} \\7.625.597.484.987{\mbox{ primeraka }}3\end{matrix}}$			$3\uparrow \uparrow \uparrow n$
4	3	${\begin{matrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}} \\7.625.597.484.987{\mbox{ primeraka }}3\end{matrix}}$				$3\uparrow \uparrow \uparrow \uparrow n$

Рачунање $10\uparrow ^{m}n$

Попунимо прву врсту бројевима 10 $n$, а прву колону десеткама. Како би одредили неку вредност у табели узимамо број одмах лево до ове позиције, и потражимо број у претходној врсти, на позицији коју означава број који смо узели.

Вредности $10\uparrow ^{m}n$ = хипер(10, m   2, n) = 10 → n → m

m\n	1	2	3	4	5	формула
0	10	20	30	40	50	$10n$
1	10	100	1.000	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	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}} \\10{\mbox{ primeraka }}10\end{matrix}}$				$10\uparrow \uparrow \uparrow n$
4	10					$10\uparrow \uparrow \uparrow \uparrow n$

Види још

• Хипер оператор
• Вредни даброви
• Катлерова нотација

Спољашње везе

• Ерик В. Вајсштајн, Нотација стрелица на сајту MathWorld
• Роберт Мунафо, Велики бројеви