Graham sayısı

Graham sayısı, adını Ronald Graham'dan alan, Ramsey teorisindeki problemlerin çözümü için üst sınır getiren büyük bir sayıdır.

Martin Gardner, Kasım 1977'de Matematiksel Oyunlar bölümünün Bilimsel Amerikan kısmında bu sayıyı açıkladığında popülaritesi hızla arttı.

1980 Guinness Rekorlar Kitabı, Graham'ın talebini tekrarladı ve onu en çok ilgi çekenler listesine ekledi. Graham sayısı, googol, googolplex gibi diğer bilinen tüm sayılardan düşünülemeyecek kadar büyüktür. Ayrıca Skewes sayısı ve Moser sayısından da büyüktür. Gerçekten de, gözlemlenebilir evren, Graham sayısının dijital ifadesini kapsamakta çok aciz kalır. Üstelik her dijitin en az bir Planck hacmi kadar yer kapladığı varsayılırsa bile. ${\displaystyle a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}}$ formunun üslü kuleleri bile bunu ifade etmekten acizdir. Hem de bu kuleler Knuth yukarı ok gösterimi kullanılarak kolayca ifade edilebilirken. Graham sayısının son on rakamları ...2464195387'dir.

Ciddi matematik ispatlarında ortaya çıkan özel tam sayılar, Graham sayısından daha büyük olarak bilinir. .

Graham problemi

Graham sayısı, matematiğin bir kolu ve Ramsey teorisi olarak bilinen şu problemle ilişkilidir:

n boyutlu hiperküp ve her köşe çiftinin bağlı olduğu ${\displaystyle 2^{n}}$ köşeli tam grafik elde etmeyi hayal edin. Sonra sadece kırmızı ve siyah renkleri kullanarak bu grafiğin her bir köşesini renklendirin. Bir düzlemde bulunan 4 köşeli alt grafiğin tek renkli olması gereken renklendirmenin mümkün olan en küçük n değeri nedir?

Graham & Rothschild (1971), bu problemin bir çözümü olabileceğini gösterdi. Bilinen, açıkça tanımlanan ve çok büyük sayı olan N ile üst sınır belirlensin. N* 'ye de şöyle bir sınırlama getirelim; 6 ≤ N* ≤ N. (Knuth yukarı ok gösteriminde, ${\displaystyle N=F^{7}(12)\,\!}$. buradaki ${\displaystyle F(n)=2\uparrow ^{n}3\,\!}$'dür.) Alt sınır olan 6, Hindistan Devlet Üniversitesinden Geoff Exoo tarafından 2003 yılında 11'e yükseltildi. N* 'nin çözümü için en iyi bilinen belirli sınır yaklaşımı şimdi 11 ≤ N* ≤ N oldu.

N'den daha büyük olan G üst sınırı, ${\displaystyle G=f^{64}(4)\,\!}$ olarak ifade edilir. Burada ${\displaystyle f(n)=3\uparrow ^{n}3\,\!}$'dür.

Graham sayısını açıklama

Knuth yukarı ok gösterimi kullanılarak Graham sayısı olan G (Gardner'in Bilimsel Amerikan makalesinde açıkladığı gibi) şöyle ifade edilir:

${\displaystyle \left.{\begin{matrix}G&=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \uparrow } 3\\&&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow } 3\\&&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&&3\underbrace {\uparrow \uparrow \cdots \cdot \cdot \uparrow } 3\\&&3\uparrow \uparrow \uparrow \uparrow 3\end{matrix}}\right\}{\text{64 derece (veya seviye)}}}$

Burada, en üst dereceden başlayarak her bir derecedeki ok sayısı, onun altındaki derecenin değeriyle şöyle ifade edilir:

${\displaystyle G=g_{64},{\text{ burada }}g_{1}=3\uparrow \uparrow \uparrow \uparrow 3,\ g_{n}=3\uparrow ^{g_{n-1}}3,}$

Yukarı oktaki üstindis kaç tane ok olduğunu belirtir. Diğer yöntemde G 64 adımda hesaplanır: İlk adım, 3'lerin arasında dört tane yukarı ok olan g₁'i hesaplamaktır. İkinci adım, 3'lerin arasında g₁ tane yukarı ok olan g₂'yi hesaplamaktır. Üçüncü adım, 3'lerin arasında g₂ tane yukarı ok olan g₃'ü hesaplamaktır ve böylece devam eder. En sonuncusu, 3'lerin arasında g₆₃ tane yukarı ok olan G = g₆₄'ü hesaplamaktır.

Eşdeğerlilik,

${\displaystyle G=f^{64}(4),{\text{ burada }}f(n)=3\uparrow ^{n}3,}$

f'nin üstindisi, fonksiyon tekrarını belirtir. Örn, f ⁴(n) = f(f(f(f(n)))). f fonksiyonu, hiper() fonksiyon ailesinin özel bir durumudur. ${\displaystyle f(n)={\text{hiper}}(3,n+2,3)}$ ve Conway dizisi ok gösteriminde şöyle ifade edilebilir; ${\displaystyle f(n)=3\rightarrow 3\rightarrow n}$. Sonraki gösterim de G ile şöyle sınırlanır:

${\displaystyle 3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2.\,}$

Graham sayısının büyüklüğü

Graham sayısının muazzam boyutunun zorluğunu ifade etmek için, 64 terimden meydana gelen dizinin sadece ilkini (g₁) üstel olarak ifade etmek bize birazcık yardımcı olabilir. Önce tetrasyon (${\displaystyle \uparrow \uparrow }$) gösterimi:

${\displaystyle g_{1}=3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots ))}$

Sağdaki ifadede bulunan 3'lerin sayısı,

${\displaystyle 3\uparrow \uparrow \uparrow 3\ =\ 3\uparrow \uparrow (3\uparrow \uparrow 3)}$'dür.

Şimdi her tetrasyon (${\displaystyle \uparrow \uparrow }$) işlemi bir üstel kule (${\displaystyle \uparrow }$) azalır ve şöyle olur;

${\displaystyle 3\uparrow \uparrow X\ =\ 3\uparrow (3\uparrow (3\uparrow \dots (3\uparrow 3)\dots ))\ =\ 3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\quad {\text{burada X tane 3 var}}.}$

Buradan,

${\displaystyle g_{1}=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots ))\quad {\text{ ,3lerin sayısı }}\quad 3\uparrow \uparrow (3\uparrow \uparrow 3)}$

olur. Sadece tekrarlı "üslü kuleler" şunlardır;

${\displaystyle g_{1}=\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{3}}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\dots \left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3\quad {\text{buradaki kulelerin sayısı }}\quad \left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3}$

ve her bir kuledeki 3'lerin sayısı, tam solundaki kuleden başlar ve sağdaki kulenin değerine eşittir.

Diğer bir yöntemler, g₁ şöyle hesaplanır: Öncelikle kulelerin sayısı bulunur. n = 3^3^3^...^3 (buradaki 3'lerin sayısı 3^3^3 = 7625597484987 tanedir) Sonra n^. kule şu seriye göre hesaplanır:

      1. kule: 3

      2. kule: 3^3^3 (3'lerin sayısı 3'dür) = 7625597484987

      3. kule: 3^3^3^3...^3 (3'lerin sayısı 7625597484987'dir) = ...

      .
      .
      .

 g1 = n. kule: 3^3^3^3^3^3^3^...^3 (3'lerin sayısı n-1. kulenin değeri kadardır)

Ardışık her bir kuledeki 3'lerin sayısı, bir önceki kulenin değeri kadardır. Daha henüz üçüncü kulenin değeri bile n oldu.

Bu ilk g₁ teriminin büyüklüğü, her ne kadar yukarıdaki gösterimlerle basitleştirilmiş olsa bile, akıl almaz derecede büyüktür. g₁ için n kule sayısı Planck uzunluğundan (yaklaşık olarak 10^185 tane) bile çok büyüktür. Bu ilk terimden sonra geriye, g nin değerleri aşırı şekilde artarak çoğalan 63 tane daha terim kaldı. Graham sayısı G = g₆₄'dir.

Graham sayısının en sağındaki rakamlar

Graham sayısı, 3${\displaystyle \uparrow \uparrow }$ formunun "üslü kule"sidir. En sağındaki rakamlar tüm benzer kuleler için bazı özellikler gösterir. Bu özelliklerden biri, tüm kulelerin yüksekliği d'den daha büyüktür ve en sağdaki rakamlar aynı seriye sahiptir. Bu en genel özelliktir. Tüm kulelerin yüksekliği d, en sağındaki rakamlar d+2'den daha büyüktür, Kulenin en tepesindeki "3" bağımsızdır. Örneğin en üstteki "3", en sağdaki d rakamlarını etkisinde kalmaksızın diğer negatif olmayan tam sayılarla değiştirilebilir.

Aşağıdaki tablo d'nin birkaç değerini gösteriyor.

3${\displaystyle \uparrow }$3${\displaystyle \uparrow }$...3${\displaystyle \uparrow }$x değerlerinin mümkün olan farklı sayıları. En sağdaki d rakamları göz ardı edildi

Rakam sayısı (d)	3${\displaystyle \uparrow }$x	3${\displaystyle \uparrow }$3${\displaystyle \uparrow }$x	3${\displaystyle \uparrow }$3${\displaystyle \uparrow }$3${\displaystyle \uparrow }$x	3${\displaystyle \uparrow }$3${\displaystyle \uparrow }$3${\displaystyle \uparrow }$3${\displaystyle \uparrow }$x	3${\displaystyle \uparrow }$3${\displaystyle \uparrow }$3${\displaystyle \uparrow }$3${\displaystyle \uparrow }$3${\displaystyle \uparrow }$x
1	4 (1,3,9,7)	2 (3,7)	1 (7)	1 (7)	1 (7)
2	20 (01,03,...,87,...,67)	4 (03,27,83,87)	2 (27,87)	1 (87)	1 (87)
3	100 (001,003,...,387,...,667)	20 (003,027,...387,...,587)	4 (027,987,227,387)	2 (987,387)	1 (387)

Aşağıdaki algoritma, Graham sayısının (veya 500'den daha fazla 3 içeren kulenin) en sağındaki 500 tane rakamı gösteriyor:

...02425950695064738395657479136519351798334535362521
   43003540126026771622672160419810652263169355188780
   38814483140652526168785095552646051071172000997092
   91249544378887496062882911725063001303622934916080
   25459461494578871427832350829242102091825896753560
   43086993801689249889268099510169055919951195027887
   17830837018340236474548882222161573228010132974509
   27344594504343300901096928025352751833289884461508
   94042482650181938515625357963996189939679054966380
   03222348723967018485186439059104575627262464195387.

Ayrıca bakınız

• Friedman sonlu formu
• Ackermann işlevi

Kaynakça

Dış bağlantılar

• "Geoff Exoo'nun Hiperküplerdeki bir Ramsey Problemi 20 Nisan 2010 tarihinde Wayback Machine sitesinde arşivlendi."
• Mathworld maddesinde Graham sayısı 16 Şubat 2010 tarihinde Wayback Machine sitesinde arşivlendi.
• Graham sayısı nasıl hesaplanır 13 Şubat 2010 tarihinde Wayback Machine sitesinde arşivlendi.
• Numeropedia - Sayılar için Özel Ansiklopedi