Bir zekâ testinde olduğunuzu hayal edin. Kolaydan zora doğru sıralanan, her biri ayrı ayrı kâğıtlara yazılmış 20 adet sorumuz var. İlk sorudan başlayarak önünüze koyuyorum ve siz çözdükçe ilerliyorum. Bir yandan da hangi soruyu kaç saniyede çözdüğünüzü bir kronometre yardımıyla ölçüyorum. Konsantresiniz, oldukça da iyi gidiyorsunuz. Son soruya kadar sorunsuz şekilde ilerlediniz. Fakat burada kronometreyi kapatarak bir kenara koyuyorum ve siz soruyu incelerken ben de yüzümde biraz endişeli, biraz da alaycı bir gülümsemeyle size bakıyorum.

1, 6, 21, 107, 47.176.870…?

Endişeliyim, çünkü ne ile uğraştığınızı fark etmediyseniz (ve bir de inat ederseniz) maalesef her ikimiz de çok uzun bir süre burada bekleyeceğiz demektir. Aynı zamanda alaycıyım, çünkü bırakın sorunun doğru cevabını bulmayı, sorunun ne olduğunu bile anlamadığınızı düşünüyorum. Siz ümitsizce bu sayılar arasında bir ilişki bulmak için çırpınıp dururken ben de sabırla pes etmenizi bekliyorum.

Çünkü doğru cevabı asla bulamayacaksınız. Bunlar Macar matematikçi Tibor Radó tarafından 1962 yılında tanımlanan Busy Beavers sayılarının ilk 5 elemanıdır. Müthiş bir hızla artarlar, aralarında tanımlanabilir bir ilişki yoktur ve bir noktadan sonra hesaplanmaları yıllar sürebilir (ya da kısaca, mümkün olmayabilir).

Çıkış noktası şu: Diyelim ki size bir bilgisayar programı gösterdim ve bana bu programın herhangi bir zamanda durup durmayacağını söylemenizi istedim. Programı çalıştırmaya başlamadan önce, bana sonsuza kadar çalışacağını veya herhangi bir zamanda duracağını söyleyebilir misiniz?

Söyleyemezsiniz. Buna meşhur “durma problemi” deniyor ve İngiliz Matematikçi Alan Turing 1936 yılında bu problemin çözülemez olduğunu ispatladı. Bundan yola çıkan Tibor Radó da durmadan en uzun süre çalışan Turing makinelerinin kaç adımda duracağını merak etti. İşte Busy Beavers sayıları da bize en uzun süre çalışan makinelerin durmadan önce maksimum kaç adım attığını gösteriyor. Yani, sonsuza kadar çalışmayan (veya kısır döngüye girmeyen) n kurallı bir Turing makinesi, en fazla BB(n) adım sonra durmak zorunda.

İşi daha da basitleştirmek adına gelin bir analoji kuralım:

Bir otelde çalıştığınızı düşünün. Otelde tek bir koridora yan yana yerleştirilmiş sonsuz sayıda oda bulunuyor. Başlangıçta bu odaların hepsinin ışıkları kapalı. Sizin göreviniz de bu odaların ışıklarını açıp kapatmak. Ama bunu aklınıza estiği gibi yapamazsınız, elinizdeki kural kitabına uygun şekilde yapmak zorundasınız. Sorumuz şu: Kural kitabı size durmanızı söylemeden önce en fazla kaç odanın ışığını açıp kapatabilirsiniz?

Yalnız çok önemli bir şey var: Bu oyunu sonsuza kadar oynamak istemiyoruz, kısır döngülere de girmek istemiyoruz. Bir noktada oyunu bitirelim, ama mümkün olduğu kadar uzun sürsün.

Tek bir kuralımız varsa, toplam 64 olası Turing makinemiz var demektir. Bu makinelerin 32 tanesi sonsuza kadar çalışır (bkz. Ek.1), 32 tanesi de maksimum 1 adımdan sonra durur (bkz. Ek.2). Dolayısıyla, BB(1)=1. 

