何の話かと言うと
上記の書籍では、チャイティンの定数 Ω の説明とそれに関連した Lisp の独自実装コードが紹介されていますが、講義録という性質上、説明がやや言葉足らずで、コードの中身を読み込んで、はじめて「なるほど」と理解できた部分がいろいろあります。その「なるほど」の部分の覚書です。(筆者個人の理解ですので、理解に誤りがあるかも知れません。)
チャイティンの定数とは
別名で「プログラムの停止確率」とも呼ばれるもので、プログラムコード p のビット数を |p| として、

で与えられます。なのですが、これだけでは、なぜこれが「確率」になるのかわからないですよね・・・。まずは、プログラムの実行環境を明示する必要があります。
実は、チャイティンの実装では、Mathematica で実装した独自の拡張 Lisp インタープリターが用いられており、プログラムを表すバイナリーコード(ビット列) p は次のように解釈されます。
(1) |p| が8の倍数で無い時は、正しいプログラムコードとは見なさない
(2) |p| が8の倍数の時は、8ビットごとにASCIIコードで文字に変換して、得られた文字列が「Lisp の正しい S 式 + 終端文字 "\n"」であれば、正しいプログラムコードと見なす
(3) 得られた文字列が 「Lisp の正しい S 式 + 終端文字 "\n"」でなければ、正しいプログラムコードとは見なさない
終端文字 "\n" の存在によって、正しいプログラムコード p に対して、p の後ろにさらにビットを加えたものは、決して、正しいプログラムコードにはなりません。(正しい S 式の途中には終端文字 "\n" は含まれることはありません。)この点に注意すると、この意味での「正しいプログラム」の集合を P として、

が成り立つことが分かります。
たとえば、「0」「1」がどちらも正しいプログラムだとすると(本当は正しくありませんが・・・)、2ビット以上の正しいプログラムは存在しないので、

となります。
あるいは、「0」と「10」が正しいプログラムのすべて(先頭2ビットが「11」はすべて正しいプログラムでは無い)とすると、

となります。
さらに、次のような思考実験をしてみましょう。何度もコインを投げてランダムなビット列を生成していって、
・正しいプログラム p が得られる
・これ以上続けても、永遠に正しいプログラムにはならないビット列(上記の「11」のような場合)が得られる
のどちらかになったらそこでコイン投げを停止します。この方法で、正しいプログラム p が得られる確率は
ですので、

は、まさに(この思考実験のプロセスにおいて)「正しいプログラムが得られる確率」に一致します。
そしてさらに、正しいプログラム全体は、「停止するプログラム(S 式の評価が有限時間で完了する)」と「停止しないプログラム(S 式の評価が永遠に完了しない)」に分類されますので、(上記の思考実験のプロセスにおいて)「停止するプログラムが得られる確率」が冒頭で説明した「プログラムの停止確率 Ω」になります。

終端文字の導入によって、「正しいプログラムにビットを付け加えたものは決して正しいプログラムにならない」という部分は上記の書籍を理解するかなり大きなポイントですが、書籍内でほとんど説明されていないので注意が必要です。(唯一あるとすれば、p.21 で受講者の質問に対して「妥当なプログラムの拡張は、妥当なプログラムにはなりません」と答えている部分でしょうか。)
Ωを計算する方法
Ωを二進数で表記すると、

のような値になると想像できますが、特定の N について、「小数点以下 N 桁目までの値」を計算することは可能でしょうか?
たとえば、1ビットのプログラム「0」が(本当にはそうではありませんが仮に)正しいプログラムで、実行してみたら(運よく)停止したとします。この事実から、

であり、

と1桁目が決定できます。(
の可能性もありますが、その場合は、無限小数展開で
と表記するものとします。)
そこで、プログラムのサイズを1ビットずつ大きくしながら、すべての正しいプログラムが停止するか確かめていけば、Ωの値を1桁ずつ決定していくことができるでしょうか?
残念ながらそうは行きません。
先ほどは、「0」が正しいプログラムで、さらに(運良く)停止したのでよかったのですが、もしも、「0」も「1」も正しいプログラムでなければ、さらに先のビットを見ないとΩの1桁目は決まりません。また、あるビット数で正しいプログラムが得られた際に、これを実行してもいつまでたっても停止しなかったとします。プログラムが停止するかを判定する汎用のアルゴリズムはありませんので、(プログラムの内容によっては)実行時間が足りなくてまだ停止しないだけなのか、本当に停止しないのかが判別できないことが起こり得ます。そうなると、この手続きはこれ以上先に進めなくなるので、「小数点以下 N 桁目までの値」がどうがんばっても計算できなくなる N が必ず存在することになります。
ちなみに、「これ以外に何かもっとうまい手続きがあるかも・・・」と思うかも知れませんが、それが存在しないことが、冒頭の書籍で証明されている、

