Conway dizisi ok gösterimi nedir ?

SaMeT46 Harbi Aktif Üye
Conway dizisi ok gösterimi, çok büyük sayıları ifade etmek için matematikçi John Horton Conway tarafından oluşturuldu. Pozitif tam sayılar serisini basitçe sağa doğru oklarla ayırarak gösterir. Örneğin, 2→3→4→5→6.

Çok kombinatorik sembolojiler ile tanımı özyinelemedir. Bundan dolayıdır ki gösterim, sayının bazı tamsayı kuvvetini yükselterek çözmektir.

Tanım ve önizleme
Conway dizisi (veya kısa dizi) şöyle tanımlanır:

  • Her pozitif tamsayı uzunluğu 1 olan dizidir.
  • n uzunluğundaki bir dizi, sağ oktan sonra pozitif tam sayı gelir ve bu dizi formunun uzunluğu
    40b85027598d87611b1c8d5d11e46812.png
    olur.
Her dizi bir tam sayı ifade eder ve şu dört kuralı içerir. Eğer aynı tam sayıyı ifade ediyorlarsa iki dizi eşdeğerdir.

Eğer p ve q pozitif tam sayı ve X bir alt dizi ise:

  1. 83878c91171338902e0fe0fb97a8c47a.png
    dizisi p sayısını ifade eder.
  2. b66c84ff4babc1c358e6e5c7df6d1ca3.png
    'nun üslü ifadesi
    89fd5cb8dac3bfccdba18831b37c754c.png
    'dir.
  3. a01b53e7a81acf9d21358207a548a1cf.png
    ,
    bb0d2f948a712fd5cf7ab679cf32c0ad.png
    'ye eşdeğerdir.
  4. c5a35d594c8b2ce4c9d6dc11b5532e53.png
    ,
    346732f832eb09fb1ddcb81d5e06f375.png
    'ye eşdeğerdir
    (q > 0 için, p tane X, p - 1 tane q ve p - 1 tane çift parantez uygulanır).
Son ifade üç nokta, kısaltma yapmak için kullanıldı:

4a.
88392b337a4dae373aa68f06f12fddb5.png

4b.
5232cc04e9eae8e97a167950dd9e4bf8.png

Özellikler

  1. Uzunluğu 3 olan bir dizi Knuth yukarı ok gösterimini ve hiperişlemleri ifade eder:
  2. X→p formunun X→Y dizisinden dolayı:
  3. a ile başlayan bir dizi, a nın bir kuvvetidir
  4. 1→Y dizisi 1'e eşittir
  5. X→1→Y dizisi X'e eşittir
  6. 2→2→Y dizisi 4'e eşittir
  7. X→2→2 dizisi X→(X)'e eşittir (X dizisinın değeri ona bağlandı)
Açıklama

Bir ok dizisini bir bütün olarak işlemekte dikkatli olunmalıdır. Ok dizileri, ikili işleçlerin (operatörlerin) tekrarlı uygulamasını açıklamaz. İçteki diğer sembol dizileri (örn, 3+4+5+6+7), çoğunlukla parçalarla (örn, (3+4)+5+(6+7)) ele alınır ve anlamda bir değişiklik olmaz (birleşmeye bakınız) veya en azından öngörülen sıraya göre adım adım işlem yapılabilir. Örn,
2abd1d9ba05808b3773c630fe08fb8cb.png
sağdan sola doğru. Örneğin:

  • 099d7adfd8e6eecf4723e482c3ec169b.png
  • 9adc779d5d6acd63f2caecd7b9707e5e.png
  • e02f539d07bde29e362fc029696ab1e4.png
Dördüncü kural temeldir. 2 veya daha büyük sayı ile biten 3 veya daha fazla elemanlı dizi, aynı uzunlukta, sondan bir önceki elemanı (genellikle büyük oranda) artan bir dizi olur. Fakat onun sonelemanı küçültülür.

Örnekler

Örnekler oldukça karışıktır. Burada birkaçına yer vereceğiz:

n

= n (1.kurala göre)
p→q

= pq (2.kurala göre)
Burada 3→4 = 34 = 81
1→(her oklu ifade)

= 1 tam ifade sonuçta 1sayı = 1 olarak azaldığında.
4→3→2

