BB(3, 3) neden zor: Bigfoot
(sligocki.com)- 3 durumlu, 3 sembollü Turing makinesi Bigfoot, boş banttan başlayınca durup durmadığını kanıtlamak için Collatz benzeri bir problemi çözmeyi gerektiren bir örnek; bu da (BB(3, 3))’ün de aynı ölçüde zor olabileceğini gösteriyor
- Bu makine, bbchallenge.org’daki (BB(3, 3)) için çözülmemiş 160 adaydan biri ve
1RB2RA1LC_2LC1RB2RB_---2LA1LAgeçiş tablosuyla tanımlanıyor - Davranışı, (A(a,b,c)) yapılandırmasının tekrarlanan kurallarına indirgeniyor; (b \bmod 6)’ya bağlı olarak a artıyor veya azalıyor ve yalnızca (a) 0’ın altına inmeye çalıştığında duruyor
- Boş banttan 69 adım sonra (A(2,1,2))’ye ulaşıyor; 24 milyon yinelemeden sonra (a = 3,999,888)’e kadar büyüyerek durma olasılığının deneysel olarak çok düşük göründüğünü gösteriyor
- (b \bmod 6) dizisi deterministik olsa da büyük ölçekte sağa 2/3, sola 1/3 eğilimli bir rastgele yürüyüşe benziyor; sonsuza kadar çalıştığını kanıtlamak için bu Collatz benzeri fonksiyonun durma geçişine ulaşmadığını göstermek gerekiyor
Bigfoot’un (BB(3, 3))’ü zorlaştırmasının nedeni
- 3 durumlu, 3 sembollü tek bir Turing makinesinin durup durmadığını kanıtlamak için Collatz benzeri bir problemi çözmek gerekiyor
- Dolayısıyla (BB(3, 3)) problemini çözmek, bu Collatz benzeri problemi çözmek kadar zor olabilir
- Paul Erdős, Collatz türü problemler için “Mathematics may not be ready for such problems” demişti
- Önceki yazı Mother of Giants, “Beeping” Busy Beaver aramasında bulunan bir Turing makinesi ailesini ele almıştı
- Bu ailede, quasihalt durumuna ulaşılıp ulaşılmadığını kanıtlamak için Collatz benzeri bir problemi verimli biçimde simüle etmek ya da tamamen çözmek gerekiyor
- Bigfoot, varyant bir oyunda değil, normal Busy Beaver oyununun içinde bulunmuş bir örnek
Mevcut Busy Beaver zorluk örnekleri
- İnsan eliyle tasarlanmış çeşitli Turing makineleri, belirli Busy Beaver değerlerini kanıtlamak için başka zor matematiksel önermelerin kanıtlanması gerektiğine dair örnekler sunuyor
- (BB(745)): ZFC’nin tutarlılığının kanıtlanması gerekiyor
- (BB(27)): Goldbach Conjecture’ın kanıtlanması gerekiyor
- (BB(15)) ve (BB(5,4)): (n > 8) iken (2^n)’in üçlü gösteriminde en az bir 2 rakamı bulunduğuna dair Erdős varsayımının kanıtlanması gerekiyor
- Ancak bu Busy Beaver değerleri şu anda erişilebilir aralığın dışında
- Son 60 yılda kanıtlanmış değerler yalnızca (BB(2), BB(3), BB(4), BB(2,3)); ayrıca (BB(6) > 10 \uparrow\uparrow 15) olduğu biliniyor
- Bigfoot analiz edilmeden önce (BB(3, 3))’ün kanıtlanabileceği düşünülüyordu
Bigfoot’un tanımı ve kaynağı
- Bu Turing makinesinin adı Bigfoot ve geçiş tablosu şu dizgeyle tanımlanıyor
1RB2RA1LC_2LC1RB2RB_---2LA1LA
- bbchallenge üzerinde kayıtlı bir makine
- Geçiş tablosu şöyle
| Durum | 0 | 1 | 2 |
|---|---|---|---|
| A | 1RB | 2RA | 1LC |
| B | 2LC | 1RB | 2RB |
| C | — | 2LA | 1LA |
- Bigfoot, bbchallenge.org Discord kanalında paylaşılan (BB(3,3))’ün geriye kalan gayriresmî 160 holdout adayından biri
- Bu belirli Turing makinesi, ilk kez 14 Ekim 2023’te aynı Discord kanalında @savask tarafından düşük seviyeli davranış açıklamasıyla birlikte paylaşıldı
- Sonraki analizde Collatz benzeri yapı ve eğilimli rastgele yürüyüş niteliği ortaya çıktı
(A(a,b,c)) yapılandırmasına indirgenen davranış
- Genel yapılandırmayı şöyle tanımlayalım
[ A(a, b, c) = 0^\infty ; 12^a ; 11^b ; \text{ <A } ; 11^c ; 0^\infty ]
- Bigfoot, (c \ge 1) olan bir (A(a,b,c)) yapılandırmasına girdiğinde aşağıdaki kurallar, sonraki davranışı durana kadar ya da sonsuza kadar tam olarak açıklar
[ \begin{array}{l} A(a, 6k, c) \to A(a, 8k+c-1, 2) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+1, c) \to A(a+1, 8k+c-1, 3) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+2, c) \to A(a-1, 8k+c+3, 2) \quad \text{if } a \ge 1 \ A(a, 6k+3, c) \to A(a, 8k+c+1, 5) \ A(a, 6k+4, c) \to A(a+1, 8k+c+3, 2) \ A(a, 6k+5, c) \to A(a, 8k+c+5, 3) \end{array} ]
[ A(0, 6k+2, c) \to \text{Halt}(16k+2c+7) ]
- Bu kurallar, (b) ve (c) parametreleri üzerinde bir Collatz benzeri fonksiyonu tekrarlar
- (a) birikimli bir değer gibi hareket eder
- (b \equiv 1 \pmod{6}) veya (b \equiv 4 \pmod{6}) ise (a) artar
- (b \equiv 2 \pmod{6}) ise (a) azalır
- Bigfoot yalnızca (a) 0’ın altına düşmeye çalıştığında durur
Boş banttan gözlenen yörünge
- Boş banttan başlanınca Bigfoot 69 adım sonra (A(2,1,2)) yapılandırmasına ulaşır
- Sonraki simülasyonda (a) düzenli olarak artıyor gibi görünür; 24 milyon yinelemeden sonra (a = 3,999,888) olur
- (b \bmod 6) kalanları dizisinin düzgün rastgele olduğu varsayılırsa bu süreç, sayı doğrusu üzerinde eğilimli bir rastgele yürüyüşe eşdeğerdir
- Her adımda sağa gitme olasılığı (\frac{2}{3})
- Sola gitme olasılığı (\frac{1}{3})
- Markov chain teorisinde, mevcut konum (a=n) iken gelecekte (a=-1)’e ulaşma olasılığının ((\frac{1}{2})^{n+1}) olduğu kanıtlanabilir
- Gerçek (b \bmod 6) dizisi rastgele değil, tamamen deterministiktir ve tutarlı biçimde tek-tek-çift-çift örüntüsünü izler
- Buna rağmen büyük ölçekte rastgele Markov chain’e benzer bir yörünge gösterir
- 24 milyon adımdan sonra Markov chain’in sağa 8 milyon kez, sola 4 milyon kez hareket etmesi beklenir
- Bu, gerçek (a) değeri olan yaklaşık 4 milyona çok yakındır
Durmayacağına dair “Probviously” sezgisi
- (a \approx 4,000,000) olduğu noktada rastgele Markov chain’in (a=-1)’e ulaşma olasılığı yaklaşık ((\frac{1}{2})^{4,000,000})’dir
- Bu sayı, bilimsel açıdan başarısızlığı garantili sayacak kadar küçüktür
- Bigfoot, Markov chain’e benzer davranıyorsa durmayacak gibi görünür
- Ancak bu katı bir matematiksel önerme değil, deneysel bir sezgiseldir
- Bigfoot’un bir googolplex yinelemeden sonra durma olasılığı da dışlanamaz
- John Conway, Collatz varsayımının “probviously” doğru olacağına dair sezgiseli açıklamak için bu ifadeyi üretmişti; ancak Collatz kanıtı hâlâ görünürde yok
Bigfoot’un olası iki sonu
- Bigfoot ikisinden biridir
- Durur
- Sonsuza kadar çalışır
- Duruyorsa, Collatz benzeri fonksiyonun yinelemeleri yeterince hızlandırılıp sona kadar simüle edilerek bu kanıtlanabilir
- Sonsuza kadar çalışıyorsa, bu Collatz benzeri fonksiyonun (a=0)’daki durma geçişine asla ulaşmadığını kanıtlamak gerekir
- Markov chain sezgisine göre ikinci durum daha olası görünür ve bunun kanıtlanması çok daha zor görünmektedir
Cryptids adı
- Bu tür makinelerin davranışı nispeten basit matematiksel kurallara indirgenebilir; ancak bu kurallar açık matematik problemleri sınıfına girer
- Durduğu ya da durmadığına dair yalnızca söylentiler bulunan, fakat iki yönde de somut kanıt sunulamayan efsanevi canlılara benzerler
- Bu makineler için Cryptids adının kullanılması önerildi
- Loch Ness Monster veya Chupacabra gibi efsanevi canlılarla kurulan bir benzetme
- Bu Turing makinesi rastgele yürüyormuş gibi göründüğü için Bigfoot adı verildi
Bu Collatz benzeri davranış gerçekten zor mu
- Bu belirli Collatz benzeri fonksiyonun dinamiği, daha önce neredeyse hiç analiz edilmemiş bir problem gibi görünüyor
- Biraz sayılar teorisi ve hesaplamayla yalnızca bu probleme uygulanabilecek zekice matematiksel özellikler bulma olasılığı hâlâ var
- Böyle bir özellik bulunursa (BB(3,3)) kanıtının hâlâ erişilebilir aralıkta olduğu anlaşılabilir
- Collatz benzeri problemlerde sorulabilecek sorular deneysel olarak iki türe ayrılır
- Nispeten önemsiz biçimde kanıtlanan sorular
- Hiçbir matematikçinin kanıt yöntemini bilmediği sorular
- Bigfoot’ta (b)’nin tek-tek-çift-çift örüntüsünü tekrarladığı gerçeği ya da geleneksel (3n+1) Collatz kuralı uygulandıktan sonra her zaman çift olup bir sonraki adımda 2’ye bölündüğü gerçeği birinci kategoriye girer
- Collatz sisteminin davranışına ilişkin neredeyse diğer tüm sorular ikinci kategoriye giren örnekler olarak görülebilir
81 durumlu alternatif ifade
- 18 Ekim 2023’te eklenen alternatif ifade, mevcut (A(a,b,c)) açıklamasının bazı kullanışsız yanlarını azaltır
- Mevcut açıklamada üç kullanışsızlık vardır
- (b) ve (c) parametreleri birbirine dolaşıktır
- Girdi modulo 6 ile çıktı modulo 8, ortak çarpan 2’ye sahiptir
- (b), tek-tek-çift-çift biçiminde tekrarlayan bir örüntü izler
- Matthew House, yeni yapılandırma şöyle tanımlanırsa bu sorunların önlenebileceğine dikkat çekti
[ B(a,b)=A(a,2b+1,2) ]
- (b=81k+r) alınır ve özgün 4 geçiş tek bir geçişte birleştirilirse Bigfoot’un Collatz benzeri davranışı 81 durumlu kurallarla ifade edilebilir
- Bu ifade, mevcut (A) ifadesinin üç özelliğini çözer ve klasik Collatz problemine daha benzer görünür
- Ancak 81 durumun tamamını ele almak gerektiğinden bir miktar hantal olur
- Bazı kurallar (a \ge 2) koşuluna bağlıdır
1 yorum
Hacker News yorumları
BB(3, 3)’ün kendisinin zor olmasından ziyade, Collatz türü problemleri kodladığını ve bu tür problemlerin genel olarak çok zor olduğunu söylemek daha doğru görünüyor
Ancak bu belirli örneğin gerçekten zor olup olmadığı ayrı bir mesele. Davranışı epey tek tarafa yatkın görünüyor; çünkü klasik Collatz problemindeki gibi tüm tam sayıların yörüngelerine bakmak yerine yalnızca tek bir yörüngeye bakmak gerekiyor
Tek yörüngeye karşı çoklu yörünge noktasıyla da bir ölçüde katılıyorum. Ancak bu Turing makinesinin durmadığı bir dünyada olduğumuzu varsayarsak, bu sistemin tek yörüngesini kanıtlamak, klasik Collatz varsayımındaki tek bir yörüngeden “daha zor” görülebilir. Collatz varsayımı doğruysa, herhangi bir tekil yörünge kanıtı nihayetinde sonlu bir hesaplamadan ibaret olur; oysa yazıdaki tekil yörüngenin sonsuza dek durmadığını göstermek gerekir ve bu daha incelikli matematik ister
Abartmak istemem. Bu, BB(3, 3)’ü çözmek için Collatz varsayımını ya da iyi çalışılmış matematikteki açık bir problemi mutlaka kanıtlamak gerektiği anlamına gelmiyor. Yine de iyi incelenmiş bir probleme benzeyen zor bir problem olduğu yönündeki “ikinci en iyi” sonuç bile anlamlı bence. Bu Collatz benzeri problemin ne kadar zor olduğunu, kimin çözebildiğine bakarak göreceğiz
Burada konuyu anlamaya yardımcı olmak istiyorum. 748 durumlu bir Turing makinesi var [0] ve benim anladığım kadarıyla bu makine yalnızca ZFC çelişkiliyse duruyor
Bu makine, bilgisayarda uygulanıp çalıştırılabilen “fiziksel” bir nesne. Mevcut hesaplama gücü yetersiz olsa da ilke olarak bu makineyi BB(748) adım boyunca çalıştırmayı engelleyen bir şey yok. Durursa Teorem 1 gereği ZFC’nin çelişkili olduğunu kanıtlamış oluruz; durmazsa da ZFC’nin tutarlı olduğunu kanıtlamış gibi görünürüz
Kafa karışıklığının özü bu. Soyut bir sonuç değil, fiilen yürütülüp bir değer elde edilebilecek bir hesaplama gibi görünüyor
Elbette Gödel’in ikinci eksiklik teoremine göre ZFC içinde ZFC’nin tutarlılığı kanıtlanamaz. Ama yukarıdaki Turing makinesi durursa ZFC’nin tutarlı olduğunu kanıtlamış olacağız gibi görünüyor; bu da bir çelişki gibi duruyor
Nerede hata var? Şu anki tahminim, Teorem 1’in kanıtında 748 durumlu Turing makinesinin yalnızca ZFC çelişkili olduğunda durduğunu göstermek için ZFC’den daha güçlü bir metateori kullanıldığı yönünde. Öyleyse ortada çelişki yok. BB(748) adım boyunca çalıştırabilsek bile bu yalnızca ZFC+’nın ZFC’nin tutarlılığını kanıtladığını gösterir; bu da zaten biliniyor. Örneğin ZFC + “erişilemez bir kardinal vardır” böyle bir rol oynar
Makaleyi ayrıntılı incelemedim, gerçekten böyle mi bilmiyorum. Bu konu üzerine derinlemesine düşünmüş biri bir içgörü paylaşabilir mi?
[0] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...
Meşgul kunduz tanrısı bize bu değeri söyleseydi, teorik olarak Turing makinesini o kadar süre çalıştırabilir ve dediğin gibi ZFC’nin tutarlı olup olmadığını kanıtlayabilirdik. Ama insanların BB(748)’i hesaplayabilmesi için fiilen bu belirli 748 durumlu Turing makinesinin bir gün durup durmayacağını ve diğer tüm 748 durumlu Turing makinelerinin de durup durmayacağını bulması gerekir
Evrendeki tüm madde ve enerjiyi kullanarak bir bilgisayar yapsak ve o bilgisayar bu tek işi fiziksel olarak mümkün olan en yüksek verimlilikle yapsa bile hesaplamayı bitiremez
Bu yüzden matematiğin fizikten ve gerçeklikten ayrıldığı bir nokta ortaya çıkıyor. Böyle nesneler hakkında konuşup akıl yürütebiliriz, ama artık fiziksel anlam taşımazlar
Ama durmadığını kanıtlamak çok daha zordur. TREE(3) adım boyunca çalıştırmak, TREE(3)+1’inci adımda durmayacağının kanıtı değildir
Bu yüzden ne yazık ki “sadece çalıştırmak yeter” diyemeyiz
Yazarın üslubunu beğendim. Konuyu anlamaya yardımcı olurken gereğinden uzun görünmüyordu; bu denge noktasını tutturmak kolay değil
İlgili kaynaklar: https://nickdrozd.github.io/2020/08/13/beeping-busy-beavers.... ve https://googology.fandom.com/wiki/Googology_Wiki
BB'nin hesaplanamaz olması ne anlama geliyor? BB büyüdükçe matematiğin tamamını kapsıyor ve sonunda her şeyi kanıtlamak gerektiği anlamına mı geliyor, merak ediyorum
Matematiğin geri kalanı durma problemi üzerinden BB'nin içine gizlice sokulur. Herhangi bir matematiksel varsayımın doğru ya da yanlış olduğu durumda duracak bir program yazılabildiği için, durma problemini veya BB'yi çözmeye çalışmak tüm matematiği bilmeyi gerektirir[0]. Bu, Turing tamlığının hesaplanabilirliğin sınırı olması sayesinde mümkündür. Bir bilgisayarı içinde barındırabilen şeyin kendisi de bilgisayardır
[0] Aslında durmayı kararlaştırılamaz yapan şey tek başına bu değildir. Kararlaştırılamazlık, varsayımsal bir durma karar vericisinin kendisinin durmayacağını söylediği durumda duran bir program gibi, programın “kendi kendisini durma probleminin içine çekmesinden” kaynaklanır
Kanıtlayamayacağımızı da çürütemeyeceğimizi de “bildiğimiz” matematik problemleri vardır. Her önermenin hem doğru hem yanlış olarak kanıtlanabildiği bir durum yoksa, Gödel'in birinci eksiklik teoremi bunu söyler. Eğer her önerme hem doğru hem yanlış olarak kanıtlanabiliyorsa o kanıt sistemi işe yaramazdır; kanıtlamanın hiçbir anlamı kalmaz, dolayısıyla böyle olmayan başka bir kanıt sistemi seçmek gerekir. Bu yüzden genelde ilk durumun, yani ne kanıtlanabilen ne de çürütülebilen problemlerin var olduğu varsayılır. Ek olarak, Gödel'in ikinci eksiklik teoremi, ilk durumda olduğumuzu asla kanıtlayamayacağımızı söyler
BB'nin hesaplanamaz olması da, BB büyüdüğünde bir noktada yalnızca kanıtlanamayan ve çürütülemeyen bir problem doğru olduğunda duran bir programı kodlayabileceği anlamına gelir. Bu nedenle o programın durup durmadığı kanıtlanamaz
Katı anlamda, kanıtlanamayan ve çürütülemeyen bir şeyi kanıtlamak ya da çürütmek yanlış bir şeyi kanıtlamak demektir; bu da sonunda her önermeyi “kanıtlamak” için kullanılabilir. Bu yüzden “matematiğin tamamını kapsar” ifadesi bir anlamda doğrudur. Ancak bu bir eşik koşuludur ve “tüm” matematik problemlerini kodlayabilecek kadar büyük bir Turing makinesi ortaya çıkmadan çok önce devreye girer. Gerçekte tüm matematik problemlerini kodlamaya yetecek sonlu bir durum sayısı yoktur; çünkü aritmetik dizgeleri sürekli daha da uzatabilirsiniz
Bundan sonra çözemeyeceğimiz BB'lerin varlığı şaşırtıcı değildir; hangi BB'lerin çözülebilir, hangilerinin çözülemez olduğunu araştırmak ilginç hâle gelir
“Dolayısıyla BB(3, 3) problemini çözmek, en azından bu Collatz benzeri problemi çözmek kadar zordur” kısmının neden şaşırtıcı olduğunu anlamıyorum. Aslında neredeyse apaçık kanıtlanıyor gibi görünüyor. Tüm BB(x, y) problemleri Collatz türü problemlere indirgenmiyor mu?
BB(x, y) kolayca durma problemine dönüştürülebilir. x durumlu ve y sembollü tüm makineler içinde duranları bulur, durmayanları ayrı tutarsınız. Sonra duran makinelerin hepsini birer adım birlikte çalıştırıp hepsi durana kadar sürdürürsünüz; çalıştırılan adım sayısı BB(x, y) değeri olur
Conway'in durma problemini Collatz türü problemlere indirgeme yöntemini gösterdiğini biliyorum. Öyleyse BB'den durma problemine, oradan da Collatz problemine giden iki aşamalı indirgemeyle, herhangi x, y için BB(x, y)'yi Collatz türü bir probleme indirgemek mümkün görünüyor
Gerekli olan şey Collatz'tan durma problemine, oradan da B(x,y)'ye giden bir indirgemedir. Collatz'tan durma problemine gitmek apaçıktır, ama durma probleminden B(x,y)'ye gitmek daha az apaçıktır. Collatz'tan indirgenebilen ama B(3,3)'ten daha zor olmayan durma problemi altkümesinin tam olarak ne olduğunu tanımlamak gerekir
Durma problemi, hesaplanabilir programlara dayanan algoritmik bilgi teorisini ve tümevarıma yönelik birçok yaklaşımı sık sık “engelliyor” gibi görünüyor. Ancak durma probleminin gerçek dünyadaki tümevarım yeteneği üzerinde maddi bir etkisi olup olmadığına dair araştırma var mı, merak ediyorum
Örneğin bir oracle'ın, herhangi bir monoton evrensel Turing makinesinin çalışırken artık çıktı bandına hiçbir şey yazmayacağı bir noktaya ulaşıp ulaşmadığını söylediğini varsayalım. Bu oracle ile yapılan tümevarım sonuçları, program uzayını tam arayıp bir program yeterince büyük n adım boyunca çıktı üretmezse basitçe bir sonraki programa “atlayan” yöntemden çok farklı olur mu?
BB(3,3) gibi özel olarak üretilmiş sınır durumlarından ya da hasmane örneklerden değil, “sıradan” sıkıştırılabilir veriler üzerindeki tümevarımdan söz ediyorum
Bir güvenlik araştırmacısı olarak bizzat fuzzer yazıyorum. Fuzzer, test edilen program için güvenlik açısından anlamlı girdileri otomatik olarak bulan bir araçtır. Girdileri algoritmik olarak üretip değiştirir, programa verir ve saniyede onlarca, yüzlerce, binlerce kez ne olduğunu gözlemler
Bir girdi programı çökertirse, bunu programı “durdurmuş” sayabiliriz. Herhangi bir program için tüm hataları gerçekçi bir süre içinde bulacak bir fuzzer yapmak için durma problemini çözmek gerekir gibi geliyor. Nitekim milyarlarca testten sonra bile görüntü çözücülerde hâlâ hata bulan insanlar var; yani elimizdeki fuzzer'ların mükemmel olmadığı kesin
Aynı zamanda gerçek dünyada fuzzer'ların yeterli süre verildiğinde karmaşık programların içine beklenenden daha derine sızdığını da gördüm. Test edilen yazılımın yaptığı girdi doğrulama, modern PC'lerin sınırlı bellek ve depolaması fuzzer'ı bir ölçüde raya oturtuyor. Ancak kriptografi işin içine girerse istisna oluşuyor; fuzzer için hesaplamalı bir katran çukuru gibi. İyi savunulan ve iyi tanımlanmış programlar, fuzzer'ın durma problemini çözmek zorunda kalmaması için kendi korkulukları gibi davranıyor
Bu yüzden programlardaki güvenlik hatalarını bulma konusunda şöyle bakıyorum: Kriptografi hariç, fuzzer'lar sıkı girdi doğrulaması yapan programları hedeflemede güçlüdür. Buna karşılık sıkı girdi doğrulaması yapmayan programlarda fuzzer'a özellikle ihtiyaç yoktur; böyle yerlerde fuzzer'ın mutlaka iyi çalışması da gerekmez
BBB, yani bipleyen meşgul kunduz neden yarı-durmadan önce çok daha uzun süre çalışabilir; buna dair bir sezgi var mı?
Görünen bir şey, fiilen durma durumunu kullanmaya gerek olmaması. Bu anlamda 3 durumlu BBB, 4 durumlu BB’ye benziyor olabilir. Bunun dışında başka bir şey var mı merak ediyorum.
Bu yüzden X boyutunda bir programın veya Turing makinesinin, Y boyutundaki — Y >> X olacak şekilde — tüm programları çalıştırmasını simüle edecek hale getirebilirsiniz. Bu programlardan biri her durduğunda bip çıkarmasını sağlarsanız, son bip, BB(Y)’nin BB(Y)’den daha fazla adımdan sonra durmasını simüle ederken gerçekleşir. Dolayısıyla BBB(X) > BB(Y) >> BB(X) olur.
Yanlış hatırlamıyorsam temelde aynı kurgu nedeniyle, BB(N)’i biliyorsanız N boyutuna kadar olan programların durma problemini çok yavaş hesaplayabilirsiniz; BBB(N)’i biliyorsanız bu boyuta kadar olan durma oracle’ı verilmiş Turing makineleri için durma problemini çok daha yavaş hesaplayabilirsiniz.
Bu benim için fazla nerd işi.
Bunu anlamak için hangi ön bilgi gerekiyor merak ediyorum. Temel kalkülüs bilmek yeterli mi? Hangi belirli konular veya dersler iyi bir temel olur?
[1] https://www.scottaaronson.com/writings/bignumbers.html
Giriş düzeyinde bir teorik bilgisayar bilimi ders kitabını takip ederseniz çoğunu anlamanıza yardımcı olur. Bilgisayar bilimi öğrencileri bunu genellikle 1. veya 2. sınıfta öğrenir ve kolay değildir. Bizim okulda en korkulan sınavlardan biriydi.
Hopcroft & Ullmann’ın giriş kitabı iyidir. Yine de ilgili içerik çok geniş olduğu için bunu daha çok bir başlangıç noktası olarak görmek gerekir.
Birçok bilgisayar bilimi lisans programında açık materyalleri olan dersler vardır.
1RB2RA1LC_2LC1RB2RB_---2LA1LAnasıl okunmalı?https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA
Örneğin durum B ise ve mevcut kafa konumundaki bant değeri 0 ise, 2 yazar, kafayı sola bir kare hareket ettirir ve C durumuna geçer.
Bu 3 karakter, yazılacak sembolü, yeni durumu ve hareket yönünü ifade eder.
---durumu durmadır.(durum, bant değeri)çifti,(yeni bant değeri, bant kafasının hareket yönü, yeni durum)üçlüsüne eşlenir.[0] https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA