Notasi anak panah atas Knuth

Dari testwiki
Loncat ke navigasi Loncat ke pencarian

Notasi anak panah atas Knuth adalah salah satu cara untuk merepresentasikan bilangan bulat yang sangat besar. Notasi ini diciptakan oleh Donald Knuth pada tahun 1976.[1] Dalam makalahnya pada tahun 1947,[2]  R. L. Goodstein memperkenalkan urutan operasi spesifik yang sekarang disebut hiperoperasi, yang mana perkalian dianggap sebagai iterasi atau perulangan dari penjumlahan, perpangkatan adalah iterasi dari perkalian, iterasi selanjutnya adalah tetrasi, kemudian pentasi, dan seterusnya, di mana notasi anak panah Knuth dapat digunakan. misalnya:

  • Anak panah tunggal () mewakili eksponenisasi yang merupakan perkalian berulang.

24=H3(2,4)=2×(2×(2×2))=24=16

24=H3(2,4)=2×(2×(2×2))=24=16

  • Anak panah tripel () mewakili pentasi yang merupakan tetrasi yang berulang.24=H5(2,4)=2(2(22))=2(2(22))=2(24)=2(2(2))=22224 copies of 265,536 2s

Definisi umum dari notasi anak panah adalah sebagai berikut, dimana dimana (a0,n1,b0):

anb=Hn+2(a,b)=a[n+2]b.

Disini, n merupakan singkatan dari anak panah yang berjumlah n sebagai contoh:

23=243.

dan kurung siku adalah notasi lain dari hiperoperasi

Pengenalan

Hiperoperasi secara alami memperluas operasi aritmetika dari operasi yang lebih kecil seperti Perkalian yang merupakan iterasi, lelaran, perulangan atau Rekursi dari penjumlahan. yang direpresentasikan dengan notasi dibawah ini:

Penambahan dengan bilangan asli didefinisikan dengan penjumlahan yang berulang

H1(a,b)=a+b=a+1++1b kali

Misalnya

5+3=5+1+1+1=8

Perkalian merupakan iterasi atau perulangan dari penjumlahan

H2(a,b)=a×b=a+a++ab kali

Misalnya:

4×3=3+3+3+3=12

Perpangkatan adalah iterasi dari perkalian, dalam notasi Knuth dilambangkan dengan satu anak panah:

H3(a,b)=ab=ab=a×a××ab kali

Misalnya:

43=43=4×4×4

Tetrasi merupakan Iterasi dari perpangkatan, yang merupakan perpangkatan yang berulang, dilambangkan dengan dua anak panah:

H4(a,b)=ab= ba=aa....ab kali=a(a(...a))b kali

Misalnya:

H4(a,b)=43=444=4(44)=42561.34078079×101544 sebanyak 3 tingkat3 angka 4

Berdasarkan definisi ini dapat diketahui bahwa anak panah ganda () ini mewakili perpangkatan dengan tingkat sebanyak n tingkat, maka

32=33=27

33=333=327=7.625.597.484.987

34=3333=376255974849871,2580143×103638334640024

35=33333=33327=337625597484987=31,2580143×103638334640024

Dan seterusnya, Walaupun bilangan ini sudah terlihat sangat besar. Hiperoperasi tidak berhenti disitu. Iterasi selanjutnya seperti pentasi, heksasi, dan lain-lain dilakukan dengan menambah jumlah anak panah pada notasi anak panah knuth:

Pentasi, mendefinisikan iterasi dari tetrasi. Direpresentasikan dengan panah tripel atau rangkap tiga ():

H5(a,b)=ab=a(a(...a))b kali

Heksasi mendefinisikan iterasi dari pentasi. Direpresentasikan dengan panah tripel atau rangkap empat ():

H6(a,b)=ab=a(a(...a))b kali

Jadi, notasi anak panah-n didefinisikan sebagai deret anak panah (n1):