Peki ya iki kuralımız olursa? Olasılık uzayında 20,736 olası Turing makinesi var! Burada hepsini sıralamamız mümkün değil ama bunların da bir kısmı sonsuza gidiyor, bir kısmı kendi içinde kısır döngüye gidiyor (bkz. Ek.3) ve kalanlar da bir süre sonra duruyor. Sonsuza kadar çalışmayan ve kısır döngüye girmeyen bir makine en fazla 6 adım sonra durmak zorunda. Dolayısıyla BB(2)=6. Benzer şekilde, 3 kurallı bir Turing Makinesi en fazla 21 adımdan sonra durmak zorunda, yani BB(3)=21. Bu ikisinin ispatı Radó ve onun doktora öğrencisi Shen Lin tarafından 1965 yılında yapıldı. Toplam 16 milyondan fazla olası Turing makinesi inanılmaz bir özveri ile tek tek kontrol edildi. Sonraki sayı olan BB(4)=107’nin ispatı ise tam 18 sene sonra, 1983 yılında Allen H. Brady tarafından yapıldı.

Beşinci sayının bulunması ise tam bir işkence oldu desek yeridir. 6 yıl sonra, 1989 yılında bilgisayar bilimcileri Heiner Marxen and Jürgen Buntrock durmadan tam 47,176,870 adım çalışan bir makine buldular. Fakat diğer tüm olasılıklar gözden geçirilmeden bu sonuç doğru kabul edilemezdi. Neticede, el elden üstündür denilerek 2022 yılında beşinci sayının bulunması için bir yarışma düzenlendi. Ve tam 35 yıl sonra, 2024 yılında bu sonucun doğruluğu ispatlandı. Yani, BB(5)=47,176,870.

Sırada BB(6) var. Ne olduğu hakkında hiçbir fikrimiz yok. Fakat minimum değeri 2↑↑↑5, zira bu adımda duran bir makine yakın zamanda keşfedildi. Bu sayının büyüklüğünü daha rahat kavrayabilmek için serinin ilk yazısına göz atabilirsiniz. Doğru cevap bu mu, bilmiyoruz. Diğer tüm olasılıkları gözden geçirmeden emin olmamızın bir yolu yok. Fakat en azından inanılmaz derecede büyük olduğuna (ve sonlu olduğuna) eminiz.

Busy beaver sayıları ile uğraşmanın bize ne kazandıracağını söyleyeyim. Yaşadığımız evreni daha iyi kavramamızı sağlayacak. Matematikte yüzyıllar boyunca çözülememiş bazı problemleri çözmemizi sağlayacak. Örneğin, Goldbach’s conjecture. Yani 2’den büyük her çift tam sayının iki asal sayının toplamı olarak belirtilebileceği iddiası. Unutmayın, siz bu yazıyı okurken 5 kurallı makineler daha yeni çözüldü, 6 kurallılar için ise sadece minimum değerler belirlendi. Henüz ne kadar yolun başında olduğumuzun ispatı ise şöyle:

2015 yılında GitHub’da yalnızca Goldbach hipotezi yanlışsa duran 27 kurallı bir Turing Makinesi için bir kod yayınlandı. Goldbach hipotezi, 2’den büyük her çift sayının iki asal sayının toplamı olarak ifade edilebileceğini iddia eder. Bu hipotezin doğrulanması (ya da yanlışlanması) sonsuz sayıda olduğu yaklaşık 2,300 yıl önce Öklid tarafından ispatlanan asal sayıların dağılımı hakkında bize önemli bilgiler verecek. Çok büyük sayılar için (4 x 10^18’e kadar) bu hipotezin doğruluğunu biliyoruz. Fakat hala elimizde genel bir çözüm yok. Bu bizim için bir üst sınır: Eğer makine BB(27) kadar adımda durmazsa onun asla durmayacağını bilirdik ve Goldbach hipotezi doğrulanmış olurdu. Eğer makine durursa, o zaman da bu aksi bir örnek bulduğumuz anlamına gelirdi ve hipotezin yanlış olduğunu anlardık. Fakat bu üzerinde uğraşmaya bile değmeyecek kadar büyük bir sayı. BB(4), BB(5) ve BB(6)’nın “alt limiti” arasındaki farka tekrar bakın. Serinin ikinci yazısına da bir atıf yapayım, BB(18)’in Graham sayısı’ndan büyük olduğunu biliyoruz (Hatta bazı kaynaklara göre bu sayı BB(16)’ya, bazılarına göre ise BB(14)’e kadar düşürülmüş). Artık BB(27)’nin ne olabileceğini hayal gücünüze bırakıyorum.

