Notasi anak panah atas Knuth

Dalam matematik, notasi anak panah atas Knuth ialah satu cara menulis integer yang sangat besar, yang diperkenalkan oleh Donald Knuth pada 1976. Ia berkait rapat dengan fungsi Ackermann terutamanya pada urutan hiperoperasi. Idea ini berdasarkan fakta bahawa pendaraban boleh dilihat sebagai penambahan berulang dan pengeksponenan boleh dilihat sebagai pendaraban berulang. Jika diteruskan begini, ia akan membawa kepada pengeksponenan berulang (tetrasi) dan kepada baki urutan hiperoperasi, yang biasanya ditulis dengan notasi anak panah Knuth. Dengan kata lain, notasi anak panah atas Knuth boleh digunakan untuk menulis nombor yang sangat besar di dalam ruang yang sangat kecil. Ia sangat berguna apabila nombor yang sangat besar disebut di dalam carta dan graf di mana ruang adalah terhad.

Pengenalan

Operasi aritmetik penambahan, pendaraban dan pengeksponenan biasanya dilanjutkan kepada satu urutan hiperoperasi seperti berikut.

Pendaraban dengan nombor asli ditakrifkan sebagai penambahan berulang:

$\begin{array}{ccc}a\times b& =& \underbrace{a+a+\dots +a}\\ & & b\text{ salinan bagi }a\end{array}$

Contohnya,

$\begin{array}{ccccc}4\times 3& =& \underbrace{4+4+4}& =& 12\\ & & 3\text{ salinan bagi }4\end{array}$

Pengeksponenan bagi kuasa asli $b$ ditakrifkan sebagai pendaraban berulang, yang digambarkan oleh Knuth dengan satu anak panah atas:

$\begin{array}{cc}a\uparrow b=a^b=& \underbrace{a\times a\times \dots \times a}\\ & b\text{ salinan bagi }a\end{array}$

Contohnya,

$\begin{array}{cccc}4\uparrow 3=4^3=& \underbrace{4\times 4\times 4}& =& 64\\ & 3\text{ salinan bagi }4\end{array}$

Untuk melanjutkan urutan operasi melangkaui pengeksponenan, Knuth mentakrifan satu pengendali "dua anak panah" untuk menandakan pengeksponenan berulang (tetrasi)

$\begin{array}{ccccc}a\uparrow \uparrow b& ={}^{b}a=& \underbrace{a^{a^{{}^{.{}^{.{}^{.{}^a}}}}}}& =& \underbrace{a\uparrow (a\uparrow (\dots \uparrow a))}\\ & & b\text{ salinan bagi }a& & b\text{ salinan bagi }a\end{array}$

Contohnya,

$\begin{array}{cccccccccc}4\uparrow \uparrow 3& ={}^{3}4=& \underbrace{4^{4^4}}& =& \underbrace{4\uparrow (4\uparrow 4)}& =& 4^{256}& \approx & 1.34078079\times 10^{154}& \\ & & 3\text{ salinan bagi }4& & 3\text{ salinan bagi }4\end{array}$

Penilalian di sini dan di bawah dibuat dari kanan ke kiri, kerana seperti pengekspenenan, pengendali anak panah Knuth adalah berkait ke kanan (right-associative).

Mengikut definisi ini,

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

$3\uparrow \uparrow 3=3^{3^3}=3^{27}=7,625,597,484,987$

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

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

dan sebagainya.

Ini sahaja sudah cukup untuk menghasilkan nombor-nombor yang besar, tetapi Knuth melanjutkan lagi notasi ini. Dia turut mentakrifkan pengendali "tiga anak panah" sebagai pengulangan aplikasi "dua anak panah" (yang juga dikenali sebagai pentasi):

$\begin{array}{cc}a\uparrow \uparrow \uparrow b=& \underbrace{a_{}\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))}\\ & b\text{ salinan bagi }a\end{array}$

diikuti dengan pengendali "empat anak panah" (juga dikenali sebagai heksasi):

$\begin{array}{cc}a\uparrow \uparrow \uparrow \uparrow b=& \underbrace{a_{}\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (\dots \uparrow \uparrow \uparrow a))}\\ & b\text{ salinan bagi }a\end{array}$

dan seterusnya. Peraturan amnya ialah satu pengendali $n$ anak panah berkembang menjadi satu siri perkaitan kanan pengendali $(n-1)$ anak panah.