という関係から分かることになります。(この証明はあとで紹介します。)
単調増加列としてΩの下限を与えるコード
Ωの各桁を個別に計算することはできないと言いましたが、「Ωは少なくともX以上である」というXを計算することはできます。また、計算時間を長くすれば、Xの値を下から上に(Ωの真の値に)徐々に近づけていくことができます。具体的には、引数 n を取る、次のような関数 Omega(n) が実装されています。
(1) n ビットのコードをすべて生成する
(2) 生成したコードを順番に実行する。ただし、制限時間を n として、n ステップの処理で終了しなかった場合は、そこで打ち切る。(正しいプログラムでない場合は、実行時エラーで終了する)
(3) 打ち切られずに正常終了したコード p について、
を足し上げた値を返す
簡単ですね。ただし、微妙な注意点があります(書籍の中では明確には説明されていませんが・・・)。先ほど、「正しいプログラムコードの条件」として、
・8ビットごとにASCIIコードで文字に変換して、得られた文字列が「Lisp の正しい S 式 + 終端文字 "\n"」であれば、正しいプログラムコードと見なす
と説明しました。チャイティンの実装したコード(Mathematica で実装した Lisp インタープリター)をよーーーーく読み解くと、文字列に変換した際に「正しい S 式 "\n" 余分なコード」となるビット列が与えられた場合、上記の (2) のステップでは、前半の「正しい S 式 "\n"」のみを取り出して実行するようになっています。つまり、(1) のステップで生成されるビット列には、実質的には、「n ビット以下のすべての正しいコード」が含まれており、Omega(n) は、
・(制限時間 n の範囲で)停止する n ビット以下のすべての正しいコード
を洗い出すようになっているのです。
そのため、n を大きくしていくと、「正常終了が確認できるコードの集合」には新たな要素が追加されていき、Omega(n) の出力も単調に増加していきます。そして、停止可能な任意のプログラムコードは、十分大きな n で必ず検出されるはずですので(この n がどのぐらい大きければよいかが分からない所が本質的な問題ではあるのですが)、理論上は、
の極限で、Omega(n) は Ω に収束することになります。
で、実際にチャイティンが実装した Omega(n) の実行結果を見ると、
・Omega(0) 〜 Omega(7):すべて 0
・Omega(8) = 1 / 256
という結果になっています。落ち着いて考えるとわかるのですが、7ビット以下では正しいプログラムコードは1つも表現できないので、Omega(0) 〜 Omega(7) がすべて 0 なのはその通りですね。(実行したら即座にエラーで終了する。)一方、8ビット以下の場合、1つだけ正しいプログラムコードが作れます。何でしょう・・・・
そう。「"\n"(終端文字のみ)」です。
つまり中身のまったくないコードです。ただ、Lisp のコードとしては、正しく実行することができて、実行結果は、「nil」もしくは「()」となります。これが、Omega(8) = 1 / 256(
)の正体です。これにより、(チャイティンが実装した Lisp の実装においては)

が証明できたことになります。
ただし、繰り返しになりますが、Ωの小数点以下8桁目までが
と確定したわけでありません。さらに大きな n を試していけば、Omega(n) の出力値は、これらの桁が変化するほどに大きくなる可能性は残されています。(9ビット以上のコードのかなりの割合が停止しないといけないので、ほぼほぼ確定している気はしますが、証明されているわけではありません。)
Omega(n) の実装に関する注意点
割と細かい話なのですが、Omega(n) の実装をよく見ると、
・n ビットのコードをすべて生成して、(時間制限 n において)実行が正常に停止したものについて、
を足し上げる
という処理を行っています。これをそのまま理解すると、「n ビット以下のすべての正しいコード p について、
を足し上げる」という意図した処理にならないようにも思えます。
なのですが・・・これで正しい実装になっています。先ほど触れたように、チャイティンの実装したコード(Mathematica で実装した Lisp インタープリター)は、文字列に変換した際に「正しい S 式 "\n" 余分なコード」となるビット列が与えられた場合、前半の「正しい S 式 "\n"」のみを取り出して実行します。従って、「n ビット以下のすべてのコード」の中には、(p = ( A B C ) を正しいコードの1つとして)「( A B C )"\n"hoge」とか「( A B C )"\n"hoga」など、p と解釈されるコードが重複してふくまれています。これらの重複を含めて、
を足し上げれば、結果的に、1つの p に対して
を1回加えるのと同じ結果になります。こんなトリッキーな事が文章で明示的に解説されていないのは、なかなか辛いです。。。