# 計算可能性：チューリング機械・再帰関数・停止問題とライスの定理
> チューリング機械と原始再帰・μ 再帰関数を定義して両者の等価性を示し、停止問題の決定不能性とライスの定理を、対角線論法と万能関数から証明する。「アルゴリズムで解ける」を数学の対象にする。
> https://rikai.mugen-giken.com/mathematics/logic-and-type-theory/computability
## 0. この記事の要点
プログラムを書くと、どんな入力でも必ず答えを返すものもあれば、入力によっては延々と動き続けるものもあります。「あるプログラムが、この入力でいつか止まるか」を、別のプログラムで必ず見抜くことはできるのでしょうか。この記事では、まず「計算できる」とは何かを数学の言葉で決め、そのうえで「見抜く手順は存在しない」ことを証明します。読み終えると、「解けない」ことを証明するとはどういうことか、その典型的な形が分かります。
- 「アルゴリズムで計算できる関数」を、**チューリング機械**で数学的に定義します。有限個の規則をもつ機械が、無限に延びるテープの上で記号 $0,1$（と作業用の目印 $2$）を読み書きする、という最小限のモデルです。
- 同じクラスの関数を、機械を使わない帰納的な定義でも与えられます。**原始再帰関数**（足し算から掛け算を作るように、一つ前の値から次の値を組み立てる繰り返しで定義される関数）に最小化演算 $\mu$（条件を満たす最小の数を探す操作）を加えたものが**部分再帰関数**です。両者が一致すること（
**決定問題と半決定問題**を定義します。集合 $A\subseteq\mathbb{N}$ が**決定可能**であるとは、特性関数 $\chi_A$（$A$ に属すれば $1$、属さなければ $0$）がチューリング計算可能な全関数であることをいいます。$A$ が**半決定可能**（計算可能枚挙可能）であるとは、$A$ がチューリング計算可能な部分関数の定義域であることをいいます。属するものにはいつか「はい」と答え、属さないものには永遠に答えない手順があること、と読めます。
## 3. 原始再帰関数
機械を使わずに、関数を帰納的に定義する方法を用意します。これは「$f(y+1)$ を $f(y)$ から計算する」という素朴な再帰を一般化したものです。
次の**基本関数**を考える。
- ゼロ関数 $Z(x)=0$。
- 後者関数 $S(x)=x+1$。
- 射影関数 $P^n_i(x_1,\ldots,x_n)=x_i$（$1\le i\le n$）。
**原始再帰関数**とは、基本関数から次の二つの操作を有限回繰り返して得られる関数である。
- **合成**：$g:\mathbb{N}^m\to\mathbb{N}$ と $h_1,\ldots,h_m:\mathbb{N}^n\to\mathbb{N}$ から、$f(\vec{x})=g(h_1(\vec{x}),\ldots,h_m(\vec{x}))$。
- **原始再帰**：$g:\mathbb{N}^n\to\mathbb{N}$ と $h:\mathbb{N}^{n+2}\to\mathbb{N}$ から、
$$
f(\vec{x},0)=g(\vec{x}),\qquad f(\vec{x},y+1)=h(\vec{x},y,f(\vec{x},y)).
$$
原始再帰関数はすべて全関数です（再帰の深さ $y$ に関する帰納法）。集合（[述語](/mathematics/foundations/sets-and-logic#def-predicate)）$P\subseteq\mathbb{N}^n$ が原始再帰的であるとは、その特性関数が原始再帰的であることをいいます。
次はいずれも原始再帰的である。
1. $x+y$、$x\cdot y$、$x^y$、$x!$、前者 $\mathrm{pd}(x)$（$\mathrm{pd}(0)=0$, $\mathrm{pd}(x+1)=x$）、切り捨て差 $x\dot-y=\max(x-y,0)$、符号 $\mathrm{sg}(x)$（$x=0$ なら $0$、それ以外 $1$）。
2. 原始再帰的な述語の否定・論理積・論理和。原始再帰的な関数による場合分け定義。
3. $f$ が原始再帰的ならば、有界和 $\sum_{i
(1) $x+0=x$, $x+(y+1)=S(x+y)$ から加法、$x\cdot0=0$, $x\cdot(y+1)=x\cdot y+x$ から乗法、以下同様に $x^y$, $x!$ を得る。$\mathrm{pd}$ は $\mathrm{pd}(0)=0$, $\mathrm{pd}(y+1)=y$ という原始再帰（$h(y,\cdot)=P^2_1$）。$x\dot-0=x$, $x\dot-(y+1)=\mathrm{pd}(x\dot-y)$。$\mathrm{sg}(0)=0$, $\mathrm{sg}(y+1)=1$。
(2) 述語の特性関数 $\chi_P,\chi_Q$ に対し、$\chi_{\neg P}=1\dot-\chi_P$, $\chi_{P\wedge Q}=\chi_P\cdot\chi_Q$, $\chi_{P\vee Q}=\mathrm{sg}(\chi_P+\chi_Q)$。場合分け $f=g_1$（$P$ のとき）、$g_2$（そうでないとき）は $\chi_P\cdot g_1+(1\dot-\chi_P)\cdot g_2$。
(3) $F(\vec{x},0)=0$, $F(\vec{x},y+1)=F(\vec{x},y)+f(\vec{x},y)$（積は初期値 $1$ と乗法）。
(4) $\exists ix]$（$y>0$）。$x\bmod y=x\dot-y\cdot\lfloor x/y\rfloor$。$y\mid x\iff x\bmod y=0\ (y>0)$。素数述語は「$x\ge2$ かつ $\forall dの議論）ので $p_i!+1$ の素因数のうち最小のものは $p_i$ より大きく、$p_i!+1$ 以下である。したがって $p_{i+1}=\mu k\le p_i!+1\,[k>p_i\wedge k\text{ は素数}]$ と有界最小化で書ける（$p_{i+1}$ は $p_i$ より大きい最小の素数）。最後に、$n>0$ のとき $(n)_i=\mu k
有界最小化の式 (4) は、小さな例で確かめると意味が見えます。$y=4$ で、$P(i)$ が $i=2$ で初めて成り立つとします（$\chi_P=(0,0,1,\ast)$。$\ast$ は何でもよい）。$j=0,1$ の項は $\prod_{i\le j}(1\dot-\chi_P(i))=1$、$j=2,3$ の項は $\chi_P(2)=1$ を含むので $0$ です。和は $1+1+0+0=2$ で、確かに最小の $i$ が出ます。
素因数分解の存在と一意性（