第3部：論理学と計算機科学における「部分（Undefined）」

——計算可能性の限界と未定義の深淵

第5章：部分写像と計算可能性 —— 「答えがない」という答え

5.1 写像の概念拡張：TotalからPartialへ

私たちは数学を学び始めたその日から、「関数（Function）」とは自動販売機のようなものだと教えられてきた。コイン（入力）を入れれば、必ずジュース（出力）が出てくる。$y=x^2$ にどんな実数 $x$ を放り込んでも、必ず二乗された値が返ってくる。 このように、定義域（Domain）の「全ての」要素に対して値が一つ定まる写像を、**全域写像（Total Function）**と呼ぶ。これが数学の、そして古典物理学の常識であった。

しかし、20世紀に産声を上げた計算機科学（Computer Science）の現場において、この常識は早々に崩れ去った。 プログラマであれば誰でも経験することだが、書かれたプログラム（関数）は、必ずしも期待された値を返すとは限らない。

• エラーでクラッシュする（例外発生）。
• いつまで経っても処理が終わらない（無限ループ）。
• 想定外の入力に対して沈黙する。 これらは日常茶飯事だ。自動販売機にお金を入れても、何も出てこないし、お釣りも返ってこないことがあるのだ。

この現象を「バグ」や「失敗」として切り捨てることは簡単だ。しかし、計算機科学の父たちは、これを「数学的な構造の一部」として受け入れる道を選んだ。 すなわち、**部分写像（Partial Function）**の導入である。 部分写像 $f:A\to B$ とは、定義域 $Dom(f)$ が始域 $A$ の「部分集合（Subset）」でしかない写像のことだ。 $Dom(f)\subseteq A$ ある入力 $x\in A$ に対して、$x\in Dom(f)$ ならば値 $f(x)$ は存在する（定義される、収束する）。これを $f(x)\downarrow$ と書く。 逆に、$x\notin Dom(f)$ ならば値は存在しない（未定義、発散する）。これを $f(x)\uparrow$ と書く。

最も身近な例は、有理数体における逆数関数 $f(x)=1/x$ である。 $x=0$ のとき、この関数は値を返さない。「ゼロ除算」は禁止されているからだ。 古典的な数学では「定義域を $x\ne 0$ に制限せよ」と教える。つまり、最初から危険な入力を排除し、無理やり全域写像に仕立て上げるのだ。 しかし計算機科学では、より包括的な視点を持つ。「$0$ を入力してもよい。ただし、結果は『未定義』になる」と考えるのである。 このパラダイムシフト——「定義されない」という状態を積極的に認めること——が、計算という行為の本質を解き明かす鍵となる。

5.2 アルゴリズムとは部分関数である

なぜ我々は「Partial」を受け入れなければならないのか？ それは、アルゴリズム（計算手順）の構造そのものが、本質的に部分性を孕んでいるからである。

アラン・チューリングが考案した抽象的な計算モデル、チューリングマシンを考えてみよう。 マシンはテープの上を動き回り、記号を読み書きし、内部状態を変える。計算が「終わる」とは、マシンが特定の「停止状態（Halting state）」に到達することを指す。停止して初めて、テープに残された記号列が「出力」として確定する。 しかし、マシンが停止するという保証はどこにもない。 単純な例として、「テープが空でなければ右に移動し続ける」という命令を与えられたマシンは、永遠に右へ走り続ける。このとき、出力は永遠に確定しない。 つまり、チューリングマシンが定義する関数は、入力によっては値を返さない。それは必然的に**部分関数（Partial Function）**とならざるを得ないのだ。

計算論の歴史において、この事実は**「帰納的関数論（Recursive Function Theory）」の中で厳密化された。 初期の試みである「原始帰納的関数（Primitive Recursive Function）」は、forループ（回数の決まった繰り返し）のみを許容する体系で、これは必ず停止する（Total Function）。しかし、これではアッカーマン関数のような急激に増大する関数を計算できないことが判明した。 より強力な計算能力を得るためには、whileループ（条件が満たされるまで繰り返す）に相当する操作、すなわち「最小化操作（$\mu$-operator）」**を導入する必要があった。 「$f(x,y)=0$ となる最小の $y$ を探せ」 この命令は強力だ。しかし同時に危険でもある。もしそのような $y$ が存在しなかったら？ 探索は永遠に終わらない（無限ループ）。

