Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

要旨

「計算できる」という語には、二つの身分の違う主張がぶら下がっている。本稿が問うのは、そのどちらが証明されたのかである。答は、片方だけである。三つの形式的定義が同じクラスを指すことは定理であり、そのクラスが「計算できるもの全部」だというテーゼは定理ではない。新しい数学定理も新しい法則も主張しない。

第一に、出発点を数える。$1934$–$1936$ 年に、動く機械・式の書き換え・再帰という三つの無関係な出発点が置かれた。三つの間の対の同値性は $\mathbf{3}$ 本である（第2節）。

第二に、これが本稿の芯である。その $3$ 本はすべて証明されている。形式的定義どうしの比較なので、証明の対象になる（第3節）。

第三に、テーゼのほうは対象にならない。片側が非形式的な「計算できる」である以上、等式として書けない。証明できないのではなく、証明という手続きの外にある（第4節）。

第四に、それでも反証可能ではある。誰もが計算だと認める手続きで、このクラスの外の関数を一つ出せば倒れる。$90$ 年出ていないが、出ない保証は無い（第5節）。

第五に、クラスの内側にも階層がある。アッカーマン関数は原始帰納的でないのに計算可能で、$A(4,2)=2^{65536}-3$ は$\mathbf{19729}$ 桁である（第6節）。

第六に、その階層は数で見える。$A(4,0)=13$ から $A(4,1)=65533$ へ $\mathbf{5041}$ 倍、そこから $A(4,2)$ へは桁数が $5$ から $19729$ へ跳ぶ（第6節）。

射程（何を示さないか）

新しい数学定理も新しい法則も主張しない。チューリング機械、$\lambda$ 計算、一般帰納的関数、それらの同値性、チャーチ＝チューリングのテーゼ、アッカーマン関数が原始帰納的でないことは、いずれも標準的である。計算可能性理論を作らない。使うのは一つの再帰的定義と、対の数え上げと、桁数だけである。同値性を証明しない。三本の同値性の証明は本稿では行わない。証明されているという事実と、それが証明の対象になりうる理由だけを書く。テーゼの真偽を判定しない。正しいとも誤りとも言わない。身分が定理ではないと言うだけである。停止問題を扱わない。論文179 が停止問題に触れている。本稿は「計算できない対象」ではなく「計算できるという語の身分」を扱う。計算量に入らない。論文04 は $\mathrm{P}$ 対 $\mathrm{NP}$ を扱う。複雑性と計算可能性は別の階層であり、本稿は後者だけを見る。アッカーマン関数を完全に評価しない。$A(4,2)$ 以降は桁数の式で書くだけであり、値を書き下さない。$A(4,3)$ 以降は本稿の道具では扱わない。定義の一覧を網羅しない。第2節に挙げるのは一部であり、同じクラスに至る定式化は他にもある。年号は初出の年であり、同値性の証明年とは別である。既刊との関係：論文163 は「良い符号が在る」と「これが良い符号だ」が別の文であることを示した。本稿も二つの文の身分の差を扱うが、あちらは存在と構成、こちらは定理とテーゼである。論文189 は「証明できない」が文の性質ではなく公理系との関係だと示した。本稿の第4節はそもそも文になっていない主張を扱う。関係の外側である。論文179 は「構成できない」に別根があることを示した。本稿は「計算できる」の示し方が三つあることを数える。論文232 は同じ等号が四つの別の主張を書いていることを数えた。本稿はテーゼの「＝」が、そもそも等号ではないことを書く。論文190 は「稀」を対数の目盛りで測った。本稿の第6節も桁数で書く。加えたのは三つの定義と三本の同値性を数えて並べたこと、定理とテーゼの分かれ目を「両側が形式的かどうか」の一点に置いたこと、テーゼが証明不能でありながら反証可能であると書いたこと、アッカーマン関数の値を実際に計算し、$A(4,2)$ の桁数 $19729$ を出したことである。

1. 記法と位置づけ

設定：「この関数は計算できる」という文を二つに分ける。

（A）形式的な主張：三つの形式的定義（機械・書き換え・再帰）が、同じ関数のクラスを指す。

