昨今いかがお過ごしでしょうか。こちらは、ほんとビジーなので、無限に時間が欲しいと毎日天に祈っています。
ビジーといえば、ところで、
ビジービーバー関数と呼ばれる関数をご存知でしょうか。自然数上で定義された、大体こんなかんじの関数です。
BB(n)=1+∑i=0nlims→∞ψ(i,n,s).
この
ψ については、あとで説明しますが、
ψ は具体的な
原始再帰関数で、
s→∞ での極限はちゃんと収束します。なので、当然ながら、
BB も自然数上の well-defined な全域関数です。というか、仮に
ψ が具体的に何かということを知らなくても、上に書いたような極限がしっかり収束するような自然数上の関数
ψ であれば
何であろうとも、上の定義が well-defined な自然数上の全域関数を与えるということは（よほどラディカルな思想をお持ちでない限り）誰しも認めるところでしょう。まあつまりは、ビジービーバー関数とは、
よくある標準的な数学的関数です。むしろ、具体的な原始再帰関数から作られている分、数学に出てくるほとんどの関数よりも遥かに地に足の着いた定義ですね。
さて、そういうわけで今日は、計算不可能性に関する正しい勘を身につけよう、のコーナーです。
- ビジービーバー関数とはなにか
- 急増加階層とゲーデルの夢
- 急増加階層におけるビジービーバー関数
- 無限の彼方へ
- ジャンプ、ハイパージャンプ、スーパージャンプ
- 無限ゲームの決定性
- 再帰的マーロ順序数を越えて
- 無限時間チューリングマシン
- 年表とまとめ
▼ビジービーバー関数とはなにか
ビジービーバー関数についての妙な誤解が蔓延する理由として、オリジナルの定義が煩雑である、という点が挙げられると思われます。そこで、ここではビジービーバー関数の本質だけを取り出して議論することにしましょう。ビジービーバー関数の本質とはなにか、それは、
どんな計算可能関数よりも急増大する自然数上の全域関数、以上です。
この具体例を与えるために、万能な部分計算可能関数
φ というものを考えます。つまり、任意の部分計算可能関数
f:⊆N→N に対して、ある
e∈N が存在して、任意の
n∈N に対して
φ(e,n)≃f(n) を満たす部分関数
φ:⊆N2→N のことです。具体的には、たとえばみなさんの目の前にあるコンピュータ（かスマホあたり）が
φ ですね。
それではみなさんの手許には、
φ があるはずです。オリジナルの定義とは違いますが、次の関数
BB:N→N をビジービーバー関数と呼ぶことにしましょう。
BB(n)=1+∑i=0(i,n)∈dom(φ)nφ(i,n).
各
BB(n) の値は、高々
n 個の自然数値の和であるから、有限の値を取ります。また、
φ はただの具体的な計算可能関数ですから、ビジービーバー関数
BB も当然ながら、有限の自然数値を返す、 well-defined な全域関数です。この関数がどんな計算可能関数よりも急増大する全域関数であるということの証明は、読者の演習問題としましょう。まあ、そんなこんなでビジービーバー関数とはかくも具体的な関数なわけです。
いやいや、総和のところになんか
dom(φ) とかあるのが気持ち悪い……という人もいるかもしれません。普通の数学ではこれくらい全く問題ないので気にしませんが、数学慣れしてない人もいるかもしれませんので、
dom(φ) に言及しない定義も与えましょう。たとえばクリーネの標準形定理などを用いれば、どんな部分計算可能関数
φ も、ある原始再帰関数
ψ:N3→N の極限として記述できます。具体的には、
ψ(i,n,s) の値として、
φ(i,n) の計算が
s ステップ以内で停止しないならば
0 、停止するならばその出力値を返すものとすれば問題ありません。あるステップ
s 以降で
ψ(i,n,s) の値は安定するので、常に極限
lims→∞ψ(i,n,s) は存在します。これが、この記事の最初に書いた式の意味となります。
BB(n)=1+∑i=0nlims→∞ψ(i,n,s).
ここで、
ψ は実際に作れる具体的な原始再帰関数です。たとえば、クリーネの標準形定理などの証明を参考にすれば、容易にその定義を書き下すことはできるでしょう。計算論の講義などで実際に書き下したことのある人もいるかもしれません。ビジービーバー関数は、そのような具体的な原始再帰関数の極限の和、という単純な方法によって定義される、かなり普通の数学的関数なんですね。（もちろん、これは標準的な自然数上の全域関数、つまり、
n が有限の数ならば
BB(n) も有限の数として定義されます。）
そういうわけで、普通の数学では余裕でビジービーバー関数が全域関数であることが証明できることがわかりました。ここでは変則的な定義を用いましたが、オリジナルのビジービーバー関数の定義を用いても同様です。しかも普通の数学的関数と比べても、遥かにめちゃくちゃ具体的に定義された関数なので、当然ながら、超越的な公理は一切使わずに、その全域性が証明されます。
それでは、実際どれくらい弱い再帰的公理化可能理論でビジービーバー関数の全域性を証明可能でしょうか。答えを言えば、たとえば、ペアノ算術よりも遥かに弱い再帰的公理化可能理論である
IΣ2 と呼ばれる形式体系あたりでも、ビジービーバー関数の全域性を証明可能であると示すことができると思います。
IΣ2⊢ビジービーバー関数は全域関数である．
もちろん、算術で全域性を証明する場合には、ビジービーバー関数のうまい算術的定義式を与える必要があって面倒なのですが、そこはクリーネの
T-述語などを使った標準的なものを考えましょう。そうすれば、これはたとえば
IΣ1 における原始再帰関数の可証全域性証明などを参考にすれば証明できると思います。算術の証明論のはじめの方によく出てくるタイプの証明なので、興味がおありでしたら証明を考えてみてください。
ちなみに、ビジービーバー関数は受け入れられない、という主張は、「極限を認めない数学」に移行すれば、正当化できなくもないかもしれません。一応、そのような数学でも、多少の初等的な数学はできないこともないとわかっています。ただ、実際に「極限を認めない数学」で解析学とかをやるのは苦行だと思いますが、がんばってください
*1。
▼急増加階層とゲーデルの夢
急増加階層 (fast growing hierarchy) というものがあります。計算可能な急増大関数の増大度の指標として極めて便利な道具です。証明論では、公理系の強さの指標のひとつとして、可証全域計算可能関数が急増加階層のどのレベルに達するか、というものを用いることがあります。詳細はググるか巨大数論をご参考にしてください。
可算順序数の基本列が与えられたとき、対応する急増加関数というものが定義可能です。ここは巨大数界隈の皆さんも分かった上でやっているのでいまさらな話ですが、大きな計算可能順序数に対して何を標準的な基本列とするかは議論の余地が非常にあるところですね。とにかく、あくまで急増加階層は、順序数に対して定まるわけではなく、基本列依存の概念なわけです。
そういうわけで、通常は、順序数を直接取り扱うのではなく、基本列のデータ込みの順序数を取り扱います。たとえば、1938年、クリーネは
O と呼ばれる順序数記法系を導入しました。クリーネの
O とは、計算可能順序数の集合ではなく、気持ち的には、計算可能順序数に基本列の情報も入った木構造なわけですね。各
a∈O は、それが表す計算可能順序数とその基本列とさらにその基本列と……というデータを持っているわけです。
ところで、関係あるかどうか分からない話ですが、計算可能関数すべてを正確に覆い尽くす線形階層の存在は、ゲーデルが夢見ていたものです。ゲーデルはこれを、数理論理学におけるきわめて重大な問題であると述べていたそうです。現在のところ、このゲーデルの問題、つまり計算可能関数すべてを正確に覆い尽くす線形階層の存在は、未解決であるようです。たとえば、急増加関数の線形階層
(F[α])α<ωCK1 をうまく定義できるでしょうか。現行の急増加階層
F[α] は順序数依存ではなく基本列の選び方に激しく依存するので線形階層にはなっておりません。もし、基本列の選び方で誤差程度の影響しか出ないような急増加階層が計算可能な方法で定義でき、そして任意の計算可能関数
g の増大度がどれかの
F[α] で上から押さえられるようにできれば、これはゲーデルの大未解決問題の解決といっていいでしょう。
しかし、ジェラルド・サックスなどはスペクター有界性を用いた議論などから、部分的な否定的結果が導出されることに気づきました。そして、おそらくそのような階層は存在しないだろう、つまりゲーデルの問題は否定的に解決されるだろうと予想しています。現時点では、ゲーデルの問題の完全な否定的解決が与えられているわけではありませんが、計算可能関数すべてを正確に覆い尽くす長さ
ωCK1 の妥当な階層は存在しないであろう、という見解があるようです。
▼急増加階層におけるビジービーバー関数
ところで、巨大数界隈では、急増大関数
F[ωCK1] が大体ビジービーバー関数であると考えられているようです。もちろん、これは界隈でも、あくまで厳密な意味ではない、と分かった上でやっているそうなので、それほど問題視はしていません。
厳密な意味では、なぜ
F[ωCK1] をビジービーバー関数と考えるのが難しいかについて、どこかに具体的な記述があったほうがよいと思うので、ここで述べておきましょう。
ωCK1 の基本列を取ること自体には特にむずかしいことは一切ないのですが、どの基本列を取るか、には議論の余地が残るところです。もちろん、
ωCK1 の計算可能な基本列はありません。超算術的な基本列もありません、というのが有名なスペクター有界性の帰結です。
とはいえ別に
ωCK1 の基本列を取ること自体はふつうの行為です。数理論理学では、クリーネの
O の
Π11-パスを取るという行為はきわめて標準的で、これから適当な方法で
ωCK1 の基本列を作ることができます。ただ、この
Π11-パスから作った急増大関数が、ビジービーバー関数程度の増大度になるかどうかというと、一般的にはもっと遥かに急増大したりすると思います。
また、ビジービーバー関数は、計算可能関数全てより急増大する関数の中では最弱に近いとはいえ、別に最弱でもありません。急増大関数
F[ωCK1] がこの中途半端な位置にあるビジービーバー関数と同程度になってくれる
ωCK1 の「自然な」基本列が都合よく存在するのかどうかはよくわかりません。しかし、急増大関数
F[ωCK1] がビジービーバー関数と同程度になるような
ωCK1 の技巧的な基本列がいちおう存在することは確かです。なので、まあ
F[ωCK1] がビジービーバー関数とおよそ同等であるという言説を否定することはできないでしょう。
さて、ビジービーバー関数を越える、
2 次ビジービーバー関数というものがあるそうです。若干、曖昧な記述の定義しかないのですが、これは停止問題から相対的な計算可能性に対するビジービーバー関数という理解で問題ないでしょうか。だとしたら、
2 次ビジービーバー関数はいわゆる
∅′-支配関数、
3 次ビジービーバー関数はいわゆる
∅′′-支配関数、一般に、計算可能順序数
α について、
α 次ビジービーバー関数は
∅(α)-支配関数と言ったところでしょうか。
これらも well-defined な全域関数です。一番簡単なビジービーバー関数の拡張ですね。
ふたたび余談ですが、2017年春期に担当した、学部
3 年生向け数理論理学の講義で、期末レポート問題の
1 つとして「
自然数上の急増大関数を作れ」という課題を与えてみました。学生の作ってきたものの中で第一位の関数の増大度は、
超算術的階層を全て支配する程度でした。つまり、任意の計算可能順序数
α に対する
α 次ビジービーバー関数全てよりも急増大する程度の関数ですね。わりとこの辺りの関数までなら思いつく学生もいるようです。
ただ、この学生の作ってきた関数の面白いところは、順序数概念などを一切使わずに、任意の
α 次ビジービーバー関数を越えていたところで、おお、すごい、賢い、と感心しました。関数の構成のアイデアとしては、後に述べるクリーネの高階計算論にかなり近いものでしたが、型
1 対象を計算するために型
2 対象を参照する高階計算論に相当するものを使って巨大関数を作ってきたのは、かなり冴えていると思います。
さて、英語圏のグーゴロジストの様子を見ると、
2 次ビジービーバー関数は
F[ωCK2] 程度の増大度であり、一般に
α 次ビジービーバー関数は
F[ωCKα] 程度の増大度であると一時期は思われていたようです。幸い、いまは、その名残がジャーゴンとして残っているだけで、
α 次ビジービーバー関数を
F[ωCKα] と書くのは厳密に言えば誤りだということは、界隈でもしっかりと把握されているようです。
しかし、
α 次ビジービーバー関数がおおよそ
F[ωCKα] というのは一見、妥当そうに見えなくもないですが、何が間違っているのでしょうか。実は、
ωCK1 はただの計算可能順序数の上限というだけではなく、そこそこやばい順序数です。ビジービーバー関数を神託に用いて計算可能な順序数の上限も
ωCK1 です。
2 次ビジービーバー関数を神託に用いて計算可能な順序数の上限も
ωCK1 です。一般に、
α 次ビジービーバー関数を神託に用いて計算可能な順序数の上限も
ωCK1 です。高次のビジービーバーになるにつれ、もちろん計算不可能度も徐々に上がっているのですが、実はそれだけでは
ωCK1 を越えるには至らないのです。そういうわけで、
α 次ビジービーバー程度では、計算不可能度がまだ弱すぎて、
ωCK1 の壁を越えることはできないんですね。
じつは、先ほど、クリーネの
O の
Π11-パスから作った急増大関数が、ビジービーバー関数程度の増大度になるかどうかを疑った理由はこれになります。つまり、たぶんふつうにクリーネの
O の
Π11-パスから適当に急増大関数を作ってしまうと、全ての計算可能順序数
α に対する
α 次ビジービーバー関数よりも急増大になることもあるのではないでしょうか。
▼無限の彼方へ
それでは、
ωCK1 の壁を突き破って
ωCK2 の先に向かうにはどうすればよいでしょうか。本記事の冒頭で、無限に時間が欲しいと言いましたが、それが答えのひとつです。無限に時間があれば
ωCK1 の壁を突き破れます。
無限時間チューリングマシンなんて、当初は誰もが、つまらない計算モデルだ、と考えたと思います。一般の順序数上の計算のアイデアなんて1960年に考案され、60年代〜80年代に膨大な数の順序数上の計算論の研究がなされ、もはや無限上の計算論なんて研究され尽くしたと考えられていたからです。そんなところに、こんなとんでもなく単純な計算モデルで面白い結果が出るわけがない。誰もがそう思ったはずです。
実際、無限時間チューリングマシンの仲間である「無限時間レジスターマシン」について言えば、大方の想像通り、（計算力に関しては）あまりおもしろくない計算モデルでした。また、もうひとつ類似の計算モデルである「順序数チューリングマシン」も、60年代の順序数上の計算論と発想が全く同じだし、新しいところはひとつもなさそうだ。これらと混同して、無限時間チューリングマシンもきっとつまらないだろう、という第一印象を持つ人も多いようです。
まず、誰もが思うことは、所詮、無限時間チューリングマシンの計算能力なんて超算術的階層くらいだろう。なぜかというと、大体、類似の計算モデルはいつもその程度だったからです。しかし、ちょっと考えてみると、超算術的階層を越えるということはすぐに分かります。だから、
ωCK1 ,
ωCK2 ,
ωCK3 等々はかんたんに計算してくれます。
まあとはいえ、せいぜい最小の
再帰的到達不可能順序数 (
recursively inaccessible ordinal) くらいで止まるだろう、とふつうは思うかもしれません。たとえば、無限時間レジスターマシンの計算能力は、最小の再帰的到達不可能順序数には程遠いレベルのかなり小さい順序数である
ωCKω で止まります。
しかし、無限時間チューリングマシンは再帰的到達不可能順序数も軽く超えてみせる。そこまで行けるならば、
再帰的超到達不可能順序数 (
recursively hyperinaccessible ordinal),
再帰的超超到達不可能順序数 (
recursively hyperhyperinaccessible ordinal), ……とどんどん順序数の階層を登っていくこともそう驚きではないでしょう。
とはいえ、いやいやさすがに最小の
再帰的マーロ順序数 (
recursively Mahlo ordinal)くらいで止まるだろう。そう思っているうちに、無限時間チューリングマシンは再帰的マーロ順序数なんて悠々と飛び越していきます。
実は、無限時間チューリングマシンの計算能力は、こんなマーロだのというしょうもないレベルではなく、もっと遥かに巨大な順序数を次々と越え、遠い世界まで行き着いていたことが判明します。そこら辺で、人々は「おや？」と思い始めるわけです。もしかして、この無限時間チューリングマシンとかいう計算モデルは面白いのではないか、と。
▼ジャンプ、ハイパージャンプ、スーパージャンプ
無限って、なんだろう。あるとき、ひとびとは、無限概念を理解するために、計算可能性を利用することを思いつきました。混沌とした無限の世界に、隠された秩序を見つけたい。無限を計算的に近似することによって、有限の秩序をもとに無限の世界を開拓できると考えたのかもしれません。1950年代、まず初めに着手されたのは、停止問題の累積階層とその超限拡張、すなわち
超算術的階層の研究でした。停止問題の超限累積の分析は、1950年代が終わる頃には深く研究が進み、そのような無限の入り口の世界には、非常に明快で美しい秩序が広がっていることが分かりました。そして、1960年には竹内外史が
順序数上の計算理論を導入、その後にクライゼルとサックスは、
メタ再帰理論と呼ばれる
ωCK1 上の計算理論を導入しました。
最小の計算不可能順序数
ωCK1 を飛び越す方法はたくさん知られているのですが、ひとつは、このような
ωCK1 上の計算論を用いる方法があります。この
ωCK1-計算論では、ゲーデルの構成可能宇宙の
ωCK1 ランク
LωCK1 の中のものは、あたかも"有限"のように扱ってよいとします。そうすると、通常の計算論で停止問題（
Σ1-完全述語）が計算可能性の領域を越えたように、
ωCK1-計算論では、
LωCK1 の
Σ1-完全述語に相当する自然数の部分集合（
Σ1-マスターコード）が
ωCK1-計算可能性の枠を越えます。これを相対化したものは、
ハイパージャンプと呼ばれます。（ちなみに、通常の教科書では、ふつうは1950年代的なクリーネの
O を用いた方法でハイパージャンプを定義することが多いです。）
これがようやく
ωCK1 の壁を越す最初の一手です。停止問題の累積（チューリングジャンプ）の超限階層では、
ωCK1 を飛び越すことはできません。ハイパージャンプは、
1 回の跳躍でチューリングジャンプの超限階層を追い抜き、
ωCK1 の壁を打ち破ります。実際、ハイパージャンプの累積階層がちょうど
ωCK1 ,
ωCK2 ,
ωCK3 ,
… という順序数の増大階層に対応します。つまり、ハイパージャンプ
1 回で
ωCK1 を計算できるようになり、ハイパージャンプ
2 回で
ωCK2 を計算できるようになり……という感じですね。
これによって、ハイパージャンプの階層は、
ωCKω,
ωCKε0,
ωCKωCK1,
ωCKωCKωCK1 などを次々に越えていきます。しかし、ハイパージャンプの階層を超限に伸ばしても、次の越えることのできない壁が現れます。それが
再帰的到達不可能順序数です。それでは、ハイパージャンプよりも凄いジャンプを作ることによって、どうにか再帰的到達不可能順序数を越えることはできないでしょうか。
ところで、1950年代末にクリーネは高階の計算理論を導入しました。この高階の計算理論が導入されたことにより、たとえばチューリング・ジャンプ作用素という高階関数（型
2 作用素）を神託に用いた計算といったようなものを考えることが出来るようになりました。これは、単に停止問題を神託に用いた計算可能性よりも強力な計算不可能性を生み出します。なぜなら、計算中で何度でもチューリング・ジャンプにアクセスすることができるので、チューリング・ジャンプ作用素から相対的な計算というものは、算術的階層も超算術的階層も作り上げることができるからです。これが、「
高階計算」という概念を歴史上最初に導入した1959年のクリーネの記念碑的論文で示された定理です。チューリング・ジャンプ作用素を神託として計算可能であることと、超算術的階層に属すことは同値である、と。
さて、このように型
2 作用素を神託とする高階計算論が導入されたことによる重要な点は、与えられたジャンプ作用素から相対的な計算可能性の（高階計算に対する）
停止問題を考えることが出来るという部分です。つまり、チューリング・ジャンプ作用素からの相対的計算可能性は、超算術的階層を覆うわけですから、その停止問題は超算術的階層を越えるわけです。事実、チューリング・ジャンプ作用素からの相対的計算の停止問題は、単発のハイパージャンプと同程度の計算能力になります。つまり、高階計算論を用いることで、
ωCK1 という概念に触れることなく、計算論的な概念のみで
ωCK1 を越えることができたわけですね。
では、このクリーネの高階計算論で、ハイパージャンプ作用素を高階関数として神託に使うとどうなるでしょう。このハイパージャンプ作用素の高階関数としての取り扱いは、1960年頃に柘植利之に導入されたものです。かつては、これは柘植の汎函数
E1 として知られていました。
これもまた、計算中に何度でもハイパージャンプにアクセスするので、ハイパージャンプの累積階層を生み出しています。そして、この累積階層の長さは、最小の再帰的到達不可能順序数の手前で止まります。実際、ハイパージャンプ作用素
E1 から計算可能な順序数の上界は、最小の再帰的到達不可能順序数
ωE11 となることが知られています。そして、ハイパージャンプ作用素
E1 から相対的な計算の停止問題は、この階層を越えます。
このハイパージャンプ作用素に相対的な停止問題を
ハイパーハイパージャンプと呼ぶことにしましょう。ハイパーハイパージャンプは最小の再帰的到達不可能順序数を越え、次の再帰的到達不可能順序数、さらに次の再帰的到達不可能順序数と進んでいきます。しかし、ハイパーハイパージャンプの超限累積も再帰的
超到達不可能順序数を越えることはできません。
1967年、チューリングの唯一の弟子であるガンディは、この発想を定式化した
スーパー・ジャンプ (
super jump) と呼ばれる型
3 作用素
SJ を導入しました。これは、ジャンプ概念という型
2 作用素を入力として、その停止問題を返す作用素ですから、従来のジャンプ概念よりも
1 つ高階の概念になるわけですね。ガンディのスーパージャンプ
SJ は、次のジャンプ概念を作り出します。チューリングジャンプを
SJ に与えたらハイパージャンプを返し、ハイパージャンプを
SJ に与えたらハイパーハイパージャンプを返します。これを
SJ に与えたらハイパー
×3 ジャンプが返ってくるわけですね。
こうして、スーパージャンプが新たなジャンプ概念を生成する毎に、再帰的到達不可能順序数、再帰的
超到達不可能順序数、再帰的
超超到達不可能順序数、と次のレベルの壁を順々に越えていくことになります。
しかし、スーパージャンプにも限界がありました。スーパージャンプには、
再帰的マーロ順序数の壁を越えることができないのです。
▼無限ゲームの決定性
余談ですが、
ωCK1 を越える、もうひとつの面白い例を上げましょう。完全情報
2 人プレイヤーゲームを考えます。この
2 人のプレイヤーは各ラウンドで交互に自然数を出していきます。
そうすると、第
n ラウンド時点では
(x0,y0,x1,y1,…,xn,yn) という有限数列が出来るわけですね。あらかじめ一階算術の
Σ1 論理式
φ が与えられているとします。もし、ある段階で
φ(x0,y0,x1,y1,…,xn,yn) が満たされたらプレイヤーIIの勝ちです（有限列は自然数でコードされていると考えてください）。
このように、プレイヤーIIの勝利条件が算術の
Σ1 論理式で書かれたゲームは
Σ1-
ゲームと呼ばれます。このようなゲームは、どちらかのプレイヤーが必勝戦略を持ちます。それでは、どちらのプレイヤーが必勝戦略を持つか、ということを判定するのは、どれくらいむずかしいでしょうか。
実は、この
Σ1-ゲームの必勝者判定問題は、単発のハイパージャンプと同じ計算不可能性を持ちます。したがって、「
ゲームの必勝者を決定する」という行為は、とんでもなく強力な計算不可能性を生み出す作用素と考えることができるわけです。
それでは、もう少し複雑な論理式を使ってゲームをしたらどうなるでしょう。最も単純な拡張方法は、勝利条件を与える論理式をより複雑にすることです。集合変数
Z を含む
Σ0n 論理式
φ(Z) が与えられているとしましょう。今考えているのは（高々）長さ
ω のゲームなので、各プレイは自然数列
X=(x0,y0,x1,y1,…,xn,yn,…) を与えます。もし
φ(X) を満たしていれば、プレイヤーIIの勝利です。このように、勝利条件が
Σ0n 論理式で書かれたゲームは
Σ0n-
ゲームと呼ばれます。でも、一般の
Σ0n-ゲームの必勝者判定問題は、ほんとうにやばいので、ここでは考えません。
もう少し論理式を細かく見ていきましょう。
Σ01-論理式
φ(Z) と
Π01 -論理式
ψ(Z) が与えられているとしましょう。ゲームのプレイ
X が
φ(X)∧ψ(X) を満たしたら、プレイヤーIIの勝利とします。このようなタイプのゲームに対する必勝者判定問題が、ちょうどハイパージャンプ
2 回分の計算不可能性です。
一般に勝利条件が
Σ01-論理式の有限ブール結合で書かれたゲームの必勝者判定問題が、ちょうどハイパージャンプ有限回に相当する計算不可能性です。そして、
Σ02-ゲームの必勝者判定問題は、超限回のハイパージャンプを大幅に飛び越していきます。
なんとなくこれで、「
あっ、ゲームの決定性って（いい意味で）
やばそうだな」と思ってもらえれば幸いです。しかし、決定性が本領を発揮するのはここから先で、ゲームの決定性のやばさはどんどん急加速していきます。一般の
n に対する
Σ0n-ゲームの必勝者判定問題は、本記事で言及するありとあらゆる計算不可能性を余裕で軽く飛び越すまじでやばい代物なので、触らぬ神に祟りなし、ということで本稿では一切触れません。
Σ11-ゲームの必勝戦略ともなると、なんかゲーデルの構成可能宇宙
L の情報とかコードし始めるし怖いので論外です。
▼再帰的マーロ順序数を越えて
さて、ガンディのスーパージャンプの話をもう少し丁寧に見ていきましょう。チューリングジャンプ作用素を
E0 , ハイパージャンプ作用素が
E1 で、スーパージャンプで作られたハイパー
×n ジャンプ作用素を
En と書くことにしましょう。一般に、与えられた高階対象
F に対して、
ωF1 を
F を神託に用いて計算可能な順序数の上限とします。
ωE11 は最小の再帰的到達不可能順序数になりますが、
ωEn1 はどれくらい巨大な順序数となるでしょうか。いま、再帰的到達不可能順序数の階層を考えましょう。
- α 番目の再帰的到達不可能順序数を τ0α をと書きます。
- β=τ0β なる順序数 β を再帰的超到達不可能順序数と呼び、 α 番目の再帰的超到達不可能順序数を τ1α と書きます。
- 一般に、 β=τνβ なる順序数 β を再帰的超ν+1到達不可能順序数と呼び、 α 番目の再帰的超ν+1到達不可能順序数を τν+1α と書きます。
- 極限順序数 λ については、任意の ν<λ について β=τνβ なる順序数 β を再帰的超λ到達不可能順序数と呼び、 α 番目の再帰的超λ到達不可能順序数を τλα と書きます。
このとき、一般に
ωEn1 は最小の再帰的超
n到達不可能順序数となります。また、これよりも更に大きな
再帰的マーロ順序数と呼ばれる順序数があり、これは常に
α=τα0 を満たします。1974年、ハーリントンは、最小の再帰的マーロ順序数がスーパージャンプを用いて計算可能な順序数の上限、つまり
ωSJ1 である、ということを証明しました。
それでは、再帰的マーロ順序数より先の世界を見ていきましょう。再帰的マーロ順序数
ρ は、
Lρ 上の如何なる計算も、ある許容順序数
α<ρ で計算が閉じている順序数として特徴付けられます。これを拡張して、
再帰的 2-
マーロ順序数 ρ とは、
Lρ 上の如何なる計算も、ある再帰的マーロ順序数
α<ρ で計算が閉じている順序数として定義します。これを繰り返して、再帰的
3-マーロ、再帰的
4-マーロ、一般的に再帰的
α-マーロと定義していきましょう。
再帰的超マーロ順序数 ρ とは、再帰的
ρ-マーロであることとします。
さて、再帰的マーロ順序数は許容順序数上
Π02-
反映順序数というものになりますが、この再帰的超マーロの階層を考えても、
Π03-
反映順序数には届かないようです。もし、
α が
Σ1-
可拡大、つまり、
Lα が真の
Σ1-初等拡大
Lκ を持つ（
+1-安定ともいう）ならば、必ず再帰的マーロであることが分かります。なぜかというと、
Lα 上の計算は
Lκ 上の計算を制限したものとして扱えますが、
Lκ 上のこの計算が部分構造
Lα で閉じていることが分かるので、
Σ1-初等性より、同様の事実が
Lα で模倣される、つまり、
Lα のある部分構造
Lβ で計算が閉じていることになるからです。実際、
Σ1-可拡大性はこれより強い性質で、任意の
n に対して
Π0n-
反映順序数であることを導くようです。
与えられた順序数
σ<λ に対して、
σ 以下の順序数をパラメータに用いた
Lλ-計算可能順序数の上界を
stλ(σ) と書くと、これは
σ より真に大きいもののうちで、
Lλ の
Σ1-部分構造となる最小の
L-階層を与えます。このようにして、与えられた
Lλ の中で
Σ1-可拡大順序数の上昇列を得ることができます。ただし、もちろん、
λ が最小の
Σ1-可拡大順序数より小さければ、
stλ(ω)=λ になるため、この列は長さ
1 で停止します。
順序数
κ が
λ へ
Σ1-射影可能とは、
κ から
λ への
Lκ-計算可能な単射があることを意味します。順序数
κ が
λ へ
Σ1-射影可能であるような最小の
λ は、
κ の
Σ1-
プロジェクタム (
projectum) と呼ばれます。（プロジェクタムの定義に
L-階層ではなく、Jensenの
J-階層を使うことも多く、その場合、本稿でのプロジェクタム
ω は、
J-階層でのプロジェクタム
1 となるので注意してください。）
この
Σ1-プロジェクタムが
ω であるという条件は、その宇宙で通常の計算論を模倣する際に重要な性質の
1 つになります。一方、
Σ1-プロジェクタムが
ω を越える順序数となると、非常に大きな順序数になります。なぜなら、
Σ1-可拡大順序数
stλ(σ) は
σ に
Σ1-射影可能ですので、
ω を始点とする
Σ1-可拡大順序数の真増大列の有限段階で
Σ1-プロジェクタム以上の値に行けるならば、この増大列を射影で逆行することによって、最終的に
ω へ
Σ1-射影可能になります。したがって、
ω を越える
Σ1-プロジェクタムの下には、
Σ1-可拡大順序数の無限増大列が佇んでいるはずです。
以上の議論より、最小の
Σ1-可拡大順序数より下の順序数、たとえば
ωSJ1 などの
Σ1-プロジェクタムは
ω であり、また、最小の安定順序数
δ12 の
Σ1-プロジェクタムも
ω となります。
Σ1-プロジェクタムが自分自身であるような順序数を
射影不能 (
nonprojectible)と呼びます。これは、
Lα が
Σ1-分出を満たすことと同値になります。これは非常に大きい順序数です。大きすぎてよくわかりませんが、最小の射影不能順序数は最小の
Π11-反映順序数や最小の
Σ11-反映順序数とは比べ物にならないくらい大きいようです。
一方で、「
α より下に
Σ1-射影できない
α を探せ」という
Σ1-探索を構成可能宇宙
L 全体に渡って行うと発見できますので、同じ現象が
Σ1-初等部分構造であるところの安定順序数階数で発生するはずです。したがって、
安定順序数の下には必ず射影不能順序数がいるはずですから、最小の射影不能順序数は
δ12 より下に出現するはずです。
まあ、ここら辺りが、通常、巨大可算順序数という括りで議論されるうちでは、最強クラスの順序数たちですね。
さて、1960年代〜1980年代に掛けて、一般再帰理論的計算モデルの様々な抽象化が考案されました。抽象
1-セクション、スペクタークラス、その他もろもろ色々あるのですが、これらは対応する順序数の
Σ1-プロジェクタムが
ω であることを導くものでした。つまり、たとえ超強力な計算モデルといえど、何かしらの意味で計算論と言えるものであれば、
Σ1-プロジェクタムが
ω である。
そういうわけで、わたしはてっきり、射影不能レベルの巨大順序数は、計算論的なモデルによる下からの構成では作れないと勘違いしていました。……
無限時間チューリングマシンを知るまでは。
▼無限時間チューリングマシン
さて、これまでに様々な計算論を見てきました。空間と時間を許容順序数
α で束縛したものが、
α-
再帰理論、つまり
Lα 上の計算論です。一方で、クリーネの高階計算論は、時間はチューリング計算と同様に
ω で束縛されつつも、記憶領域の束縛をある程度排除したものと考えることができます。
1989年、当時、大学院生だったジェフリー・キダーとジョエル・ハムキンスは、
無限時間チューリングマシンの概念を考案しました。この概念は、既に研究され尽くしていた、順序数上の計算概念と一体、何が違うのでしょうか。無限時間チューリングマシンは、物理的デバイスはふつうのチューリングマシンと全く同じです。ただ、時間の制約がないだけです。極限順序数ステップでも、状態、ヘッド位置、テープの各セルに書かれた文字が（固定した順序の下で）下極限値にリセットされ、そのまま計算が続いていく、というだけです。めちゃくちゃ簡単な計算モデルですね。
そういうわけで、無限時間チューリングマシンは、時間の束縛が皆無です。ただし、空間の束縛のために、ある一定以上の時間を掛ける計算は必ずループに陥るため、結果的に時間の制約は可算順序数に収まります。また、無限時間チューリングマシンで計算可能な集合のクラスは
Δ12 集合の範囲を越えられないということも自明です。
さて、無限時間チューリングマシンはちょっと特殊な計算モデルなので、何かの計算可能性を議論した際、何をもってして、それを計算したとみなすか、という点には議論の余地があります。チューリングマシンなので、計算結果は、出力テープに書き出されます。
そこで、ハムキンスとルイスは、「
書ける (
writable)」「
やがて書ける (
eventually writable)」「
たまたま書ける (
accidentally writable)」の
3 種類の出力概念を考察しました。訳語は適当なので、もっといい訳語を募集中です。はじめは「最終可筆 (eventually writable)」とか格好いい訳語を付けて本稿を執筆していたのですが、恥ずかしくなってきたのでやめました。
「書ける」というのは、計算を停止した際に、出力テープに書かれる、ということです。「やがて書ける」というのは、計算は停止状態に入らないかもしれないが、出力テープ上の文字列はあるステップ以降安定してしまい、そこに書かれている、ということです。「たまたま書ける」というのは、計算途中で出力テープ上に一度でも書かれることがある、ということとなります。
さて、無限時間チューリングマシンに対する停止問題を考えることもできます。これを無限時間停止問題と呼ぶことにしましょう。ハムキンスとルイスは、
無限時間停止問題の解は「書けない」けれども「やがて書ける」ということを証明しました。
それでは、無限時間停止問題を神託とした無限時間計算の無限時間停止問題、といったように、無限時間停止問題の累積階層を考えることもできます。実際、ハムキンスとルイスは、「やがて書ける」順序数回の無限時間停止問題の累積は「やがて書ける」ということを示しています。
そういうわけで、無限時間チューリングマシンで「書ける」ものよりも「やがて書ける」ものの方が遥かに多いわけです。それでは、「書ける」順序数の上限、「やがて書ける」順序数の上限、「たまたま書ける」順序数の上限をそれぞれ
λ,ζ,Σ と書くとしましょう。2000年、フィリップ・ウェルチが示したものは、
λ-
ζ-
Σ 定理と呼ばれる、次の定理です。
■ウェルチのλ-ζ-Σ 定理 ζ は最小の Σ2-可拡大順序数であり、 Lζ は LΣ の Σ2-初等部分構造となる。
さらに、 Lλ は Lζ の最小の Σ1-初等部分構造となる。
Lλ≺1Lζ≺2LΣ.
あっ、こいつらやばい順序数ですよ。よく見ると、この
ζ とか
Σ2-可拡大ってことは、つまりは
射影不能順序数です。しかも、初等部分構造の性質から「
Σ の下に射影不能順序数がある」という性質が
λ の下にも反映されて、
λ の下にも共終個の射影不能順序数が存在することが導かれるわけです。つまり、無限時間チューリングマシンは、
大量の射影不能順序数を書けるほどの計算能力を持つわけです。これは、とんでもないことですよ。
もうひとつ、最近、ウェルチによって証明された定理を紹介して、この話は締め括りましょう。先ほど、無限時間停止問題の概念を導入しましたが、この解は「やがて書ける」ので、「やがて書ける」範囲の外に飛び出すことはできません。したがって、代わりに「
無限時間やがて書くか問題」を考えましょう。これは、無限時間チューリングマシンの与えられたプログラムが、何かをやがて書く（つまり、出力テープの記述が安定する）かどうかを判定せよ、という問題です。この「無限時間やがて書くか問題」の解は、「やがて書けない」ということはすぐに分かります。
さて、停止問題に対するチューリングジャンプ作用素のように、「無限時間やがて書くか問題」から「
やがてジャンプ作用素」を作ることができます。さて、この型
2 作用素を用いた高階計算を行いましょう。ただし、ここでは無限時間高階計算を考えます。
2015年にウェルチによってアナウンスされたものは、以下のおどろきの定理です。
■ウェルチの定理 次の 2 つの問題は再帰的同型である。
- やがてジャンプ作用素を神託に用いた無限時間高階計算の停止問題
特に、この
2 つの問題の解の計算不可能度は、ぴったり一致するわけです。
ああ、「やがて書ける」のレベルでやばいのに、「やがてジャンプ」の超限累積を越え、「やがてジャンプ作用素を神託に用いた無限時間高階計算の停止問題」を持ってきて、人類はようやく
Σ03-ゲームの必勝者判定問題に辿り着けるんですね……。
あっ、ちなみに、まだ
Σ03-ゲームです。
3 です。ゲームの決定性、やばいですね
*2。
▼年表とまとめ
そういうわけで、
極小サイズ（ビジービーバー関数レベル）から
中サイズ（無限時間チューリングマシンレベル）の計算不可能性の話でした。あっ、念のため書いておくと、本稿で扱っている内容は（ゆるい意味で）構成的なので、ZF集合論より遥かに遥かに弱い体系で展開できます。ねんのため。
さて，巨大数界隈、計算可能レベルでは、極小サイズから大サイズに掛けて、徐々に段階的に理解している人が多いと思います。しかし、巨大数界隈では、計算
不可能レベルの話となると、
極小サイズから何故かいきなりすっ飛ばしてよく分からない
謎サイズに飛ぶ話ばかりなので、これが計算不可能性の理解の阻害になっているのではないかな、と思いました。実際には、計算不可能性にむずかしいことはなく、むしろ計算不可能の方が計算可能よりよっぽど分かりやすいです（個人的感想）。本記事が、計算不可能の
中間レベルを理解する助けになりましたら幸いです。
本記事の前半について、巨大数界隈でも一部のしっかりした人はちゃんと理解していて、Gwikiなどの議論を見るとかなり高度なことをやっている様子です。一方で、Gwikiでも平均的な層は勘違いしている感じもあったので、ちょっと心配になったのが、本稿を執筆する切っ掛けでした。特に、世の中、証明をせずに勘で数学概念を取り扱うスタイルの人がいて、まあそれはいいんですけど、こと計算不可能性となると、かなりの人の勘がことごとく間違っているので……。特にロジック周辺の数学を取り扱う場合、人間の勘の99パーセントは間違っている、可能な限りすべての都合の悪いことが発生する、というくらいのきもちでやらないと、どんどん間違った方向に進んでいくと思います。人間が間違った方向に進むのに歯止めをかけてくれるのが数学的証明なので。
とはいえ、個人的には、純粋に巨大数づくりを楽しんでいる人たちに対しては、この件については特に何も心配していないし、数学的厳密性を要求するつもりも一切ありません。そのまま楽しんでいってほしいです。心配しているのは、巨大数づくりの外にはみ出して、誤った勘に基づいた思想を流す人たちで、まあ、ゲーデルの不完全性定理の濫用にせよ、そういうのは数学基礎論周辺の分野では避けられない定めなのかもしれませんが
*3……。
さて、本稿で説明したものは、あくまで中レベルまでの計算不可能性に関する内容なので、本気の計算不可能巨大関数を作る際には、あまり役に立たないと思います。そういうわけで、あまり中レベルのところに深入りしても仕方がないかもしれませんが、一応参考文献を以下に書いておきます。
本稿の後半部の内容は、1960〜80年代に隆盛を極めた、
一般再帰理論 (
generalized recursion theory) と呼ばれる分野のものです。代表的な教科書は、
Perspectives in Logic で無料公開されています。このうち、Barwise (1975), Fenstad (1980), Sacks (1990), Hinman (1978) を全て読み込めば、ここで触れた内容のほとんどは完全に理解できると思います。ついでに Devlin (1984) も読むと、更に理解の幅が広がると思います。ただ、いずれの本も一長一短で、著者のクセが強く、記述が独特なので、どの本も読み込むのは非常に苦労すると思います。何かもう少し読みやすい教科書があればよいのですが……。
無限時間チューリングマシンについては、これらの教科書が刊行された後に考案された概念なので、一般再帰理論の教科書では扱われていません。
無限時間チューリングマシン周辺は、とてつもなく地雷論文が多く、極めて注意する必要があります。しかし、無限時間チューリングマシンの論文について、良い論文かどうかの判定方法は簡単です。それは、著者の中に Welch という名前の人物が入っているかどうか確認することです。
いや、 Welch という名前が入ってない論文でも、読む価値のある論文は存在しないこともないのですが、何がマトモな論文かどうか判断できない場合、 Welch という名前が入っていない論文は読まないことをオススメします。
[2022/06/14追記] 最近は、わりと Welch 以外の論文でも、優れた無限次元チューリングマシンの論文が増えてきたので訂正しておきます。
ただ、どれを読むか迷ったら、とりあえず Welch の名前が入った文献を読むことをオススメします。
地雷が多いといったのは、英語版巨大数wikiでもそうなのですが、「超限回の停止問題の累積は複雑で扱いにくいから計算可能概念の他の拡張を考えたのだろう」という程度の理解で無限時間チューリングマシンに関する文章を書く人がいるからですね。無限時間チューリングマシンの計算能力が射影不能順序数を越えているくらいのことについては触れてほしい……ほしい……。また、
無限時間ビジービ…どの文献とは言いませんが、「
Σ11 または
Π11 （ハイパージャンプ）という極小レベル」と「
Δ12 という決して到達できない壁（安定順序数レベル）」の中間部に一切触れていない文献、つまり、無限時間チューリングマシンの本質はその中間部なのに、
Π11 からいきなり
Δ12 の話に行くようなやつは完全に地雷なのでスルーした方がいいと思います。
ただ、 Welch もそうなのですが、無限時間勢がたまに主張する、「いわゆる一般再帰理論は、（抽象数学的な定式化を行っているため）計算モデルを与えているわけではない。近年の無限時間計算論は、具体的に計算モデルを与えているという点で新しい」みたいな感じの主張はどうかと思うんですよね。
たしかに一般再帰理論の記述は、「計算モデル」的ではないことが多いです。これは、一般再帰理論の主要な発展が1960年〜70年代頃におけるもので、未発達だった計算機科学的記述よりも厳密な数学的記述を好んだ、という類の時代背景があったのではないかと思うのですが、いかがでしょうか。実際には、「計算モデル」的なアイデアを持って進められていたと思うんですけどね。Hinmanの本の記述とかも、その背後にある計算モデル的アイデアはとてつもなく明瞭なので、わたしは一般再帰理論の結果を、完全に計算モデル的に理解していました。
なので、「一般再帰理論は、計算モデルを与えていない」とか主張されるのを見ると、首を傾げてしまいます。無限時間勢による一般再帰理論へのこの手の見縊りが、一般再帰理論をよく知る人々から煙たがられている要因だと思うんですけどね。
という無限時間の専門家に対する愚痴はさておき、そろそろ締めに入りましょう。
「計算不可能って、なんかずるい」そういう印象を受ける人もいるようです。その印象の、ひとつ先のレイヤーに、今回の話はあるかもしれません。「超越的な何かによって、巨大な無限がぽっと与えられるのは、なんかずるい」だから、超越的な概念を排除して、構成的に、下から徐々に、無限を理解していこう。そういう思いが、60〜80年代の一般再帰理論における計算不可能性の探求の源泉だったのかもしれません。
そうやって、ひとびとは、混沌とした無限の世界に、秩序をもたらしてきたのでした。
0 件のコメント:
コメントを投稿