BB(3, 3)は難しい

• 本文では、停止するかどうかを証明するために Collatz 類似問題を解かなければならない 3状態・3記号のチューリングマシンについて論じており、そのため BB(3,3) 問題はこの Collatz 類似問題を解くのと同じくらい難しいと述べている。
• 著者は、「quasihalt」かどうかを証明するために、Collatz 類似問題の効率的なシミュレーションまたは完全な解決を必要とするチューリングマシン（TM）のファミリーに言及している。
• 著者は通常の Busy Beaver ゲームで例を見つけ、Busy Beaver ゲームに結果を与える多数の TM を発見した。
• 著者は「Bigfoot」という TM を紹介している。これは、非公式な BB(3,3) の未解決候補 160 個のうちの 1 つである。
• Bigfoot の挙動は、a が累積和を保持しながら、b と c に対する Collatz 類似関数を反復するものとして説明されている。
• 著者はマルコフ連鎖理論を使って Bigfoot の挙動を説明し、Bigfoot は「probviously」決して停止しないと結論づけている。
• 著者は、私たちは Bigfoot が停止する世界か永遠に実行される世界のどちらかに住んでおり、自分たちは後者の世界に住んでいると信じていると提案している。
• 著者は、この種の機械を「Cryptids」と呼ぶことを提案しており、Loch Ness Monster や Chupacabra のような伝説上の生物への比喩を用いている。
• 著者は、この問題に取り組む方法についてのアイデアを募り、BB(3,3) の証明が依然として可能であるという希望を表明している。
• 著者は結論として、自身の経験では、Collatz 類似問題について問えることには、比較的簡単に証明できるものと、数学者ですら証明方法を知らないものの 2 種類しかないと述べている。

[GN⁺]

Hacker Newsの意見

• BB(3, 3) の複雑さについての議論。Collatz 型の問題として知られているが、偏った振る舞いと単一の軌道だけを考えればよいため、必ずしも難しいとは限らないという主張。
• 748 状態のチューリングマシンについての議論。ZFC（Zermelo-Fraenkel 集合論と選択公理）が無矛盾でないなら停止するマシン。BB(748) ステップでこのマシンを実行することの含意と、ゲーデルの第二不完全性定理との潜在的な矛盾についての混乱の表明。
• 著者の文体が明快で簡潔であり、読者が冗長さなしに主題を理解する助けになっているという称賛。
• BB（Busy Beaver）が計算不可能であるとはどういう意味か、そして BB が成長するにつれてあらゆることを証明しなければならないのかという問い。
• すべての BB(x, y) 問題は Collatz のような問題に帰着でき、したがって任意の x と y に対する BB(x, y) を見つけることも Collatz のような問題に帰着できるのではないかという提案。
• Beeping Busy Beavers（BBB）が、はるかに長く実行される前になぜ準停止できるのかという問い。停止状態を使う必要がないからかもしれないという提案。
• 停止性問題が現実世界の帰納に与える影響への疑問。与えられたチューリングマシンが出力テープに何か別のものを出力するかどうかを判定できるオラクルを含む仮想的なシナリオ。
• こうした話題を理解するために必要な前提知識についての質問。良い基礎を与えてくれる特定のテーマや科目の要望。
• 特定の文字列 1RB2RA1LC_2LC1RB2RB_---2LA1LA をどのように読めばよいのかという質問。