（B）非形式的な主張：そのクラスが、人が「計算できる」と呼ぶもの全部である。

問い：（A）と（B）は、同じ身分の主張か。

答は、違う。（A）は定理であり証明されている。（B）はテーゼであり、証明の対象になりえない。

注意：本稿は（B）が誤りだとは言わない。身分が定理ではないと言うだけである。正しさと、証明できるかどうかは、別の問いである。

2. 出発点を数える

検算 2.1：三つの出発点を並べる。年は初出のものであり、同値性が示された年とは別である。

観察 2.2　三つは互いに似ていない。一つは数の上の再帰、一つは記号列の書き換え、一つは物理的な装置の理想化である。同じものが出てくる理由は、定義からは見えない。

検算 2.3：三つの定義のあいだの、対の同値性の本数を数える。

観察 2.4　$3$ つの定義から作れる対は $\binom{3}{2}=3$ 本であり、その全部が証明されている。後年これに register 機械や型 $0$ 文法などが加わったが、どれも同じクラスに落ちた。第2節に挙げたのは一部である。

3. 芯：同値性は定理である

観察 3.1　なぜ証明できるのか。両側が形式的だからである。「チューリング機械で計算できる関数の集合」も「$\lambda$ 項で表せる関数の集合」も、定義が書き下されている。だから包含を両向きに示せばよい。

観察 3.2　証明の形も具体的である。一方の対象を他方で模倣する手続きを作ればよい。$\lambda$ 項をテープ上に符号化して簡約を機械に実行させる、といった構成である。

観察 3.3　この $3$ 本が本稿の「定理」の側である。ここまでは、通常の数学と同じ意味で確定している。

4. テーゼは定理ではない

観察 4.1　チャーチ＝チューリングのテーゼは、こう言う。「このクラスが、直観的に計算できる関数の全部である」。右辺の「直観的に計算できる」は、定義が書き下されていない。

検算 4.2：二つの主張を、身分で並べる。

観察 4.3　分離子、何を動かすと別物になるか。右辺が形式的かどうか、その一点だけである。左辺は両方とも同じものである。

観察 4.4　「まだ証明されていない」ではない。非形式的な概念との一致は、証明という手続きの入力になりえない。論文232 が同じ等号の四つの身分を数えたのと同じ話で、テーゼの「＝」はそもそも等号ではない。

観察 4.5　混同すると何が起きるか。「計算可能性は証明された」と書いてしまう。証明されたのは $3$ 本の同値性だけであり、テーゼは証明されていない。

5. だが反証可能ではある

観察 5.1　証明できないことと、反証できないことは別である。テーゼを倒すには、誰もが計算だと認める手続きで、このクラスの外の関数を一つ出せばよい。

検算 5.2：何が出れば倒れるかを並べる。

観察 5.3　四行のうち、倒すのは一行目だけである。停止問題のように「クラスの外にある関数」は既に知られているが、それは計算できないほうの証拠であってテーゼの反証ではない。

観察 5.4　$90$ 年、一行目は出ていない。だがそれは証拠であって証明ではない。反証可能な主張が長く反証されずにいるとき、それは強い経験的支持であり、定理ではない。

6. クラスの内側にも階層がある

設定：「計算できる」の中は一様ではない。アッカーマン関数は、原始帰納的でないのに計算可能である。階層が実在することの具体例である。

検算 6.1：定義どおりに評価する。

観察 6.2　$A(3,n)=2^{n+3}-3$ である。$5,13,29,61,125,253,\dots$ と、表の四行目がこの式にそのまま乗っている。

検算 6.3：$m=4$ の行に進む。

観察 6.4　$13$ から $65533$ へは $\mathbf{5041}$ 倍である。そこから次へは、値の比ではなく桁数が $5$ から $19729$ へ跳ぶ、倍率で書くことに意味が無くなる。

観察 6.5　この関数はどの原始帰納的関数よりも速く増えるので、原始帰納的ではない。それでも上の表のとおり実際に計算できている。「計算できる」の内側が一層でないことの、動く証拠である。