= 4→(4→(4)→1)→1 (4.kurala göre) ve sonra iç parantezlerden dışa doğru,
= 4→(4→4→1)→1 (gereksiz parantezler kaldırıldı)
= 4→(4→4)→1 (3'e göre)
= 4→(256)→1 (2'ye göre)
= 4→256→1
= 4→256 (3'e göre)
= 4256 (2'ye göre)
= 13 407 807 929 942 597 099 574 024 998 205 846 127 479 365 820 592 393 377 723 561 443 721 764 030 073 546 976 801 874 298 166 903 427 690 031 858 186 486 050 853 753 882 811 946 569 946 433 649 006 084 096 exactly ≈ 1.34078079299 × 10154
Knuth oklarıyla:
d0333cae0972bbe1c96b7c614975f530.png


2→2→4

= 2→(2)→3 (4'e göre)
= 2→2→3
= 2→2→2 (4'e göre)
= 2→2→1 (4'e göre)
= 2→2 (3'e göre)
= 4 (2) (4 için her dizi 2 tane 2 ile başlar)
2→4→3

= 2→(2→(2→(2)→2)→2)→2 (4.'e göre) Dört tane X (ki buradakisi 2 dir), üç tane q (buradakisi yine 2'dir) ile karışmasını engellemek için koyu yazıldı
= 2→(2→(2→2→2)→2)→2
= 2→(2→(4)→2)→2 (önceki örnekteki gibi)
= 2→(2→4→2)→2
= 2→(2→(2→(2→(2)→1)→1)→1)→2 (4.kurala göre)
= 2→(2→(2→(2→2→1)→1)→1)→2
= 2→(2→(2→(2→2)))→2 (yine 3'e göre)
= 2→(2→(2→(4)))→2 (2'ye göre)
= 2→(2→(16))→2 (2'ye göre)
= 2→65536→2
= 2→(2→(2→(...2→(2→(2)→1)→1...)→1)→1)→1 (4'e göre) 65535 parantezli
= 2→(2→(2→(...2→(2→(2))...)))) (yine 3'e göre)
= 2→(2→(2→(...2→(4))...)))) (2'ye göre)
= 2→(2→(2→(...16...)))) (2'ye göre)
=
1a4b2f00fa25ab56eddab10ad42fc7b5.png
(216 kule = 65536 kat) = 655362 (Tetrasyona bakınız)
Knuth okları ile:
73c3c03578aa1461ef152325c58e3cac.png


2→3→2→2

= 2→3→(2→3)→1 (4'e göre)
= 2→3→8 (2 ve 3) Knuth okları ile: 2 ↑8 3 (özellik1)
= 2→(2→2→7)→7 (1)
= 2→4→7 (iki tane başlangıç 2'si 4 eder [özellik6]) Knuth okları ile: 2 ↑7 4 (özellik1)
= 2→(2→(2→2→6)→6)→6 (4)
= 2→(2→4→6)→6 (özellik6)
= 2→(2→(2→(2→2→5)→5)→5)→6 (4)
= 2→(2→(2→4→5)→5)→6 (özellik6)
= 2→(2→(2→(2→(2→2→4)→4)→4)→5)→6 (4)
= 2→(2→(2→(2→4→4)→4)→5)→6 (özellik6)
= 2→(2→(2→(2→(2→(2→2→3)→3)→3)→4) →5)→6 (4)
= 2→(2→(2→(2→(2→4→3)→3)→4)→5)→6 (özellik6)
= 2→(2→(2→(2→(2→65536→2)→3)→4)→5)→6 (önceki örnekten)
= önceki sayıdan çok büyüktür
Knuth okları ile:
f54e1cc0cd3db81dd2fdf0a0ec8f2bb8.png


3→2→2→2

= 3→2→(3→2)→1 (4)
= 3→2→9 (2 ve 3)
= 3→3→8 (4)
Knuth okları ile:
b0f5fed04524076a66e4750ac261eb04.png
.

Sistematik örnekler
Dört terimlilerin en basit durumları (2'den küçük tam sayı içermez):

  • 23b0272d323ebd1eedc3767baac042e1.png
(ayrıca bahsedilen son özellikten)
  • 9d82808b06d676f828040fd57478ac4f.png

    c508fd56ec4ec5ff0bc80585f47441e1.png
  • 585aec8ae8b9a1630fda187fcda6306f.png
m>2 için burada bir kalıp görebiliriz. Eğer herhangi bir X dizisi için
f13cc27c9f2c821c32fe7db6fdd198fb.png
ise, buradan
03078caf74d1779fdd3f7b431ce2784d.png
elde ederiz (fonksiyonel kuvvetlere bakınız]]).

Bunu
8b0b565d81acb2ec77667b46c9b071b7.png
'ye uygularsak
dc8f05ca66b23e86939d672b43eabbf5.png
ve
7fceb9cb5f8221b88688c0ca3feff048.png
olur.

Buradan örneğin,
135e911413ebfc77a31c29261c13c4c6.png
elde edilir.

Devam edersek:

  • c735e161cf0ca2a24e43c5effe6f0451.png
Tekrar genelleştirme yapabiliriz.
5cd86ca5912f9921c5c8e436fa3d3e09.png
yazarsak
cd849d46f610f9599f07093af02d2b5d.png
elde ederiz. Buradan
d9baaf38150da61d61216cfc92301e80.png
olur. Yukarıdaki durumda,
035f980525ec91dd946b1665c3afab8b.png
ve
d31bd9a7ad2ecebe96632ce468cc6fad.png
olur. Buradan da
95fe76ffab5e83fa10ad9d79e3f14b00.png
elde edilir.

Ackermann işlevi
Ackermann işlevi, Conway dizisi ok gösterimi kullanılarak şöyle ifade edilebilir:

m>2 için, A(m, n) = (2 → (n+3) → (m − 2)) − 3
olduğundan dolayı,

n>2 için, 2 → nm = A(m+2,n-3) + 3 olur.
(n=1 ve n=2, sırasıyla A(m,-2)=-1 ve A(m,-1)=1'i karşılayabilir. Bu mantıksal olarak eklenebilir).

Graham sayısı

Graham sayısı
d0f2a719fdb790449519bd35ded4d6fd.png
, kendini Conyaw dizisi ok gösteriminde özlü olarak ifade edemez. Fakat
bc3849a9f3f9d0c6be9e42d940a8af7f.png
ortanca fonksiyonunu tanımlayarak;
8e58cff0b412a8d2256081d8f518002e.png
(fonksiyonel kuvvetebakınız) ve
de9d175f880c04189fb38a08850d03d8.png
'yi elde ederiz.

İspat: Sırasıyla kural 3 ve kural 4'deki açıklamaları uygularsak şunları elde ederiz:

ec760ada4b4352f72b71069f00889fff.png


4a632501f69cc856ce009be2f4784a67.png
(64 tane
9836c7ec28dca233a2cd64ab06a36724.png
)
76d11d7befebf1d1fbe322eacac517b7.png

6ddb68c0e09b3b7ba003589971da53d2.png

df1fac3a76f06ad2bbb972744ff4ec2c.png


aa968a295af28dc5b7403d81e4c84f67.png
(64 tane
9836c7ec28dca233a2cd64ab06a36724.png
)
b4225be85278594ae38996b366a49239.png


33620e433240fd6b0438003a0520ef2a.png
(64 tane
9836c7ec28dca233a2cd64ab06a36724.png
)
55ab443ea399ff8abb2ab978cdb0481a.png
(65 tane
9836c7ec28dca233a2cd64ab06a36724.png
)
abd2346e8e104a703a487f4fee00b094.png
(yukarıdaki gibi hesaplanır).
f hızlı olarak artarken,

94e8ef8bca2ffca8fb9059c0070d475a.png
'de sapma meydana gelir.
Çok büyük sayıyı dizi okları ile ifade etmek oldukça kolaydır. Örneğin,

463f305872a4c18ef5a8f323af338f2f.png

sayısı Graham sayısından çok büyüktür.
 

Benzer Konular

Yanıtlar
0
Görüntülenme
9B
Yanıtlar
0
Görüntülenme
5B
Yanıtlar
0
Görüntülenme
4B
Yanıtlar
0
Görüntülenme
3B
Yanıtlar
0
Görüntülenme
6B
Üst