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:

Contohnya,

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

Contohnya,

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

Contohnya,

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,

 

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):

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

dan seterusnya. Peraturan amnya ialah satu pengendali  anak panah berkembang menjadi satu siri perkaitan kanan pengendali  anak panah.

Contohnya:

Notasi  biasanya digunakan untuk melambangkan  dengan  anak panah.

Notasi 
Dalam pernyataan seperti , notasi bagi pengeksponenan biasanya ditulis dalam bentuk nombor eksponen  ditulis dalam superskrip selepas nombor asas . Tetapi dalam sesetengah keadaan — seperti di dalam bahasa pemprograman dan emel berteks biasa — tulisan superskrip tidak boleh digunakan. Kebanyakan orang telah menggunakan notasi linear  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  bukan bersifat terlalu umum, dan sebab inilah Knuth menggunakan notasi linear .

Menulis notasi anak panah atas dalam terma kuasa (notasi superskrip)
Jika  ditulis dalam notasi superskrip yang biasa, ia akan menghasilkan apa yang dipanggil "menara kuasa".
Contohnya, 

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

Jika diteruskan dengan notasi ini,  boleh ditulis sebagai satu susunan menara kuasa, setiap satu menunjukkan saiz menara diatasnya.

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

Tambahan lagi,  boleh ditulis sebagai beberapa susunan menara kuasa ini, setiap susunan menunjukkan ketinggian menara di sebelah kirinya.

Dan secara lebih am:

Ini boleh terus dilakukan untuk menggambarkan  dalam bentuk pengeksponenan berulang bagi mana-mana nilai ,  dan  (walaupun dengan jelas ia akan memakan ruang).

Menggunakan tetrasi
Notasi tetrasi  membolehkan kita untuk membuatkan gambar-gambar rajah ini lebih ringkas dan masih lagi mengekalkan perlambangan berbentuk geometri (kita boleh memanggilnya menara tetrasi).

 

 

 

Akhir sekali, sebagai contoh, nombor Ackermann keempat, , boleh ditulis sebagai

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  anak panah  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.

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

untuk semua integer  dengan .

Kesemua pengendali anak panah atas (termasuk pengeksponenan biasa, ) 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,  dan bukannya ; contohnya  sama dengan , bukannya .

Ada sebab yang baik mengapa urutan pengiraan kanan ke kiri digunakan untuk pengendali ini. Jika urutan kiri ke kanan digunakan,  akan bersamaan dengan , dan tidak akan menjadikan  satu operasi yang baru. Perkaitan kanan juga adalah tepat kerana kita boleh menulis semula ungkapan anak panah berulang  yang diperolehi daripada perkembangan  sebagai , supaya kesemua  menjadi kendalian sebelah kiri bagi pengendali anak panah. Ini adalah penting kerana pengendali anak panah ini tidak boleh bertukartertib.

Menulis  untuk kuasa fungsi ke-b bagi fungsi  memberikan kita .

Takrifan ini boleh ditentuluarkan selangkah lagi, bermula dengan  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↑<sup>m</sup>n
Pengiraan  boleh dinyatakan semula dalam bentuk jadual tak terhingga. Kita letakkan nombor  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:

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

Mengira 3↑mn
Kita letakkan nombor  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:

Mengira 10↑mn
Kita letakkan nombor  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:

Rujukan

Matematik