観察 6.6　正直に書くべき点、$A(4,2)$ の値そのものは本稿で書き下していない。桁数の式で書いただけであり、$A(4,3)$ 以降は本稿の道具では扱えない。

7. 点呼と結び

1. 出発点は三つ（検算2.1）：$1934$ の再帰、$1936$ の書き換え、$1936$ の機械。
2. 三つは似ていない（観察2.2）：同じものが出る理由は定義から見えない。
3. 同値性は $3$ 本（検算2.3）：$\binom{3}{2}=3$、その全部が証明されている。
4. 証明できる理由（観察3.1）：両側が形式的だから。
5. テーゼの右辺は非形式的（検算4.2）：だから定理ではない。
6. 分離子は一点（観察4.3）：右辺が形式的かどうか。
7. 反証はできる（検算5.2）：四行のうち倒すのは一行目だけ。
8. $90$ 年出ていない（観察5.4）：証拠であって証明ではない。
9. $A(3,n)=2^{n+3}-3$（観察6.2）：$5,13,29,61,125$。
10. $A(4,2)$ は $19729$ 桁（検算6.3）：原始帰納的でないのに計算可能。

結び：$1936$ 年に起きたことは、二つあった。一つは、三つの無関係な出発点が同じクラスに着いたという定理である。対の同値性 $3$ 本は、通常の数学と同じ意味で確定している。もう一つは、そのクラスが「計算できるもの全部」だというテーゼである。こちらは右辺が非形式的なので、証明という手続きの外にある。混同すると「計算可能性は証明された」と書いてしまう。そしてテーゼは、証明できないが反証はできる。$90$ 年反証されていないのは強い証拠であって、定理ではない。分けるものは一つ、両側が形式的かどうかを書き出すこと。書き出せば、確定している部分と、支持されているだけの部分が分かれる。書き出さなければ、$3$ 本の定理の信用が、テーゼの側へ黙って流れ込む。

参考文献

1. Turing, A. M. (1936). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, s2-42.
2. Church, A. (1936). An Unsolvable Problem of Elementary Number Theory. American Journal of Mathematics, 58(2).
3. Kleene, S. C. (1936). General Recursive Functions of Natural Numbers. Mathematische Annalen, 112.
4. Turing, A. M. (1937). Computability and $\lambda$-Definability. The Journal of Symbolic Logic, 2(4).
5. Ackermann, W. (1928). Zum Hilbertschen Aufbau der reellen Zahlen. Mathematische Annalen, 99.
6. Soare, R. I. (2016). Turing Computability: Theory and Applications. Berlin: Springer.
7. Odifreddi, P. (1989). Classical Recursion Theory. Amsterdam: North-Holland.
8. 山岸勇輝 (2026). 総当たり探索の物理的資源限界 [論文04]. Zenodo. 10.5281/zenodo.21404131
9. 山岸勇輝 (2026). 「良い符号が在る」と「これが良い符号だ」は、別の文である [論文163]. Zenodo. 10.5281/zenodo.22092677
10. 山岸勇輝 (2026). 「構成できない」にも別根がある [論文179]. Zenodo. 10.5281/zenodo.22098419
11. 山岸勇輝 (2026). 「証明できない」は、文の性質ではない [論文189]. Zenodo. 10.5281/zenodo.22105830
12. 山岸勇輝 (2026). 「稀」は、対数の目盛りで測る [論文190]. Zenodo. 10.5281/zenodo.22106182
13. 山岸勇輝 (2026). 証明を落とした本から学ぶと、等号の身分も一緒に落ちる [論文232]. Zenodo. 10.5281/zenodo.22127528

作成にあたって：本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI（大規模言語モデル）の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。

書誌

山岸勇輝（2026）「同値性は定理であり、テーゼは定理ではない」［論文260］. Zenodo.
DOI: 10.5281/zenodo.22169292

@misc{yamagishi2026yoi260,
  author = {Yamagishi, Yuuki},
  title = {The Equivalence Is a Theorem and the Thesis Is Not},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/260},
  doi = {10.5281/zenodo.22169292},
  note = {Preprint, edition 1}
}