Bitmedi. 2016 yılında, Texas Üniversitesi’nde bilgisayar bilimcisi olan Scott Aaronson, Yuri Matiyasevich ve Stefan O’Rear ile birlikte yalnızca Riemann hipotezi yanlışsa duran 744 kurallı bir Turing makinesi geliştirdi. Tıpkı Goldbach hipotezi gibi, Riemann hipotezi de asal sayıların doğasını anlamamız için elzem olan, matematiğin en büyük çözülmemiş problemlerinden biri. Bu aynı zamanda Clay Mathematics Institute tarafından belirlenen Milenyum problemlerinden biri ve çözebilene 1 milyon dolarlık ödül mevcut.

Gelin bir adım daha öteye gidelim. Modern matematiğin neredeyse tamamı Zermelo-Fraenkel (ZF) küme teorisi üzerine kuruludur. 9 farklı aksiyomdan oluşur. Fazla teknik detayına girmeyeceğim ama bildiğimiz tüm matematiği yalnızca kümeler kullanarak ve paradokslara yol açmaksızın ifade edebilmemizi sağlar. İşte yine 2016 yılında Scott Aaronson ve öğrencisi Adam Yedidia yalnızca ZF küme teorisi tutarsız ise duran 7,910 kurallı bir Turing makinesi geliştirdi.

Şimdi, Gödel’in meşhur eksiklik teoremini hatırlayalım. 1931 yılında vardığı sonuçlar şunlardı:

1) Ögesel aritmetik içeren aksiyomatik bir sistem tutarlı ise eksiksiz değildir.

2) Ögesel aritmetik içeren aksiyomatik bir sistemin tutarlılığını sistemin kendi içinden (sistemin kendi formüllerini ve işlemlerini kullanarak) ispatlamak mümkün değildir.

ZF küme teorisi ögesel aritmetik içeren aksiyomatik bir sistem. Dolayısıyla bu sistemin tutarlılığını yine sistemin kendi içinden bir sayı olan BB(7,910) ile ispatlamak mümkün değil. Tamam, ama BB(7,910)’un bir sonucu olduğundan eminiz. Bu da bizi şu kaçınılmaz sonuca götürüyor: Eğer Gödel’in eksiklik teoremi doğru ise, BB(7,910) asla hesaplanamaz! İşte alın size matematiğin sınırları. Asla hesaplanamaz olanın izdüşümü. İşin daha da vahimi, O’Rear sonrasında bu sınırı BB(748)’e kadar düşürmüş. Ohio State Üniversitesi’nden matematik profesörü Harvey Friedman’a göre BB(50) doğru cevap olabilir. Hatta Scott Aaronson BB(20)’nin bile yeterli olabileceğini düşünüyor. İmkânsız sandığımızdan çok daha yakın olabilir. Yıllar önce sicim kuramcısı Leonard Susskind bir röportajında teorik fiziğin sınırlarına erişmiş olabileceğimizden bahsetmişti. Kim bilir, belki aynı şey matematik için de geçerlidir.

Bir sonraki yazı, TREE(3) hakkında olacak.

Barış Yalın Uzunlu

Ek.1: Tek kurallı sonsuza giden Turing Makinelerinin tam listesi

0: Kapat, 1: Aç, L: Sola git, R: Sağa git, H: Dur

Ek.2: Tek kurallı, tek bir adımdan sonra duran Turing makinelerinin tam listesi:

Ek.3: Hiçbir zaman durmayacak, kendi içinde kısır döngüye giren 2 kurallı bir Turing makinesi örneği: