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

Из Википедије, слободне енциклопедије

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

Увод[уреди]

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


  \begin{matrix}
   a b & = & \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\uparrow2=3^3=27\,\!
3\uparrow\uparrow3=3^{3^3}=3^{27}=7625597484987\,\!
3\uparrow\uparrow4=3^{3^{3^3}}=3^{7625597484987}\,\! (у разложеном облику, овај број би попунио неколико повећих хард дискова[1])
3\uparrow\uparrow5=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\uparrow2=3\uparrow\uparrow3=3^{3^3}=3^{27}=7.625.597.484.987\,\!


  \begin{matrix}
    3\uparrow\uparrow\uparrow3 = 3\uparrow\uparrow3\uparrow\uparrow3 = 3\uparrow\uparrow(3\uparrow3\uparrow3) = &
    \underbrace{3_{}\uparrow 3\uparrow\dots\uparrow 3} \\
   & 3\uparrow3\uparrow3\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 \ge 0, n \ge 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^na који се понавља у развоју a \uparrow^{n + 1}b као a\uparrow^n\cdots\uparrow^na\uparrow^n1, па је свако 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

Види још[уреди]

Референце[уреди]

  1. ^ То јест 7.625.597.484.987 \times \frac{\log 3}{\log 2} битова, или око 1,4 TB

Спољашње везе[уреди]