チャーチ＝チューリングのテーゼは、「計算可能な関数」を「（一般）帰納的関数」と定義した。そして一般帰納的関数とは、本質的に部分関数なのである。 我々が手にした「万能計算（Universal Computation）」という神の力は、「計算が終わらないかもしれない（Partialである）」というリスクを受け入れた代償として得られたものなのだ。全域性（Totality）と万能性（Universality）は、トレードオフの関係にあると言っても過言ではない。

5.3 未定義値（Bottom, $\perp$）の導入

「値がない」という状態を数学的に扱うのは厄介だ。「$f(x)$ は存在しない」という文は、数式の中で使いづらい。 そこで編み出されたのが、「値がない」ことを表す「値」を発明するというトリックである。 この特別な値を**ボトム（Bottom）**と呼び、記号 $\perp$ で表す。

集合 $D$（例えば整数 $\mathbb{Z}$）に $\perp$ を加えた拡張集合 $D_{\perp }=D\cup \{\perp \}$ を考える。 そして、部分写像 $f:D\to D$ を、拡張された全域写像 $f^{\prime }:D\to D_{\perp }$ と見なすのである。

• 元々値があった場所では、$f^{\prime }(x)=f(x)$。
• 元々未定義だった場所では、$f^{\prime }(x)=\perp$。

これにより、形式上は全ての入力に対して「何か（値か、あるいは $\perp$ か）」が返ってくることになり、数学的な操作（合成など）が格段にスムーズになる。これは位相空間論における「一点コンパクト化（無限遠点の導入）」と全く同じ精神的所産である。

プログラミング言語理論において、この $\perp$ の扱いは**「評価戦略」**の違いとして現れる。

• 厳格評価（Strict Evaluation）： 引数の一部でも $\perp$（エラーや無限ループ）であれば、関数全体の結果も $\perp$ になる。$f(\perp )=\perp$。C言語やJavaなど、多くの言語はこれを採用している。「毒が入っていたら料理全体が毒になる」という論理だ。
• 非厳格評価 / 遅延評価（Non-strict / Lazy Evaluation）： 引数が $\perp$ であっても、結果が返ることがある。例えば定数関数 $f(x)=1$ ならば、$f(\perp )=1$ となる。Haskellなどの関数型言語が採用する。「毒が入っていても、食べなければ死なない」という論理だ。

遅延評価の世界では、無限リスト（終わりのないデータ列）を扱うことができる。全体は $\perp$（終わらない）を含んでいても、必要な「部分（Head）」だけを取り出して計算を進めることができる。ここでも「Partial」な情報の有効活用が、計算の可能性を広げている。

---

第6章：停止性問題とドメイン理論 —— 無限の情報と有限の近似

6.1 停止性問題と対角線論法 —— 知り得ない領域

計算機科学における最大の未解決問題、あるいは「解決不可能であることが解決された問題」。それが**停止性問題（Halting Problem）**である。 問いはシンプルだ。 「あるプログラム $P$ と入力 $x$ が与えられたとき、$P(x)$ が有限時間で停止するかどうかを判定する万能プログラム $H(P,x)$ は存在するか？」

アラン・チューリングが出した答えは、衝撃的な “No” であった。 証明にはカントールの対角線論法が用いられる。 もし $H$ が存在すると仮定しよう。すると、次のような意地悪なプログラム $D(P)$ を作ることができる。

• $H(P,P)$ が「停止する」と判定したら、$D$ はわざと無限ループする。
• $H(P,P)$ が「停止しない」と判定したら、$D$ はすぐに停止する。 さて、このプログラム $D$ に自分自身 $D$ を入力したらどうなるか？
• 停止するなら無限ループし、無限ループするなら停止する。 これは矛盾である。したがって、仮定した $H$ は存在しない。

この証明の核心は、関数表の対角線を反転させて「定義域から外れる」点を作ることにある。 $H$ は「Total（全てのプログラムに対して判定を下す）」であることを求められた。しかし、自己言及という悪魔の回路を通すことで、論理の網の目は破られ、「判定不能」という穴（Partiality）がどうしても空いてしまうのだ。

