TR関数

超越整数の拡張関数は巨大数研究 Wikiユーザー ふぃっしゅが作った計算可能巨大関数の族であり、\(\textrm{TR}\) と表記する。 これは超越整数の定義から自然に生じる計算可能関数の拡張である。

定義

\(T\) を算術の固定された埋め込みを持つ形式理論、および \(n\) を自然数とする。このとき \(\textrm{TR}(T,n)\) は以下のような最小の自然数 \(N\) として定義される: 任意のチューリング機械 \(M\) について、\(M\) の停止を \(T\) において \(n\) 記号以内で証明可能ならば、\(M\) は実際に \(N\) ステップ以内に停止する。

解説

\(\textrm{ZFC}\) 集合論のようなベース理論で作業し、\(T\) をベース理論内で符号化された形式理論と考える。ベース理論のチューリング機械 \(M\) ごとに、\(M\) を算術で符号化する既知の方法が存在するので、 \(T\) にも存在する。したがって \(M\) の \(T\) における停止は自然に意味をなす。この方法で、\(\textrm{TR}\) 関数は算術の固定された埋め込みを持つ形式理論 \(T\) ごとに \(n\) の部分関数を生成する。特に \(T\) が再帰的理論である時、その部分関数は計算可能である。

この関数 \(\textrm{TR}\) 自体は全域的ではない。なぜならば矛盾した形式理論が存在するからである。たとえば、ベース理論は無矛盾で、\(T\) は\(\textrm{PA}\)に反証可能な論理式 \(0 = S0\) を加えた理論で、\(M\) は停止しないと仮定する。爆発律により、\(M\) の停止は \(T\) で証明可能である。\(n\) が \(M\) の停止の \(T\) における最短の証明の記号数以上ならば、\(M\) が \(N\) ステップ以内に停止するような自然数 \(N\) は存在しない。なぜならば \(M\) は停止しないからである。したがってこの場合 \(\textrm{TR}(T,n)\) はill-definedである。