$\begin{array}{c}a\underset{n}{\underbrace{{\uparrow }_{}\uparrow \dots \uparrow }}b=\underset{b\text{ salinan bagi }a}{\underbrace{a\underset{n-1}{\underbrace{\uparrow \dots \uparrow }}(a\underset{n-1}{\underbrace{{\uparrow }_{}\dots \uparrow }}(\dots \underset{n-1}{\underbrace{{\uparrow }_{}\dots \uparrow }}a))}}\end{array}$

Contohnya:

$3\uparrow \uparrow \uparrow 2=3\uparrow \uparrow 3=3^{3^3}=3^{27}=7,625,597,484,987$

$\begin{array}{cc}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\text{ salinan bagi }3\end{array}\begin{array}{cc}=& \underbrace{3_{}\uparrow 3\uparrow \dots \uparrow 3}\\ & \text{7,625,597,484,987 salinan bagi 3}\end{array}=\underset{7,625,597,484,987}{\underbrace{3^{3^{3^{3^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^3}}}}}}}}}$

Notasi $a{\uparrow }^{n}b$ biasanya digunakan untuk melambangkan $a\uparrow \uparrow \dots \uparrow b$ dengan $n$ anak panah.

Notasi

Dalam pernyataan seperti $a^b$, notasi bagi pengeksponenan biasanya ditulis dalam bentuk nombor eksponen $b$ ditulis dalam superskrip selepas nombor asas $a$. Tetapi dalam sesetengah keadaan — seperti di dalam bahasa pemprograman dan emel berteks biasa — tulisan superskrip tidak boleh digunakan. Kebanyakan orang telah menggunakan notasi linear $a\uparrow b$ dalam keadaan seperti ini; anak panah atas melambangkan "menaikkan ke kuasa ke-". Jika di dalam set karakter itu tidak mempunyai anak panah atas, tanda karet ^ digunakan sebagai ganti.

Notasi superskrip $a^b$ bukan bersifat terlalu umum, dan sebab inilah Knuth menggunakan notasi linear $a\uparrow b$.

Menulis notasi anak panah atas dalam terma kuasa (notasi superskrip)

Jika $a\uparrow \uparrow b$ ditulis dalam notasi superskrip yang biasa, ia akan menghasilkan apa yang dipanggil "menara kuasa".

Contohnya, $a\uparrow \uparrow 4=a\uparrow (a\uparrow (a\uparrow a))=a^{a^{a^a}}$

Jika $b$ ialah satu pembolehubah (ataupun ia terlalu besar), menara kuasa akan ditulis dengan titik-titik dan satu nota yang menunjukkan ketinggian menara itu.

$a\uparrow \uparrow b=\underset{b}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}$

Jika diteruskan dengan notasi ini, $a\uparrow \uparrow \uparrow b$ boleh ditulis sebagai satu susunan menara kuasa, setiap satu menunjukkan saiz menara diatasnya.

$a\uparrow \uparrow \uparrow 4=a\uparrow \uparrow (a\uparrow \uparrow (a\uparrow \uparrow a))=\underset{\underset{\underset{a}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}$

Sekali lagi, sekiranya $b$ ialah satu pembolehubah ataupun ia terlalu besar, susunan itu mungkin ditulis dengan titik-titik dan satu nota yang menunjukkan ketinggiannya.

$a\uparrow \uparrow \uparrow b=\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}b$

Tambahan lagi, $a\uparrow \uparrow \uparrow \uparrow b$ boleh ditulis sebagai beberapa susunan menara kuasa ini, setiap susunan menunjukkan ketinggian menara di sebelah kirinya.

$a\uparrow \uparrow \uparrow \uparrow 4=a\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow a))=\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}a$

Dan secara lebih am:

$a\uparrow \uparrow \uparrow \uparrow b=\underset{b}{\underbrace{\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\cdots \}a}}$

Ini boleh terus dilakukan untuk menggambarkan $a{\uparrow }^{n}b$ dalam bentuk pengeksponenan berulang bagi mana-mana nilai $a$, $n$ dan $b$ (walaupun dengan jelas ia akan memakan ruang).

Menggunakan tetrasi

Notasi tetrasi $b^{}a$ membolehkan kita untuk membuatkan gambar-gambar rajah ini lebih ringkas dan masih lagi mengekalkan perlambangan berbentuk geometri (kita boleh memanggilnya menara tetrasi).

