BB(3, 3) zor bir problem

• Metin, Collatz benzeri bir problem çözülmeden durup durmadığı kanıtlanamayan 3 durumlu, 3 sembollü Turing makinelerini ele alıyor; bu yüzden BB(3,3) probleminin de bu Collatz benzeri problemi çözmek kadar zor olduğunu söylüyor.
• Yazar, "quasihalt" olup olmadığını kanıtlamak için Collatz benzeri problemin verimli bir simülasyonunu ya da tam çözümünü gerektiren bir Turing makinesi (TM) ailesinden söz ediyor.
• Yazar, sıradan Busy Beaver oyunundan örnekler getirdiğini ve Busy Beaver oyununa sonuç sağlayan çok sayıda TM keşfettiğini belirtiyor.
• Yazar, kalan 160 gayriresmî BB(3,3) direnççisinden biri olan "Bigfoot" adlı bir TM tanıtıyor.
• Bigfoot'un davranışı, a kümülatif toplamı tutarken b ve c üzerinde Collatz benzeri bir fonksiyonun yinelenmesi olarak açıklanıyor.
• Yazar, Bigfoot'un davranışını açıklamak için Markov zinciri teorisini kullanıyor ve Bigfoot'un "probviously" hiçbir zaman durmayacağı sonucuna varıyor.
• Yazar, iki dünyadan birinde yaşadığımızı öne sürüyor: Bigfoot'un durduğu dünya ya da sonsuza kadar çalıştığı dünya; kendisi bizim ikinci dünyada yaşadığımıza inanıyor.
• Yazar, bu tür makinelere Loch Ness Monster veya Chupacabra gibi efsanevi yaratıklara benzeterek "Cryptids" adını vermeyi öneriyor.
• Yazar, bu probleme nasıl saldırılabileceğine dair fikirleri davet ediyor ve BB(3,3) için bir ispatın hâlâ mümkün olduğuna dair umudunu dile getiriyor.
• Sonuç olarak yazar, kendi deneyimine göre Collatz benzeri problemler hakkında sorulabilecek soruların görece kolay ispatlananlar ile matematikçilerin bile nasıl ispatlayacağını bilmedikleri türler olmak üzere ikiye ayrıldığını söylüyor.

[GN⁺]

Hacker News görüşleri

• BB(3, 3)'ün karmaşıklığına dair tartışma; Collatz tipi bir problem olarak bilinse de, önyargılı davranış ve yalnızca tek bir yörüngenin dikkate alınması gerektiği için bunun mutlaka zor olmayabileceği iddiası.
• 748 durumlu bir Turing makinesi üzerine tartışma; ZFC (Zermelo-Fraenkel küme teorisi ve seçim aksiyomu) tutarsızsa duran bir makine. Bu makineyi BB(748) adımında çalıştırmanın sonuçları ve Gödel'in ikinci eksiklik teoremiyle olası çelişki konusundaki kafa karışıklığının dile getirilmesi.
• Yazarın yazım tarzının açık ve öz olması sayesinde okuyucuların konuyu lafı uzatmadan anlamasına yardımcı olduğuna dair övgü.
• BB'nin (Busy Beaver) hesaplanamaz olmasının ne anlama geldiği ve BB büyüdükçe her şeyin ispatlanmasının gerekip gerekmediğine dair soru.
• Tüm BB(x, y) problemlerinin Collatz benzeri problemlere indirgenebileceği ve dolayısıyla x ve y'nin herhangi bir değeri için BB(x, y)'yi bulmanın da Collatz benzeri bir probleme indirgenebileceği önerisi.
• Beeping Busy Beavers'ın (BBB) neden çok daha uzun süre çalışmadan önce yarı-durabildiğine dair soru; bunun, durma durumunu kullanmak zorunda olmamalarından kaynaklanabileceği önerisi.
• Durma probleminin gerçek dünyadaki tümevarım üzerindeki etkisine dair soru; verilen bir Turing makinesinin çıktı bandına farklı bir şey yazıp yazmayacağını belirleyebilen bir oracle içeren varsayımsal senaryo.
• Bu konuları anlamak için gereken ön bilgiye dair soru; iyi bir temel sağlayacak belirli konu veya dersler için talep.
• Belirli bir dizgenin, 1RB2RA1LC_2LC1RB2RB_---2LA1LA, nasıl okunması gerektiğine dair soru.