日記 (2025 年 12 月 22 日)

ふと思い立って計算可能性理論の基礎を勉強し始めたので、 ここに勉強ノートとしてまとめていこうと思う。 基本的に Enderton†1 を参考にする。

古くから数学者たちは数多くの命題を証明してきたが、 それらはすべて人間の思考と直感による営みであった。 そんな中 1928 年、 David Hilbert と Wilhelm Ackermann は、 「数学的命題の真偽を機械的な手順によって自動的に判定することは可能か」 という問いを投げかけた。 しかし、 この問いに答えるには、 そもそも 「機械的に計算できる」 とは数学的に何を意味するのかを厳密に定義する必要があった。 こうして、 「計算」 の定義を巡る数学者たちの考察が始まった。

最初に Kurt Gödel は、 方程式系に基づいて式を変形することで値が導かれる 「一般再帰関数」 と呼ばれる関数のクラスを定義した。 このような関数は単純な操作の繰り返しでその値を求めることができるため、 これを 「計算できる」 関数と見なすのは自然だと考えられた。 しかし、 当時の Gödel 自身は、 直感的に 「計算できる」 と思える関数がこれで全て網羅できているかという点については懐疑的だったようである。 続いて Alonzo Church は、 計算を関数の適用と抽象化のプロセスと捉え、 「ラムダ計算」 という体系を構築した。 しかし、 この体系は抽象的であるため、 果たして現実の 「計算」 と同一視しても良いのか疑問視され、 周囲からの納得を得るには至らなかった。 一方で Alan Turing や Emil Post はそれぞれ独立に、 計算をテープ上の文字列の読み書きとして定式化し、 仮想的ではあるがより具体的な計算機を構築した。 これは後に 「Turing 機械」 と呼ばれる。

こうして、 再帰関数, ラムダ計算, Turing 機械という、 全く異なるアプローチをとった 3 つの 「計算」 の定義が現れた。 しかし驚くべきことに、 Stephen Kleene 等による解析の結果、 これら 3 つの定義は全く同じ関数のクラスを定めていることが明らかになった。 どのアプローチをとっても同じ結論に達したというこの事実は、 「計算」 という概念の正当性を裏付けるものであった。 このようにして、 「計算」 とは何なのかを巡る論争には終止符が打たれた。

歴史についてはこの辺りにして本題に移ろう。 まず、 計算できるかどうかを判定する対象としては、 自然数から自然数への多価関数 f:󱀍k󰔇→󱀍 を考えることにする。 というのも、 (これは後々しっかり議論することになるが) だいたいのデータは自然数に変換することができるため、 自然数上の関数を考えれば十分であるからである。 さらに、 計算というのは終わらない可能性がある。 そのため、 値が必ずしも定まるとは限らない関数を考えたい。 そこで、 これを次のように定式化する。

今後は、 基本的に部分関数を扱っていくことになる。 そのため、 全ての値が定義されるような関数の方を特殊扱いしたいため、 これに専用の名前をつけておく。

すなわち、 全域関数 f:󱀍k󰔇→󱀍 とは、 普通の意味での関数 f:󱀍k→󱀍 のことである。

さて、 今後の議論のためにいくつかの記法や用語を用意しておこう。 まず、 我々は自然数から自然数への多価 (部分) 関数を扱うため、 󱀍k の元を考えることが多い。 この元は k 個の自然数の組 (x0,⋯,xk−1) であるが、 これをまとめて 󰕷x のように書くことにする。 逆に、 󰕷x∈󱀍k を構成する各自然数のことは x0,⋯,xk−1 のように添え字を付けて表すが、 このときは原則として添字を 0 から始めることにする。

加えて、 部分関数を扱う上での便利な用語も用意しておく。

定義されないことを表す ↑ という記号は、 部分関数を定めるときにも利用することがある。 例えば、 f: 󱀍2 󰔇⟶ 󱀍 (x,y) ⟼ { x−y (x≥y) ↑ (x<y) と書いたら、 f は定義域を {(x,y)∣x≥y}⊆󱀍2 とする部分関数である。

部分関数の値を比較することは頻繁にあるが、 部分関数の値は定義されないことがあるので少し注意が必要である。 以降、 特に指示がない場合、 f(󰕷x)=g(󰕷y) という形の等式が成立するとは、 両辺 f(󰕷x), g(󰕷y) が両方定義されていて等しいか両方とも定義されていないかのいずれかであるときとする。 したがって、 両辺を定める部分関数の定義域がズレていたら等式は成立していないことになる。

また、 部分関数の値を組み合わせることもよくあるが、 特に指示がなければ、 式の一部が定義されない場合は式全体が定義されないこととする。 例えば、 f: 󱀍2 󰔇⟶ 󱀍 (x,y) ⟼ { x−y (x≥y) ↑ (x<y) g: 󱀍 󰔇⟶ 󱀍 x ⟼ { x/2 (x は偶数) ↑ (x は奇数) と定義した場合、 x∈󱀍 に対して f(g(x),3) という式は、 x が奇数であれば g(x) が定義されないので全体も定義されず、 さらに x が偶数であっても g(x) が 3 未満であれば定義されない。 したがって、 h: 󱀍 󰔇⟶ 󱀍 x ⟼ f(g(x),3) と定めると、 この式の字面だけを見れば全域関数に見えるが、 実際にはその定義域は {x∣x は偶数かつ x/2≥3}⊂󱀍 である。

準備は以上にしよう。 次回からは、 再帰関数の理論を展開していく。

参考文献

1. H. B. Enderton (2011) 『Computability Theory』 Academic Press