これはゲーデルの不完全性定理とも深く共鳴している。 数学的真理の集合（Total）に対して、公理系から証明可能な定理の集合（Partial）は、決して一致しない。「真だが証明できない」命題が存在するように、「停止するが、停止することを示せない」プログラムが存在する。 我々は、論理的宇宙において、原理的に「知り得ない領域（Undefined zone）」と共存しなければならない。

6.2 スコット領域（Domain Theory） —— 情報の順序構造

プログラム $f$ が再帰的に定義されているとき（例：階乗関数の定義）、それは数学的には「方程式」と見なせる。 $f=\Phi (f)$ $\Phi$ はプログラムのコードそのものが表す変換操作だ。この方程式を満たす $f$（不動点）を見つけることが、再帰プログラムの「意味」を確定することになる。 しかし、関数空間はあまりに複雑で、通常の方法では解の存在が保証できない。

1960年代末、デイナ・スコットはこの難問に対し、**ドメイン理論（Domain Theory）という革新的な枠組みを提示した。 彼は、「計算」というプロセスを「情報の順序関係（Information Order）」**として捉え直したのである。 記号 $⊑$ を用いて、「情報の多寡」を表す。

• $\perp$（情報なし） $⊑$ 部分的な出力 $⊑$ 完全な出力。 例えば、$\perp ⊑[1,2,\perp ]⊑[1,2,3]$ のように。

スコットの洞察はこうだ。計算とは、時間が経つにつれて情報が増えていく（順序を登っていく）単調なプロセスである。 そして、プログラムが記述する関数 $\Phi$ は、この順序を保存する**「連続関数（Continuous Function）」である。 トポロジー（位相幾何学）の定理によれば、ある種の条件を満たす空間（完備半順序集合、CPO）上の連続関数は、必ず最小不動点（Least Fixed Point）**を持つ。

$f={⨆}_{n=0}^{\infty }{\Phi }^n(\perp )$ この数式は美しい物語を語っている。 計算は、無知の状態（$\perp$）から始まる。プログラム（$\Phi$）を1回適用すると、少し情報が得られる（$\Phi (\perp )$）。もう1回適用すると、もう少し詳しくなる（$\Phi (\Phi (\perp ))$）。 これを無限に繰り返した極限（$⨆$）こそが、再帰プログラムの真の意味（不動点 $f$）である。 無限ループするプログラムの場合、この列はずっと $\perp$ のままであり、その極限も $\perp$ となる。つまり「意味は未定義」ということが、数学的に厳密に定義される。

6.3 連続性と近似可能性 —— 有限から無限へ

ドメイン理論における「連続性」という言葉は、解析学のそれと驚くほど似ているが、情報の文脈でより深い意味を持つ。 関数 $f$ が連続であるとは、「極限の計算」と「関数の適用」が交換可能であることを意味する。 $f(\lim x_n)=\lim f(x_n)$ これを計算機科学的に翻訳するとこうなる。 「無限のデータ（$\lim x_n$）に対する計算結果を知りたければ、その有限の近似（$x_n$）に対する計算結果を集めて、最後に極限を取ればよい」

これは**「有限近似可能性（Finite Approximation）」**の原理である。 コンピュータは有限のメモリと有限の時間しか持たない。したがって、真の「無限」を直接扱うことはできない。 円周率 $\pi$ を計算するとき、我々は $3.14,3.141,3.1415\dots$ という有限の近似値を扱う。計算が進めば進むほど、精度（情報量）は上がり、真の値（Total）に近づいていく。 ドメイン理論は、「計算可能な関数」とは、「有限の部分情報（Partial input）だけを見て、有限の部分出力（Partial output）を確定できるもの」に限られることを数学的に示した。 逆に言えば、「入力が無限に続くリストの『最後』を見ないと最初の1ビットも出力できない」ような関数は、計算不可能（不連続）なのである。

我々は常に「Partial」な世界に生きている。 しかし、そのPartialな断片を無限に積み重ねるシステムと理論（極限、不動点、完備化）を持つことで、我々は有限の身でありながら、無限の「Total」な真理に——近似的にではあるが——確実に触れることができるのである。

---

（第3部 完）