$a\uparrow \uparrow b={}^{b}a$

$a\uparrow \uparrow \uparrow b=\underset{b}{\underbrace{{}^{{}^{{}^{{}^{{}^a.}.}.}a}a}}$

$a\uparrow \uparrow \uparrow \uparrow b=\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{{}^{{}^{{}^{{}^{{}^a.}.}.}a}a}}}{\underbrace{{}^{{}^{{}^{{}^{{}^a.}.}.}a}a}}\}b$

Akhir sekali, sebagai contoh, nombor Ackermann keempat, $4{\uparrow }^{4}4$, boleh ditulis sebagai

$\underset{\underset{\underset{4}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}=\underset{\underset{{}^{{}^{{}^{4}4}4}4}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}$

Generalisasi

Sesetengah nombor adalah terlalu besar sehinggakan beberapa anak panah di dalam notasi Knuth memakan terlalu banyak ruang. Dalam hal ini (dan juga dalam gambaran dengan jumlah anak panah yang berubah-ubah), pengendali $n$ anak panah ${\uparrow }^n$ adalah berguna. Pengendali hiper juga boleh digunakan.

Sesetengah nombor, seperti nombor Graham adalah terlalu besar sehinggakan notasi ini pun tidak memadai. Untuk ini, notasi anak panah berantai Conway boleh digunakan. Satu rantaian dengan tiga unsur adalah setara dengan notasi lain, tetapi satu rantaian dengan empat atau lebih unsur adalah lebih berkeupayaan.

$\begin{array}{ccccc}a{\uparrow }^{n}b& =& \text{hyper}(a,n+2,b)& =& a\to b\to n\\ \text{(Knuth)}& & & & \text{(Conway)}\end{array}$

Notasi anak panah Knuth biasanya dicadangkan untuk digunakan di dalam nombor yang lebih kecil, manakala notasi anak panah berantai atau pengendali hiper digunakan untuk nombor yang lebih besar.

Takrif

Notasi anak panah atas Knuth biasanya ditakrifkan dengan

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

untuk semua integer $a,b,n$ dengan $b\ge 0,n\ge 1$.

Kesemua pengendali anak panah atas (termasuk pengeksponenan biasa, $a\uparrow b$) adalah berkait ke kanan (right-associative), yakni pengiraan dilakukan dari kanan ke kiri di dalam satu ungkapan yang mengandungi dua atau lebih pengendali sebegini. Sebagai contoh, $a\uparrow b\uparrow c=a\uparrow (b\uparrow c)$ dan bukannya $(a\uparrow b)\uparrow c$; contohnya $3\uparrow \uparrow 3=3^{3^3}$ sama dengan $3^{(3^3)}=3^{2}7=7625597484987$, bukannya ${(3^3)}^3=27^3=19683$.

Ada sebab yang baik mengapa urutan pengiraan kanan ke kiri digunakan untuk pengendali ini. Jika urutan kiri ke kanan digunakan, $a\uparrow \uparrow b$ akan bersamaan dengan $a\uparrow (a\uparrow (b-1))$, dan tidak akan menjadikan $\uparrow \uparrow$ satu operasi yang baru. Perkaitan kanan juga adalah tepat kerana kita boleh menulis semula ungkapan anak panah berulang $a{\uparrow }^n{\dot{\dot{\dot{\uparrow }}}}^{n}a$ yang diperolehi daripada perkembangan $a{\uparrow }^{n+1}b$ sebagai $a{\uparrow }^n{\dot{\dot{\dot{\uparrow }}}}^{n}a{\uparrow }^{n}1$, supaya kesemua $a$ menjadi kendalian sebelah kiri bagi pengendali anak panah. Ini adalah penting kerana pengendali anak panah ini tidak boleh bertukartertib.

Menulis $(a{\uparrow }^m{)}^b$ untuk kuasa fungsi ke-b bagi fungsi $f(x)=a{\uparrow }^{m}x$ memberikan kita $a{\uparrow }^{n}b=(a{\uparrow }^{n-1}{)}^{b}1$.

Takrifan ini boleh ditentuluarkan selangkah lagi, bermula dengan $a{\uparrow }^{n}b=ab$ jika n = 0, kerana pengeksponenan ialah pendaraban berulang yang bermula dengan 1. Menentuluarkan selangkah lagi dengan menulis operasi pendaraban sebagai penambahan berulang adalah tidaklah begitu jelas dan mudah kerana pendaraban ialah penambahan berulang bermula dengan 0 bukannya 1. "Menentuluarkan" selangkah lagi dengan menulis penambahan n sebagai penambahan berulang 1 memerlukan permulaan dengan nombor a. Bandingkan dengan definisi bagi pengendali hiper, di mana nilai permulaan bagi penambahan dan pendaraban juga dinyatakan secara berasingan.

Jadual-jadual nilai

Mengira 2↑^mn

Pengiraan $2{\uparrow }^{m}n$ boleh dinyatakan semula dalam bentuk jadual tak terhingga. Kita letakkan nombor $2^n$ di baris atas, dan isikan lajur kiri dengan nilai 2. Untuk menentukan satu nombor di atas jadual, ambil nombor betul-betul di sebelah kiri, kemudian lihat nombor yang diperlukan di baris sebelumnya, di kedudukan yang diberikan oleh nombor yang telah diambil:

Nilai-nilai $2{\uparrow }^{m}n$ = hyper(2, m + 2, n) = 2 → n → m

m\n	1	2	3	4	5	6	formula
1	2	4	8	16	32	64	$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\uparrow \uparrow n$
3	2	4	65536	$\begin{array}{c}\underbrace{2_{}^{2^{{}^{.{}^{.{}^{.{}^2}}}}}}\\ 65536\text{ salinan }2\end{array}$			$2\uparrow \uparrow \uparrow n$
4	2	4	$\begin{array}{c}\underbrace{2_{}^{2^{{}^{.{}^{.{}^{.{}^2}}}}}}\\ 65536\text{ salinan }2\end{array}$				$2\uparrow \uparrow \uparrow \uparrow n$

Jadual ini sama dengan jadual bagi fungsi Ackermann, bezanya hanya anjakan dalam $m$ dan $n$ dan penambahan 3 dalam semua nilai.

Mengira 3↑^mn

Kita letakkan nombor $3^n$ di baris atas, dan isikan lajur kiri dengan nilai 3. Untuk menentukan satu nombor di atas jadual, ambil nombor betul-betul di sebelah kiri, kemudian lihat nombor yang diperlukan di baris sebelumnya, di kedudukan yang diberikan oleh nombor yang telah diambil:

Nilai-nilai $3{\uparrow }^{m}n$ = hyper(3, m + 2, n) = 3 → n → m

m\n	1	2	3	4	5	formula
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{array}{c}\underbrace{3_{}^{3^{{}^{.{}^{.{}^{.{}^3}}}}}}\\ 7,625,597,484,987\text{ salinan }3\end{array}$			$3\uparrow \uparrow \uparrow n$
4	3	$\begin{array}{c}\underbrace{3_{}^{3^{{}^{.{}^{.{}^{.{}^3}}}}}}\\ 7,625,597,484,987\text{ salinan }3\end{array}$				$3\uparrow \uparrow \uparrow \uparrow n$

Mengira 10↑^mn

Kita letakkan nombor $10^n$ di baris atas, dan isikan lajur kiri dengan nilai 10. Untuk menentukan satu nombor di atas jadual, ambil nombor betul-betul di sebelah kiri, kemudian lihat nombor yang diperlukan di baris sebelumnya, di kedudukan yang diberikan oleh nombor yang telah diambil:

Nilai-nilai $10{\uparrow }^{m}n$ = hyper(10, m + 2, n) = 10 → n → m

m\n	1	2	3	4	5	formula
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^{10^{10^{10,000,000,000}}}$	$10\uparrow \uparrow n$
3	10	$\begin{array}{c}\underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ 10\text{ salinan }10\end{array}$	$\begin{array}{c}\underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ \underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ 10\text{ salinan }10\end{array}$	$\begin{array}{c}\underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ \underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ \underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ 10\text{ salinan }10\end{array}$		$10\uparrow \uparrow \uparrow n$
4	10	$\begin{array}{c}\underbrace{{}^{{}^{{}^{{}^{{}^{10}.}.}.}10}10}\\ 10\text{ salinan }10\end{array}$	$\begin{array}{c}\underbrace{{}^{{}^{{}^{{}^{{}^{10}.}.}.}10}10}\\ \underbrace{{}^{{}^{{}^{{}^{{}^{10}.}.}.}10}10}\\ 10\text{ salinan }10\end{array}$			$10\uparrow \uparrow \uparrow \uparrow n$