Tek bir bilardo topu her hesaplamayı yapabilir: program masanın şekli

"Turing tam" ne demek, neden bir top için şaşırtıcı

Alan Turing 1936'da hesaplamanın soyut bir modelini tanımladı: sonsuz bir şerit, şerit üzerinde sembolleri okuyup yazan bir kafa, ve sonlu sayıda durumdan oluşan basit bir kural tablosu. Bir sistem bu makinenin yapabildiği her şeyi taklit edebiliyorsa ona "Turing tam" denir. Telefonunuz Turing tamdır, tablo programınız Turing tamdır, hatta bazı kart oyunları Turing tamdır.

Turing tamlığın ilginç yanı, getirdiği sınırdır. Turing aynı makaleyle "durma problemi"ni de kanıtladı: verilen bir programın sonunda duracağını mı yoksa sonsuza dek çalışacağını mı önceden söyleyen genel bir yöntem yoktur. Bu bir bilgi eksikliği değil, mantıksal bir imkânsızlık. Dolayısıyla bir fiziksel sistem Turing tamsa, o sistemin geleceğine dair bazı sorular da kesin olarak cevapsız kalır.

İşte Miranda ve Ramos'un sonucu bu yüzden önemli. Bir bilardo masası, fiziğin en yalın sahnelerinden biri: bir noktasal parçacık, düz gidiyor, duvara çarpınca geliş açısına eşit açıyla yansıyor. Başka hiçbir şey yok. Bu kadar fakir bir kurallar dizisinin bütün bir hesaplama dünyasını taşıyabilmesi beklenen bir şey değildi.

Fredkin ve Toffoli'nin 1982'deki bilardo bilgisayarı

Bilardo ve hesaplama fikri yeni değil. Edward Fredkin ve Tommaso Toffoli, 1982'de International Journal of Theoretical Physics dergisinde yayımlanan "Conservative Logic" (Korunumlu Mantık) makalesinde, sürtünmesiz bir ortamda çarpışan bilardo toplarıyla mantık kapıları kurulabileceğini gösterdiler. İki topun çarpışması bir VE kapısı gibi davranabiliyordu: topların gelip gelmemesi girdi, çıkış yolları ise çıktıydı. Toplar ve duvarlar hiç enerji harcamadığı için bu model, ısı yaymayan tersinir bir bilgisayarın olabilirliğini tartışmanın da yoluydu.

Ama Fredkin-Toffoli düzeneği birden çok topa, topların birbiriyle çarpışmasına ve hassas biçimde zamanlanmış girdilere dayanıyordu. Yeni çalışmanın farkı tam burada: tek top, hareketli hiçbir parça yok, çarpışma yok. Miranda'nın Matematik Araştırma Merkezi'nin (CRM) duyurusunda söylediği gibi, "Hesaplama tokmaklarda olmuyor, sınırın şeklinde oluyor."

Otuz beş yıllık açık soru

Asıl soruyu 1990'da Cristopher Moore sormuştu. Physical Review Letters'da yayımlanan "Unpredictability and undecidability in dynamical systems" makalesinde Moore, üç serbestlik dereceli bir hareketin bir Turing makinesine denk olabileceğini gösterdi ve doğal ortam olarak üç boyutlu bilardoyu önerdi: aynalardan oluşan bir ormanda sekip duran bir parçacık. Moore, gerçekten alçak boyutlu sistemlerin evrensellik eşiğinin altında kalabileceğini de savunmuştu. Yani "düzlemde, iki boyutta olur mu?" sorusu açık kaldı.

Miranda ve Ramos'un yanıtı: olur. Makalenin özetindeki ifade net: "İki boyutlu bilardo sistemleri evrensel Turing makinelerini taklit edebilir."

Peki hafıza nerede duruyor?

Bir Turing makinesinin sonsuz şeridi var; bir bilardo masasının ise sonlu bir kenarı. Yazarların çözümü, bütün şerit içeriğini topun konumuna gömmek. Şeritteki semboller dizisi, üçlü tabanda yazılmış bir sayıya çevriliyor ve bu sayı bir aralıkta bir noktaya karşılık geliyor. Bu kodlama, matematikte Cantor kümesi diye bilinen yapıyı kullanır: bir doğru parçasını üçe bölüp ortasını atarak, sonra kalanlara aynısını yaparak elde edilen, sonsuza kadar incelen tozumsu küme. Okuma kafasının şerit üzerindeki yeri de aynı aralığa, uzunlukları üstel olarak küçülen kopyalar halinde yerleştiriliyor.

