Meşgul Kunduz (Busy Beaver): Sayılabilir Ama Hesaplanamayan Fonksiyon

Bir oyun: en uzun ne kadar çalışabilirsin?

Hayal edin: elinize basit bir bilgisayar verildi. Bu bilgisayarın sadece $n$ durumu var ve 0/1 yazabilen sonsuz bir bant üzerinde çalışıyor. Bant başlangıçta hep 0.

Oyun: $n$ durumlu programlar arasında, eninde sonunda durmak şartıyla en uzun çalışan programı bulun. Bu programın yazdığı 1'lerin sayısı $\Sigma(n)$ — "Meşgul Kunduz Fonksiyonu" — olsun.

Bu, Macar matematikçi Tibor Radó'nun 1962'de Ohio State'te tanımladığı bir problem. Çıktığı yer pratik bilgisayar bilimi değil, hesaplanabilirlik teorisidir.

Bilinen değerler

$n$ durum sayısı arttıkça $\Sigma(n)$ patlama gibi büyür:

$n$	$\Sigma(n)$
1	1
2	4
3	6
4	13
5	4098
6	en az $10^{18267}$
7	$\geq 10^{10^{10^{10^{10^{7.6}}}}}$ — hayal bile edilemez

$\Sigma(5) = 4098$ sadece 2024 Temmuz'da kesin olarak kanıtlandı (yıllarca açık kalmıştı). Tarafsız hesap, modern süper-bilgisayarların aylarca çalışmasıyla — yetmiş yıllık ortak bilgi-kanıtlama çabası — sonunda kapatıldı.

$\Sigma(6)$ hâlâ açık ve bilinmiyor.

Neden bu kadar zor?

Bir $n$ durumlu Turing makinesi sonlu sayıda farklı yapıdadır: kabaca $(4n+2)^{2n}$ tane. Yani $n=5$ için 16 milyar; $n=6$ için 232 trilyon makine.

Problem: bu makinelerden çoğu sonsuz döngüye girer. Hangi makinenin duracağını, hangisinin durmayacağını ayırt etmemiz gerekir. Ama durma problemi (Halting Problem) hesaplanamaz — yani genel bir algoritma yoktur.

Dolayısıyla $\Sigma(n)$'in kendisi hesaplanamaz fonksiyondur. Hiçbir Turing makinesi (yani hiçbir bilgisayar programı) $\Sigma$'yı genel olarak hesaplayamaz.

Küçük $n$ için tek tek elle/sayma ile bulunur; her yeni $n$ astronomik olarak daha zordur.

$\Sigma$ hesaplanabilir herhangi bir fonksiyonu aşar

Key teorem: $\Sigma(n)$, sonuçta her hesaplanabilir $f(n)$ fonksiyonundan büyüktür. Yani Ackermann fonksiyonu, faktöriyel-faktöriyel, hatta düşünebileceğiniz tüm "yavaş büyüyen" fonksiyonlardan büyük.

Kanıt (özet): eğer $\Sigma$'yı bir program hesaplayabilseydi, durma problemi çözülürdü (n durumlu makine $\Sigma(n)$ adımdan fazla çalışıyorsa hiç durmaz — kontrol ettir, hangisinin durmayacağını bilirsin). Çelişki.

Bu, bilinen en hızlı büyüyen "doğal" matematiksel fonksiyondur.

Goldbach ve diğer açık problemlerle bağlantı

Çok şaşırtıcı bir bağ var: $\Sigma(n)$'i bilmek, açık matematiksel sanıları kanıtlamamızı sağlar.

$\Sigma(n)$'i bilirsek: n durumlu bir Turing makinesi $\Sigma(n)$ adımdan sonra hâlâ çalışıyorsa hiç durmayacaktır. Bu sayede şu fikirleri uygulayabiliriz:

• Goldbach sanısı: "2'den büyük her çift sayı iki asalın toplamıdır". Bir Turing makinesi yazılabilir: tek tek çift sayıları kontrol et, ilk karşı örneği bulduğunda dur. Bu makinenin $n$ durumu vardır (somut bir sayı). Eğer $\Sigma(n)$'i bilirsek ve makine $\Sigma(n)$ adımı geçerse — Goldbach doğrudur!

• Riemann hipotezi: Aynı şekilde. Yetenekli yazarlar Riemann hipotezini kontrol eden 744 durumlu bir Turing makinesi inşa etti (Yedidia, Aaronson 2016). $\Sigma(744)$ bilinse Riemann hipotezi de bilinirdi.

• ZFC tutarlılığı: Bir matematiksel sistemde çelişki ararsa, $\Sigma$ değerini bilmek bu sistemin tutarlı olup olmadığını söyler.

Yani $\Sigma$ fonksiyonu tüm açık matematik problemlerinin cevabını içerir. Bilemediğimiz şey değer.

Aaronson'un katı sınıfı

MIT'li bilgisayar bilimcisi Scott Aaronson 2016'da gösterdi: yeterince büyük $n$ için $\Sigma(n)$ ZFC'de bağımsızdır. Yani matematiğin standart aksiyom sistemi (kümeler teorisinin Zermelo-Fraenkel + seçim aksiyomu hali) ile $\Sigma(n)$'in tam değeri kanıtlanamaz.

İlk bilinen bağımsız $n$: 7910 (sonraki yıllarda 748'e indirildi). Yani $\Sigma(748)$, ZFC'de kanıtlanamayan bir tam sayıdır. Garip bir gerçek: var olan ve sonlu olan bir sayı, formel sistemde "bilinemez".

Praktik anlamı

Busy Beaver doğrudan kullanışlı değildir; kuramsal bir mihenk taşıdır. Bizlere şunları söyler:

1. Hesaplanabilirlik teorisinde net bir sınır: "Hesaplanabilir fonksiyon" sınıfı keskin bir sınıra sahip.
2. Sonlu programlar sonsuz davranışa yol açabilir: bir 7-durumlu program 10^(10^10^...) adımı geçebilir.
3. Matematiğin nesnel kısıtları: Gödel'in eksiklik teoremlerinin somut, sayısal bir gösterimi.
4. Mütevazılık dersi: En küçük programlar, en büyük sayıları gizleyebilir.

"Beaver" neden?

Radó isim seçerken küçük bir nedenle: kunduzlar küçüktür ama çok çalışır, çok inşa eder. Küçük (n durumlu) makineler bantta bol "1" inşa eder — kunduz benzetmesi yapışmış.

Sonuç

Busy Beaver fonksiyonu, matematiksel düşüncenin sınırlarına dair en şiirsel örneklerden biri:

• Tanımı: lise öğrencisi anlayabilir.
• Değerleri: ilk birkaçı kolay, sonrası insan ürünü hiçbir gücün ulaşamayacağı kadar büyük.
• Hesaplanamaz: hiçbir algoritma genel olarak çözmez.
• ZFC'den bağımsız: matematik sisteminin ötesinde.
• Tüm açık problemleri içerir: bilebilseydik bilirdik.

"Sonsuz çoktur ama hesaplanabilir az; aralarında, $\Sigma(n)$ gibi denizler vardır."