以下、定数記号も関数記号も関係記号も有限個しか持たないような \(T\) に絞って考え、\(T\) の変数記号を \(x_0, x_1, \ldots\) と番号付ける。任意の \(n\) に対し \(T\) での \(n\) 記号以下の証明全体の集合を \(P_n\) と置く。変数の置き換えは \(P_n\) の同値関係 \(\sim_n\) を定め、添字が \(n\) 未満の変数記号しか現れない証明全体のなす部分集合を \(P'_n \subset P_n\) と置くと \(P_n\) に属する任意の証明は \(P'_n\) に属するある証明と \(\sim_n\) に関して同値である。定数記号と関数記号と関係記号の有限性の仮定より\(P'_n\) は有限集合であることと合わせ、\(T\) において \(n\) 記号以下で停止性が証明可能なチューリング機械 \(M\) は有限個しか存在しない。これにより、\(T\) において \(n\) 記号以下で停止性が証明可能なチューリング機械 \(M\) がもし必ず停止するならば、それらの停止ステップ数全体の集合は有限集合となるため確かに上限 \(N\) を持ち、\(\textrm{TR}(T,n)\) が定義される。ここで「\(T\) において \(n\) 記号以下で停止性が証明可能なチューリング機械 \(M\) がもし必ず停止する」という仮定を置いたがこれは必ずしも成り立たないことに注意する。

たとえベース理論で \(\textrm{Con}(T)\) が成り立つという意味で \(T\) が無矛盾だったとしても、停止しないチューリング機械の停止が \(T\) において証明されるかもしれない。たとえば、ベース理論が \(\textrm{ZFC}\) で \(T\) が \(\textrm{PA} + \neg \textrm{Con}(\textrm{PA})\) ならば、\(T\) は無矛盾だが \(\textrm{TR}(T,n)\) は十分に大きな \(n \in \mathbb{N}\) に対して ill-defined である。なぜならばあるチューリング機械が存在し、その停止は \(\neg \textrm{Con}(\textrm{PA})\) と同値であり、\(\neg \textrm{Con}(\textrm{PA})\) は \(T\) で証明可能だがベース理論で反証可能だからである。

任意の \(n\) に対する \(\textrm{TR}(T,n)\) のwell-defined性を保証するには、\(T\) のベース理論における \(\Sigma_1\)-健全性と呼ばれる強い仮定が必要である。実際にこの仮定の下で \(\textrm{TR}(T,n)\) がwell-defined性であることはp進大好きbotが証明した。\(\textrm{TR}(T,n)\) を特定の \(n\)、たとえば \(2^{1000}\) に対して定義したいだけならば、より弱い以下の仮定だけで十分である: 任意のチューリング機械 \(M\) について、\(M\) の停止が \(T\) において \(n\) 記号以内で証明可能ならば、\(M\) は実際に停止する。

たとえば、\(T\) が \(\textrm{ZFC}\) 集合論ならば、\(\textrm{TR}(T,n)\) はベース理論における \(\textrm{ZFC}\) 集合論の \(\Sigma_1\)-健全性の仮定のもとで全域であり、\(\textrm{TR}(T,2^{1000})\) は最小の超越整数と一致する。これが \(\textrm{TR}\) を超越整数の拡張関数と呼ぶ理由である。

特殊化

ふぃっしゅは\(\textrm{I}0\) 関数と呼ばれる特定の関数を \(\textrm{TR}(\textrm{ZFC}+\textrm{I}0,n)\) として作った。ここで、\(\textrm{I}0\) は非常に強い巨大基数公理である階層内階層基数の存在公理を表す。Friedmanは特定の超越整数を作っていないので、ふぃっしゅも \(\textrm{I}0\) 関数の値を作っていない。

解析

定義により、\(\textrm{TR}(T,n)\) は \(T\) で可証全域ないかなる計算可能関数よりも速く増加する。これは、もし与えられた計算可能全域関数が「全域であると知られている」ならば、ある特定の \(T\) の選択に対して \(\textrm{TR}(T,n)\) によって抑えられることを含意する。たとえば、ほとんどすべての既知の全域計算可能関数は \(\textrm{I}0\) 関数によって抑えられる。

これが超越整数の概念の素朴な拡張であるかどうかには議論の余地があるが、ふぃっしゅが指摘したように強い理論がさらに強い理論において直接より大きな数をもたらすことの明示的な説明を与えていることは重要である。したがって \(\textrm{ZFC}\) 集合論より強い理論で作業するならばベース理論を固定して明示しておくのが合理的である。さもなければ、任意の全域計算可能関数は上記の意味で \(\textrm{TR}\) 関数よりも弱くなってしまう。

特定の \(T\) を伴う \(\textrm{TR}(T,n)\) 関数のようなものは、急増加関数において \(\textrm{PTO}(T)\)、すなわち \(T\) の証明論的順序数に「近似」されることがあるが、この「近似」には意味がない。なぜならば急増加関数は順序数に対してではなく、順序数と基本列系の組に対して well-defined だからである。より小さな順序数と異なり、\(\textrm{PTO}(T)\) は固定された基本列系を持たないので、比較に意味はない。急増加関数は基本列系の選択に強く依存するので、基本列系を固定することができたとしても、比較は極めて疑わしい。

参照

日本の巨大数論

Aeton: おこじょ数・N成長階層
mrna: 段階配列表記・降下段階配列表記・多変数段階配列表記・横ネスト段階配列表記
Kanrokoti: くまくまψ関数・亜原始ψ関数・ハイパー原始ψ関数・TSS-ψ関数
クロちゃん: クロちゃん数（第一・第ニ・第三・第四）
じぇいそん: ふにゃふにゃぜぇたかんすう・\(\zeta\)関数
たろう: 多変数アッカーマン関数・2重リストアッカーマン関数・多重リストアッカーマン関数
Nayuta Ito: フラン数（第一形態・第二形態・第四形態改三）・N原始・東方巨大数4の規則の境界を突いた巨大数
バシク: 原始数列数・大数列数・ペア数列数・バシク行列システム
長谷川由紀路: 紅魔館のメイドナンバー・恋符マスタースパーク数・みくみく順序数
108Hassium: E2:B-01-Hs・L-階差数列類・E3:B-02-Hs
公太郎: 弱亜ペア数列・肉ヒドラ数列・弱ハイパーペア数列
p進大好きbot: 超限急増加関数表記・拡張ブーフホルツのψ関数に伴う順序数表記・四関数・三関数・巨大数庭園数
ふぃっしゅ: ふぃっしゅ数（バージョン1・バージョン2・バージョン3・バージョン4・バージョン5・バージョン6・バージョン7）・ マシモ関数・マシモスケール・TR関数（I0関数）
ゆきと: 亜原始数列･ハイパー原始数列・Y数列
本: 巨大数論・寿司虚空編
大会: 東方巨大数・幻想巨大数・即席巨大数・式神巨大数・お料理巨大数
掲示板: 巨大数探索スレッド
外部リンク: 日本語の巨大数関連サイト