https://music.apple.com/jp/album/halting-problem/6817057972
https://en.wikipedia.org/wiki/Halting_problem
対角線論法は、カントールが実数の非可算性を示すために使った手法です。「すべてを列挙したリスト」の対角成分を書き換えることで、リストに載っていない要素を作り出し、矛盾を導きます。チューリングの証明も同じ構造を持っています。仮に停止判定プログラムが存在するとして、それを自分自身に適用させると矛盾が生じる、というものです。アルバムの出発点として、問題を生む論理そのものを置いています。
チューリングマシンのテープは無限に続くものとして定義されているので、テープの終わりは存在しません。それでも観測者は待ち続けるしかありません。停止性問題を、証明の側ではなく、実行を見守る側から描いた曲名です。
ビジービーバー関数 BB(n) は、n 状態のチューリングマシンのうち、最終的に停止するものの中で最も長く動くものの実行ステップ数です。この関数はどんな計算可能関数よりも速く増大し、計算不能であることが知られています。BB(5) = 47,176,870 は2024年に共同研究プロジェクト bbchallenge によって確定しましたが、BB(6) は現在も分かっていません。「止まるけれど、止まるまでが途方もなく長い」ものの象徴です。
チューリングは1939年の論文で、停止判定のような計算不能な問いに一手で答える仮想の装置「オラクル」を導入しました。ただし、オラクルを持つ機械にも、その機械自身の停止性問題がやはり生じます。判定者を外部に置いても、問題は一段上に移るだけで消えません。そもそも現実にはそのオラクルは存在しないので、問いに答えは返ってきません。
"Halting State" は、チューリングマシンが計算を終えて止まる状態のことです。それに "Unreachable"（到達不能）が付いています。42分27秒のあいだ、聴き手はこの曲が終わりに向かっているのかどうかを、聴くことによっては判定できません（言い過ぎ、カッコつけ過ぎ）。再生時間という外部の情報、つまり一種のオラクルを見ない限り、分かるのは「まだ終わっていない」ことだけです。アルバムはここで、聴き手を停止性問題の観測者の位置に置いて閉じます。