Masanın kendisi de buna göre kuruluyor. Makinenin her durumu için masanın içinde bir doğru parçası var; durumlar arası geçişler ise bu parçaları birbirine bağlayan koridorlar. Sembolü okuma ve yazma işini parabolik ve salınımlı eğri duvarlar yapıyor. Topun izlediği yol, hesabın kendisi oluyor.

Kurgunun püf noktalarından biri, Charles Bennett'in 1973'te kanıtladığı bir teoreme dayanması: her Turing makinesi için ona denk, geriye doğru da çalıştırılabilen "tersinir" bir Turing makinesi vardır. Bilardoda bu şart, çünkü topun yolları geri sarılabilir olmazsa iki farklı hesap yolu aynı noktada birbirine karışır.

Sonuç: kestirilemezliğin ikinci türü

Teoremin iki doğrudan sonucu var ve ikisi de bilardo dinamiğinin klasik sorularını kesiyor. Bir yörüngenin belirli bir bölgeye ulaşıp ulaşmayacağına karar vermek algoritmik olarak imkânsız; bir yörüngenin periyodik olup olmadığına, yani kendini tekrar edip etmediğine karar vermek de öyle. Bunlar "henüz bilmiyoruz" değil, "genel bir yöntemle hiç bilinemez" anlamında.

Miranda'nın CRM duyurusundaki ayrımı burada işe yarıyor: "Kaos bir hassasiyet engeli koyar; karar verilemezlik ise mantıksal bir engel koyar." Kaotik bir sistemde başlangıç koşulunu daha iyi ölçerseniz daha uzağı görebilirsiniz. Karar verilemez bir sistemde ise ölçümü sonsuz hassas yapsanız bile cevap yok.

Sınırı da söyleyelim

Bu bir masaüstü icadı değil. Kurgu, sonsuz hassasiyette bir başlangıç konumu ve sonsuz incelikte geometrik ayrıntı gerektiriyor; gerçek bir masada topun izleyeceği yol birkaç sekmeden sonra fizik tarafından bulanıklaştırılır. Sonucun değeri pratik değil kavramsal: karar verilemezliğin, çok parçacıklı karmaşık sistemlere gerek kalmadan, tek parçacıklı ve son derece tanıdık bir modelde ortaya çıkabildiğini gösteriyor.

Yazarlar bunun tamamen yapay bir kurgu olmadığını da vurguluyor: bilardolar, duvarları sert değil de kenara yaklaşınca hızla yükselen bir potansiyelle değiştirdiğinizde, pürüzsüz Hamilton sistemlerinin bir limiti olarak doğal biçimde ortaya çıkıyor. Makalenin özeti bu yüzden sert küre gazı modellerinden ve gök mekaniğindeki çarpışma zinciri limitlerinden söz ediyor.

Aynı ekibin daha önceki durağı

Miranda için bu, tanıdık bir yol. 2021'de Robert Cardona, Daniel Peralta-Salas ve Francisco Presas ile birlikte yine PNAS'ta yayımlanan çalışmada, üç boyutta Turing tam Euler akışları kurmuşlardı; yani bir akışkanın içindeki parçacığın nereye gideceğinin karar verilemez olabileceğini göstermişlerdi. Bilardo, aynı sorunun çok daha çıplak hali.

Miranda'nın açık bıraktığı soru, işin nereye gidebileceğini gösteriyor: yer çekiminin hesap yapmaya başlaması için kaç gezegen gerekir? Üç cisim probleminin iki yüz yıldır direnen zorluğunun altında, kaosun yanı sıra mantıksal bir imkânsızlık da yatıyor olabilir mi? Bilardo masası, bu sorunun en sade laboratuvarı olarak elimizde duruyor.

Fotoğraf: Д.Ильин: vectorization, CC0, Wikimedia Commons