a...nb=a...n1(a...n1(......n1a))b kali

Sebagai contoh:

32=33=333=327=7,625,597,484,987

33=3(33)=3(333)=3333 sebanyak 333=3333 sebanyak 7,625,597,484,987 tingkat=333333 sebanyak 7,625,597,484,987 tingkat

Notasi

Terdapat notasi versi simpel yang lebih pendek, dengan menggunakan anb, contohnya a4b=ab=H6(a,b). Tapi perlu diingat bentuk ini tidak sama dengan notasi hiperoperasi, misalnya dalam hiperoperasi contoh tersebut seharusnya bernama tetrasi karena n-nya adalah empat, bukan heksasi yang n-nya enam. Dalam hiperoperasi notasi tersebut berbentuk an2b, contohnya a5b=ab=H7(a,b), dan diberinama pentasi sesuai dengan n-nya yaitu lima.

Notasi anak panah dipilih karena beberapa hal seperti bahasa pemrograman dan e-mail berupa teks tidak mendukung simbol pangkat. Jika suatu pengodean karakter tidak memiliki simbol anak panah dapat digunakan simbol "caret" atau Superskrip (^).

Notasi alternatif lainnya adalah notasi anak panah berantai yang diciptakan John Horton Conway dan digunakan untuk melambangkan angka yang sangat besar, lebih besar dari notasi Knuth:

anb=abn

Merepresentasi notasi anak panah knuth dalam bentuk menara daya

notasi ab dapat direpresentasikan dengan menggunakan menara daya atau tetrasi yang berarti a pangkat a sebanyak b kali.

a4=a(a(aa))=aaaa

Menambahkan satu anak panah lagi akan menghasilkan menara daya bertumpuk yang menunjukkan jumlah anak panah untuk tingkat yang lebih tinggi diatasnya.

a4=a(a(aa))=aa...aaa...aaa...aa

Melanjutkan dari notasi ini, ab bisa digambar dengan titik diantara menara dengan informasi tambahan mengenai berapa jumlah tingkat menara yang disigkat menjadi titik.

ab=aa...aaa...aa}b

Lebih-lebih lagi, anak panah 4. ab dapat ditulis dengan menumpuk menara anak panah tripel sebanyak b kali.

a4=a(a(aa))=aa...aaa...aa}aa...aaa...aa}aa...aaa...aa}a

Dan lebih lanjut, lagi secara umum akan direpresentasikan setidaknya seperti ini:

ab=aa...aaa...aa}aa...aaa...aa}}ab

Cara ini dapat terus dilakukan untuk merepresentasi (a)nb sebagai eksponenisasi iterasi dari eksponenisasi untuk a,b dan n. Meskipun ini akan semakin sulit dilakukan.

Menggunakan tetrasi

Notasi Rudy Rucker ba membuat representasi notasi anak panah knuth menjadi sedikit lebih mudah sambil terus menggunakan menara daya (representasi geometris)

ab=ba

ab=a...aab

ab=a...aaa...aaa}b

Dan akhirnya, bilangan keempat dari Fungsi Ackerman, 4()44 dapat direpresentasikan dengan:

4...444...444...444=4...444...444444

Penyederhanaan

Saat bilangan yang dibahas terlalu besar, dan jumlah anak panah terlalu panjang untuk ditulis, operator n dapat sangat membantu, n dapat merepresentasikan jumah panah yang ada. Jika bilangan tersebut masih terlalu besar maka Notasi anak panah berantai Conway dapat digunakan, notasi panah berantai tiga mungkin sama dengan notasi anak panah knuth, tapi jika rantai mencapai 4 anak panah, ini akan sangat jauh lebih kuat daripada anak panah Knuth.

anb=a[n+2]b=abn(Knuth)(hiperoperasi)(Conway)

642=6[4]4=64=66...64=6666=6646656

10(3×10(3×1015)+3)= 100000...000300000...003300000...00015 = 103×103×1015+3

Fungsi yang tumbuh lebih cepat dari ini oun dapat dikategorikan menggunakan analisis ordinal yang disebut hierarki cepat bertumbuh Hirarki cepat bertumbuh menggunakan iterasi fungsi dan diagonalisasi yang berurutan untuk secara sistematis membuat fungsi yang tumbuh lebih cepat dari beberapa fungsi dasar. f(x) untuk hirarki cepat bertumbuh dapat menggunakan f0(x)=x+1, f1(x) menunjukkan perkalian, f2(x) sudah menunjukkan eksponensial, f3(x) menunjukkan iterasi eksponenisasi berupa tetrasi. Kemudian fω(x) sebanding dengan Fungsi Ackermann ,fω+1sudah berada di luar jangkauan panah bertingkat, tetapi masih dapat digunakan untuk memperkirakan Bilangan Graham , dan sebanding dengan notasi panah berantai Conway yang bisa dipanjangjan sepanjang apapun.

Semua fungsi ini dapat dihitung. Bahkan fungsi yang dapat dihitung lebih cepat, seperti Deret Goodstein dan Deret TREE yang memerlukan penggunaan ordinal besar, dapat terjadi dalam konteks kombinatorik dan teori pembuktian tertentu. Ada fungsi yang tumbuh sangat cepat, seperti Fungsi Busy Beaver , yang sifatnya akan sepenuhnya berada di luar jangkauan panah atas, atau bahkan analisis berbasis ordinal apa pun.

Definisi

Tanpa referensi dari hiperoperasi, Notasi anak panah atas Knuth masih dapat dijabarkan dengan rumus formal matematika.

anb={ab,jika n=1;1,jika n>1 dan b=0;an1(an(b1)),jika kondisi tidak ada yang terpenuhi

Dimana Bilangan bulat a, b, n adalah a0, n1, b0.

Definisi ini menggunakan eksponenisasi (a1b=ab=ab) sebagai kasus atau tingkatan dasar, dan tetrasi (a2b=ab) sebagai eksponenisasi yang diulang(iterasi). ini setara dengan tingkatan hiperoperasi kecuali suksesi, penjumlahan dan perkalian.

Seseorang juga dapat memilih perkalian (a0b=a×b)sebagai kasus dasar dan ulangi dari sana. Kemudian eksponensial menjadi perkalian berulang. Definisi formalnya adalah:

anb={a×b,jika n=0;1,jika n>0 dan b=0;an1(an(b1)),jika kondisi tidak terpenuhi 

Dimana Bilangan bulat a, b, n adalah a0, n0, b0.

Namun perlu dicatat bahwa simplifikasi Notasi anak panah Knuth tidak mendefinisikan "panah nol" (0), notasi ini daspat diperluas ke indeks (n2) sedemikian rupa sehingga sesuai dengan seluruh rangkaian hiperoperasi kecuali untuk jeda dalam pengindeksan:

Hn(a,b)=a[n]b=an2b dengan n0.

Operasi panah ke atas adalah termasuk operasi asosiatif kanan. Yaitu dimana operasi abc, dipahami sebagai a(bc), alih-alih (ab)c Jika ambiguitas bukan masalah, tanda kurung terkadang dihilangkan.

Tabel nilai bilangan

Menghitung 0↑nb

Menghitung 0nb=Hn+2(0,b)=0[n+2]b akan menghasilkan:

  • 0, jika n = 0  
  • 1, jika n = 1 dan b = 0
  • 0, jika n = 1 dan b > 0  
  • 1, jika n > 1 dan b genap (termasuk juga ketika b = 0)
  • 0, jika n > 1 dan b ganjil

Menghitung 1↑nb

Menghitung angka 1 dengan cara mengalikannya, memangkatkannya atau bahkan menumpuknya dengan tetrasi akan selalu menghasilkan angka 1.

Menghitung 2↑nb

Komputasi 2nb dapat direpresentasikan dalam bentuk tabel yang berukuran tak terbatas. disini hanya ditampilan angka-angka 2bpada baris paling atas, dan isi kolom kiri dengan nilai 2.

Nilai dari 2nb = Hn+2(2,b) = 2[n+2]b = 2bn
Templat:Diagonal split header 1 2 3 4 5 6 formula
1 2 4 8 16 32 64 2b
2 2 4 16 65536 265,5362.0×1019,728 2265,536106.0×1019,727 2b
3 2 4 65536 22...22 sebanyak 65.536 22...222...22 sebanyak 65.536 22...222...222...22 sebanyak 65.536 2b
4 2 4 22...22 sebanyak 65.536 2...2222...22 sebanyak 65.536 2...222...2222...22 sebanyak 65.536 2...222...222...2222...22 sebanyak 65.536 2b

Menghitung 3↑nb

Komputasi 3nb dapat direpresentasikan dalam bentuk tabel yang berukuran tak terbatas. disini hanya ditampilan angka-angka 3bpada baris paling atas, dan isi kolom kiri dengan nilai 3.

Nilai dari 3nb = Hn+2(3,b) = 3[n+2]b = 3bn
Templat:Diagonal split header 1 2 3 4 5 formula
1 3 9 27 81 243 3b
2 3 27 7.625.597.484.987 37.625.597.484.9871.3×103.638.334.640.024 337.625.597.484.987 3b
3 3 7.625.597.484.987 33...33 sebanyak 7.625.597.484.987 33...333...33 sebanyak 7.625.597.484.987 33...333...333...33 sebanyak 7.625.597.484.987 3b
4 3 33...33 sebanyak 7.625.597.484.987 3...3333...33 sebanyak 7.625.597.484.987 3...333...3333...33 sebanyak 7.625.597.484.987 3...333...333...3333...33 sebanyak 7.625.597.484.987 3b

Menghitung 4↑nb

Komputasi 4nb dapat direpresentasikan dalam bentuk tabel yang berukuran tak terbatas. disini hanya ditampilan angka-angka 4bpada baris paling atas, dan isi kolom kiri dengan nilai 4.

Nilai dari 4nb = Hn+2(4,b) = 4[n+2]b = 4bn
Templat:Diagonal split header 1 2 3 4 5 formula
1 4 16 64 256 1024 4b
2 4 256 42561.34×10154 44256108.0×10153 444256 4b
3 4 44256108.0×10153 44...44 sebanyak 44256 44...444...44 sebanyak 44256 44...444...444...44 sebanyak 44256 4b
4 4 44...444...44 sebanyak 44256 4...4444...444...44 sebanyak 44256 4...444...4444...444...44 sebanyak 44256 4...444...444...4444...444...44 sebanyak 44256 4b

Menghitung 10↑nb

Komputasi 10nb dapat direpresentasikan dalam bentuk tabel yang berukuran tak terbatas. disini hanya ditampilan angka-angka 10bpada baris paling atas, dan isi kolom kiri dengan nilai 10.

Nilai dari 10nb = Hn+2(10,b) = 10[n+2]b = 10bn
Templat:Diagonal split header 1 2 3 4 5 formula
1 10 100 1.000 10.000 100.000 10b
2 10 10.000.000.000 1010.000.000.000 101010.000.000.000 10101010.000.000.000 10b
3 10 1010...1010 sebanyak 10 1010...101010...1010 sebanyak 10 1010...101010...101010...1010 sebanyak 10 1010...101010...101010...101010...1010 sebanyak 10 10b
4 10 10...101010 sebanyak 10 10...101010...101010 sebanyak 10 10...101010...101010...101010 sebanyak 10 10...101010...101010...101010...101010 sebanyak 10 10b

Pranala luar

Referensi

Templat:ReflistTemplat:Googologi

Templat:Authority control