計算可能関数

同義語：computable function計算可能な関数

概要

前提知識: Turing機械, μ再帰関数, 万能Turing機械, 停止問題

自然数の関数のうち、有限個の命令からなる機械的な手順で値を求められるものを 計算可能関数 という。厳密には、Turing機械で計算できる関数、あるいは同じことだが μ再帰関数として作れる関数のことである。手順が止まらない入力では値が定まらないので、計算可能性の理論は最初から部分関数を相手にする。値が常に定まる（全域的な）ものだけを計算可能関数とよび、部分関数を含めるときは部分計算可能関数とよぶのが標準的である（OLT26 §30.1、p. 447）。
この記事では計算可能関数を定義し、番号付け $\varphi_0,\varphi_1,\dots$ をもとに、次のことを証明する。部分関数が計算可能であることはグラフが半決定可能であることと同値であり、全域関数なら計算可能性とグラフの決定可能性が同値である。無限集合が半決定可能であることは単射な計算可能関数の値域であることと、決定可能であることは狭義単調増加な計算可能関数の値域であることと同値である。最後に、すべての計算可能関数を十分先で上から押さえる関数は計算可能でないことを示す。

記法と前提

$\mathbb{N}=\{0,1,2,\dots\}$ とする。$\mathbb{N}^k$ の部分集合の上で定義された写像を部分関数といい $f\colon\mathbb{N}^k\rightharpoonup\mathbb{N}$ と書く。$f(\vec x)$ が定義されることを $f(\vec x)\!\downarrow$、されないことを $f(\vec x)\!\uparrow$ と書き、$e_1\simeq e_2$ は「両辺とも定義されて等しいか、両辺とも定義されない」ことを表す（μ再帰関数の記事の記法）。$f$ の定義域を $\operatorname{dom}f$、グラフを $\Gamma_f:=\{(\vec x,y)\mid f(\vec x)\!\downarrow,\ f(\vec x)=y\}\subset\mathbb{N}^{k+1}$ と書く。
自然数の有限列は $\langle a_0,\dots,a_{k-1}\rangle:=\prod_{i< k}p(i)^{a_i+1}$（$p(i)$ は $i$ 番目の素数）で符号化し、$c$ の $i$ 番目の項を $(c)_i$ と書く。符号化 $(a_0,\dots,a_{k-1})\mapsto\langle a_0,\dots,a_{k-1}\rangle$ と $(i,c)\mapsto(c)_i$ は原始再帰関数であり、$(\langle a_0,\dots,a_{k-1}\rangle)_i=a_i$ である（万能Turing機械の記事の補題「列の操作は原始再帰的」）。
次の事実を使う。

(A) 計算のモデルの一致．Turing 計算可能な部分関数の全体と μ再帰関数の全体は、変数の個数ごとに一致する（Gal15 §7.7.1、p. 355。全域関数については Bil03 Theorem 13.14（p. 92）、Theorem 14.8・Corollary 14.9（p. 97））。「μ再帰関数は Turing 計算可能である」向きを (A1)、逆向きを (A2) と書く。1 変数の関数についての (A2) は万能Turing機械の記事で証明されている（定理「万能関数の標準形」と、定理「万能 Turing 機械の存在」の後の注意）。(A1) はこの記事では証明しない。μ再帰関数とレジスタ機械で計算できる関数の一致は Church–Turingのテーゼの記事で証明されている。
(A) により、μ再帰関数が合成・原始再帰・μ 作用素で閉じていること（μ再帰関数の記事の定義「μ再帰関数」）は、Turing 計算可能な部分関数についても成り立つ。

定義

計算可能関数

部分関数 $f\colon\mathbb{N}^k\rightharpoonup\mathbb{N}$ が Turing 計算可能であるとき（Turing機械の記事の定義「Turing 機械が計算する関数」）、$f$ は 部分計算可能（partial computable）であるという。
部分計算可能な関数のうち全域的なもの $f\colon\mathbb{N}^k\to\mathbb{N}$ を 計算可能関数（computable function）という。
$A\subset\mathbb{N}^k$ の特性関数 $\chi_A$ が計算可能関数であるとき、$A$ は 計算可能（決定可能）であるという。$A$ がある部分計算可能関数の定義域であるとき、$A$ は 半決定可能（計算可能枚挙）であるという（停止問題の記事の定義「決定可能と半決定可能」と同じ）。

(A) により、1 の「Turing 計算可能」は「μ再帰的」に置き換えてよい。したがって計算可能関数は μ再帰関数の記事の意味の再帰関数（全域的な μ再帰関数）と同じものであり、古い文献では帰納的関数・再帰関数とよばれる。どの計算のモデルで定義しても同じ関数の全体が得られること、およびそれが「直観的に計算できる関数」を捉えているという主張は Church–Turingのテーゼの記事で扱う。

番号付け

万能Turing機械の記事では、Turing 機械に番号 $e$ を付け、番号 $e$ の機械の出力を表す万能関数 $u(e,x)$ を定めた（同記事の定義「出力関数と万能関数」）。これを使う。

標準の番号付け

$e\in\mathbb{N}$ に対し、1 変数の部分関数 $\varphi_e$ を $\varphi_e(x):\simeq u(e,x)$ で定める。$k$ 変数の部分関数 $\varphi^{(k)}_e$ を $\varphi^{(k)}_e(x_1,\dots,x_k):\simeq\varphi_e(\langle x_1,\dots,x_k\rangle)$ で定める。$e$ を $\varphi_e$（$\varphi^{(k)}_e$）の番号（index）という。

万能Turing機械の記事の定理「万能関数の標準形」により、原始再帰的な関係 $T(e,x,s)$ と原始再帰関数 $V(e,x,s):=\operatorname{Out}(\operatorname{conf}(e,x,s))$ があって
$$ \varphi_e(x)\simeq V\bigl(e,x,\ \mu s\,T(e,x,s)\bigr) $$
が成り立つ。$1\mathbin{\dot-}\chi_T$ は全域的なので、$\mu s\,T(e,x,s)$ が定義されるのは $T(e,x,s)$ となる $s$ があるときちょうどである。よって $\varphi_e(x)\!\downarrow$ は $\exists s\ T(e,x,s)$ と同値である。

番号付けは部分計算可能関数をすべて並べる

$k\ge1$ とする。部分関数 $f\colon\mathbb{N}^k\rightharpoonup\mathbb{N}$ が部分計算可能であることは、ある $e$ で $f=\varphi^{(k)}_e$ となることと同値である。さらに $(e,\vec x)\mapsto\varphi^{(k)}_e(\vec x)$ は $k+1$ 変数の部分計算可能関数である。

$(e,x)\mapsto\varphi_e(x)=u(e,x)$ は、標準形により原始再帰関数と μ 作用素から作られる μ再帰関数なので、(A1) により部分計算可能である。$\varphi^{(k)}_e(\vec x)\simeq u(e,\langle\vec x\rangle)$ はこれと原始再帰関数 $\vec x\mapsto\langle\vec x\rangle$ の合成なので、$k+1$ 変数の部分計算可能関数である。とくに各 $\varphi^{(k)}_e$ は部分計算可能である（$e$ を定数として代入する）。
逆に $f$ を部分計算可能とし、$g(z):\simeq f((z)_0,\dots,(z)_{k-1})$ とおく。$g$ は $f$ と原始再帰関数の合成なので、(A) により 1 変数の部分計算可能関数である。万能Turing機械の記事の定理「万能 Turing 機械の存在」の後半により、すべての $z$ で $g(z)\simeq u(e,z)$ となる $e$ がある（$g$ を計算する機械の番号をとればよい）。すると $(\langle\vec x\rangle)_i=x_{i+1}$ なので
$$ \varphi^{(k)}_e(\vec x)\simeq u(e,\langle\vec x\rangle)\simeq g(\langle\vec x\rangle)\simeq f(\vec x) $$
である。$\square$

万能Turing機械の記事の補題「標準の機械はどれも番号をもつ」により、1 変数の部分計算可能関数を計算する機械の番号は無限個あるので、1 変数の部分計算可能関数はどれも無限個の番号をもつ。

例

計算可能関数の例

原始再帰関数はすべて全域的な μ再帰関数なので、(A1) により計算可能関数である。加法・乗法・冪・切り捨て差、素数の判定の特性関数、$n$ 番目の素数 $p(n)$ などがそうである（原始再帰関数の記事の例「算術の基本的な関数」と命題「素数の判定と $n$ 番目の素数」）。
Ackermann 関数は原始再帰関数ではないが（原始再帰関数の記事の系「Ackermann 関数は原始再帰でない」）、全域的な μ再帰関数であり（μ再帰関数の記事の定理「Ackermann 関数は再帰関数である」）、したがって計算可能関数である。
部分計算可能だが全域的でない関数の例として、$h(x):\simeq\mu s\,[\,x=s+s\,]$ がある。$x$ が偶数なら $h(x)=x/2$、奇数なら $h(x)$ は定義されない。
円周率 $\pi$ の 10 進展開に $7$ が $n$ 個以上連続して現れるとき $f(n)=1$、そうでないとき $f(n)=0$ と定める。$f$ は計算可能関数である。実際、$f(n)=1$ なら $f(m)=1$（$m\le n$）なので、すべての $n$ で $f(n)=1$ であるか、ある $N$ があって $f(n)=1$（$n\le N$）、$f(n)=0$（$n>N$）となる。どちらの場合も $f$ は原始再帰関数である（後者は $f(n)=\overline{\mathrm{sg}}(n\mathbin{\dot-}N)$）。ただし、どちらの場合なのか、後者なら $N$ がいくつなのかを知らなくても、この議論は成り立つ。計算可能であることは、計算する手順が存在することであって、その手順を私たちが知っていることではない。

計算可能でない関数の例

自己停止集合 $K=\{e\mid M_e\text{ は入力 }e\text{ で停止する}\}$ の特性関数 $\chi_K$ は計算可能でない（停止問題の記事の定理「停止問題の決定不能性」）。
関数 $\mathbb{N}\to\{0,1\}$ は非可算個あるが、計算可能関数は番号で並ぶので可算個しかない（prop-cf-index）。したがって計算可能でない関数は「ほとんどすべて」である（Turing機械の記事の定理「Turing 計算可能でない関数の存在」）。
下の thm-cf-domination の関数 $F$ は計算可能でない。

ex-cf-examples の 4 と ex-cf-noncomputable の 1 は対照的である。例 4 の $f$ は値を求める手順を具体的に書けないのに計算可能であり、$\chi_K$ は値の定義が明確なのに計算可能でない。計算可能性は関数そのものの性質であって、定義の書き方の性質ではない。

性質

停止した計算の読み取り

標準形の $\mu s\,T(e,x,s)$ は、正しく停止した計算の段数を探している。探索を「段数 $s$ を 1 つ与えて確かめる」形に直すと、上界のない探索を量化記号 $\exists s$ 1 つにまとめられる。

停止した計算の読み取り

関係 $R\subset\mathbb{N}^4$ を
$$ R(e,x,y,s)\ :\Longleftrightarrow\ T(e,x,s)\ \land\ \forall t< s\ \lnot T(e,x,t)\ \land\ V(e,x,s)=y $$
で定める。$R$ は原始再帰的な関係であり、すべての $e,x,y$ について
$$ \varphi_e(x)\!\downarrow\ \text{かつ}\ \varphi_e(x)=y\quad\Longleftrightarrow\quad\exists s\ R(e,x,y,s) $$
が成り立つ。さらに各 $(e,x)$ について、$R(e,x,y,s)$ となる組 $(y,s)$ は高々 1 つである。

要点：$R$ は原始再帰的な関係を有界量化と共通部分で組み合わせたものであり、$R(e,x,y,s)$ は「$s$ が標準形の探索 $\mu s\,T(e,x,s)$ の値で、そのときの出力が $y$」と同じことを述べている。

詳しい証明を開く

$T$ と $V$ は原始再帰的で、原始再帰的な関係は有界量化・共通部分で閉じ、等号は原始再帰的なので（原始再帰関数の記事の命題「有界な和・積・量化・最小化」と例「関係と特性関数」）、$R$ は原始再帰的である。

$R(e,x,y,s)$ とする。$T(e,x,s)$ が成り立ち $t< s$ では成り立たないので、$\mu s'\,T(e,x,s')=s$ である。標準形により $\varphi_e(x)=V(e,x,s)=y$ である。逆に $\varphi_e(x)=y$ なら、標準形の右辺が定義されるので $s_0:=\mu s\,T(e,x,s)$ が定義され、$\varphi_e(x)=V(e,x,s_0)$ である。$s_0$ の最小性から $R(e,x,y,s_0)$ が成り立つ。最後の主張：$R(e,x,y,s)$ なら $s$ は $T(e,x,\cdot)$ を満たす最小の数であり、$y=V(e,x,s)$ なので、$(y,s)$ は $(e,x)$ だけで決まる。$\square$

グラフによる特徴づけ

計算可能性とグラフ

$k\ge1$、$f\colon\mathbb{N}^k\rightharpoonup\mathbb{N}$ を部分関数とする。

$f$ が部分計算可能であることと、グラフ $\Gamma_f\subset\mathbb{N}^{k+1}$ が半決定可能であることは同値である。
$f$ が全域的なら、$f$ が計算可能であること、$\Gamma_f$ が決定可能であること、$\Gamma_f$ が半決定可能であることの三つは同値である。

以下、$\vec x=(x_1,\dots,x_k)$ について $\langle\vec x\rangle=\langle x_1,\dots,x_k\rangle$、$\langle\vec x,y\rangle=\langle x_1,\dots,x_k,y\rangle$ と書く。
1 の「部分計算可能 ⇒ 半決定可能」：prop-cf-index により $f=\varphi^{(k)}_e$ となる $e$ がある。$f(\vec x)\simeq\varphi_e(\langle\vec x\rangle)$ なので、lem-cf-stage により
$$ (\vec x,y)\in\Gamma_f\iff\exists s\ R(e,\langle\vec x\rangle,y,s) $$
である。$g(\vec x,y):\simeq\mu s\,\bigl[\,1\mathbin{\dot-}\chi_R(e,\langle\vec x\rangle,y,s)=0\,\bigr]$ とおくと、μ 作用素を施す関数は全域的な原始再帰関数なので、$g$ は μ再帰関数であり、$g(\vec x,y)$ が定義されるのは $(\vec x,y)\in\Gamma_f$ のときちょうどである。(A1) により $g$ は部分計算可能なので、$\Gamma_f=\operatorname{dom}g$ は半決定可能である。
1 の「半決定可能 ⇒ 部分計算可能」：$\Gamma_f=\operatorname{dom}\psi$ となる部分計算可能関数 $\psi\colon\mathbb{N}^{k+1}\rightharpoonup\mathbb{N}$ をとる。prop-cf-index により $\psi=\varphi^{(k+1)}_d$ となる $d$ があり、標準形の後の注意から
$$ (\vec x,y)\in\Gamma_f\iff\varphi_d(\langle\vec x,y\rangle)\!\downarrow\iff\exists s\ T(d,\langle\vec x,y\rangle,s) $$
である。そこで、値の候補 $y$ と段数 $s$ を 1 つの数 $w$ にまとめて探し、
$$ f'(\vec x):\simeq\Bigl(\mu w\,\bigl[\,T\bigl(d,\langle\vec x,(w)_0\rangle,(w)_1\bigr)\,\bigr]\Bigr)_0 $$
とおく。μ 作用素を施す関数は全域的な原始再帰関数なので、$f'$ は μ再帰関数である。$f'=f$ を示す。$f(\vec x)=y$ とすると、$T(d,\langle\vec x,y\rangle,s)$ となる $s$ があり、$w=\langle y,s\rangle$ は条件を満たすので、最小の $w_1$ が存在する。$T(d,\langle\vec x,(w_1)_0\rangle,(w_1)_1)$ から $(\vec x,(w_1)_0)\in\Gamma_f$ であり、$f$ は写像なので $(w_1)_0=f(\vec x)=y$ である。よって $f'(\vec x)=y$ である。$f(\vec x)$ が定義されないなら、$(\vec x,y)\in\Gamma_f$ となる $y$ はないので、条件を満たす $w$ はなく、$f'(\vec x)$ も定義されない。よって $f=f'$ は μ再帰関数であり、(A1) により部分計算可能である。
2：$f$ が計算可能なら、$\chi_{\Gamma_f}(\vec x,y)=\overline{\mathrm{sg}}(\lvert f(\vec x)-y\rvert)$ は計算可能関数の合成で全域的なので、(A) により計算可能関数であり、$\Gamma_f$ は決定可能である。$\Gamma_f$ が決定可能なら半決定可能である（停止問題の記事の定理「決定可能性と半決定可能性」の証明の前半。$\mu s\,[\,1\mathbin{\dot-}\chi_{\Gamma_f}(\vec x,y)=0\,]$ の定義域が $\Gamma_f$ になる）。$\Gamma_f$ が半決定可能なら、1 により $f$ は部分計算可能であり、全域的なので計算可能関数である。$\square$

証明の後半は「値の候補と計算の段数の組を、$0,1,2,\dots$ と順に調べる」手順である。値の候補だけを順に調べると、ある候補 $y$ についての確かめが止まらないとき先へ進めない。候補と段数を対にして並べるのは、このような探索の基本的な技法である。
2 の「全域的」は外せない。$f(x)=0$（$x\in K$）、$f(x)$ は定義されない（$x\notin K$）とすると、$f$ は部分計算可能だが、$\Gamma_f=K\times\{0\}$ は決定可能でない（下の反例の表）。

全単射の逆写像

$f\colon\mathbb{N}\to\mathbb{N}$ を単射な計算可能関数とする。値域 $f(\mathbb{N})$ の上で定義された逆写像 $f^{-1}\colon\mathbb{N}\rightharpoonup\mathbb{N}$ は部分計算可能である。とくに $f$ が全単射なら $f^{-1}$ は計算可能関数である。

$\Gamma_{f^{-1}}=\{(y,x)\mid f(x)=y\}$ は、thm-cf-graph の 2 により決定可能な $\Gamma_f$ の成分を入れ替えたものなので決定可能であり、とくに半決定可能である。thm-cf-graph の 1 により $f^{-1}$ は部分計算可能である。全単射なら $f^{-1}$ は全域的である。$\square$

計算可能関数による枚挙

空でない半決定可能な集合は「計算可能関数の値域として並べ上げられる集合」と言い換えられる（OLT26 Theorem 30.9、p. 455）。無限集合については、並べ方を重複のない形や大きさの順に整えられるかどうかで、半決定可能と決定可能が分かれる。
まず、無限の決定可能集合を小さい順に並べる手順が計算できることを確かめる。この補題は下の定理の証明で 2 回使う。

無限の決定可能集合を小さい順に並べる

$Q\subset\mathbb{N}$ を無限の決定可能集合とし、$q(0):=\mu w\,[\,w\in Q\,]$、$q(n+1):=\mu w\,[\,w>q(n)\ \land\ w\in Q\,]$ と定める。$q$ は狭義単調増加な計算可能関数で、$q(\mathbb{N})=Q$ である。

要点：$Q$ が無限なので「$v$ より大きい $Q$ の最小の元」を求める探索は必ず止まり、$q$ は全域的な μ再帰関数になる。$q(n)$ は $Q$ の元を小さい順に並べた $n$ 番目の元である。

詳しい証明を開く

$\chi_Q$ は (A2) により全域的な μ再帰関数である。$Q$ は無限集合なので、どの $v$ に対しても $w>v$ となる $w\in Q$ があり、$H(v):\simeq\mu w\,[\,w>v\land w\in Q\,]$ は（μ 作用素を全域的な $\overline{\mathrm{sg}}(\chi_{<}(v,w)\cdot\chi_Q(w))$ に施したものなので）全域的な μ再帰関数である。$Q$ は空でないので $a:=\mu w\,[\,w\in Q\,]$ が定まり、$q$ は $q(0)=a$、$q(n+1)=H(q(n))$ というパラメータのない原始再帰で定まるので全域的な μ再帰関数であり、(A1) により計算可能関数である。定義から $q(n)\in Q$、$q(n)< q(n+1)$ である。$q(\mathbb{N})=Q$ を示す。$w\in Q$ とし、$Q$ の元で $w$ より小さいものの個数を $m$ とする。$n$ についての帰納法により、$q(n)$ は $Q$ の元を小さい順に並べた $n$ 番目（$0$ から数える）の元である（$q(n+1)$ は $q(n)$ より大きい $Q$ の最小の元だから）。よって $q(m)=w$ である。$\square$

無限集合の枚挙

$A\subset\mathbb{N}$ を無限集合とする。

$A$ が半決定可能であることと、単射な計算可能関数 $g\colon\mathbb{N}\to\mathbb{N}$ で $A=g(\mathbb{N})$ となるものがあることは同値である。
$A$ が決定可能であることと、狭義単調増加な計算可能関数 $g\colon\mathbb{N}\to\mathbb{N}$ で $A=g(\mathbb{N})$ となるものがあることは同値である。

1 の ⇐：$A=g(\mathbb{N})$ とする。$h(y):\simeq\mu n\,[\,g(n)=y\,]$ は、$g$ が (A2) により全域的な μ再帰関数なので μ再帰関数であり、$h(y)$ が定義されるのは $y\in g(\mathbb{N})$ のときちょうどである。(A1) により $A=\operatorname{dom}h$ は半決定可能である。
1 の ⇒：$A=\operatorname{dom}\psi$ となる部分計算可能関数 $\psi$ をとり、prop-cf-index により $\psi=\varphi_e$ とする。標準形の後の注意から $x\in A\iff\exists s\ T(e,x,s)$ である。
$$ w\in Q\ :\Longleftrightarrow\ w=\langle(w)_0,(w)_1\rangle\ \land\ T\bigl(e,(w)_0,(w)_1\bigr)\ \land\ \forall t<(w)_1\ \lnot T\bigl(e,(w)_0,t\bigr) $$
とおく。$Q$ は原始再帰的な関係なので決定可能である。$x\in A$ に対し、$T(e,x,s)$ となる最小の $s$ を $s_x$ とすると、$Q=\{\langle x,s_x\rangle\mid x\in A\}$ であり、$x\mapsto\langle x,s_x\rangle$ は $A$ から $Q$ への全単射である（逆写像は $w\mapsto(w)_0$）。$A$ は無限なので $Q$ も無限である。lem-cf-increasing の $q$ をとり、$g(n):=(q(n))_0$ とおく。$g$ は計算可能関数で、$q$ が単射で $w\mapsto(w)_0$ が $Q$ の上で単射なので $g$ は単射であり、$g(\mathbb{N})=\{(w)_0\mid w\in Q\}=A$ である。
2 の ⇒：$A$ は無限の決定可能集合なので、lem-cf-increasing の $q$（$Q=A$ として）が求める $g$ である。
2 の ⇐：$g$ は狭義単調増加なので、$n$ についての帰納法で $g(n)\ge n$ である。よって $y\in A$ なら $y=g(n)$ となる $n$ は $n\le y$ を満たし、
$$ \chi_A(y)=\mathrm{sg}\Bigl(\sum_{n\le y}\overline{\mathrm{sg}}\bigl(\lvert g(n)-y\rvert\bigr)\Bigr) $$
である。右辺は全域的な μ再帰関数 $g$ から合成と原始再帰（有界和）で作られるので全域的な μ再帰関数であり、(A1) により $\chi_A$ は計算可能関数である。$\square$

1 と 2 の差は、並べた値を見て「$y$ はもう出てこない」と判断できるかどうかにある。小さい順に並んでいれば $y$ を超えた時点で判断できるが、重複がないだけでは、$y$ がいつ現れるかの見当がつかない。

自己停止集合を並べる

自己停止集合 $K$ は半決定可能であり（停止問題の記事の定理「停止集合は半決定可能」）、無限集合である。実際、定数関数 $0$ を計算する機械の番号は無限個あり（万能Turing機械の記事の補題「標準の機械はどれも番号をもつ」）、そのような番号 $e$ では $M_e$ は入力 $e$ で停止するので $e\in K$ である。thm-cf-enumeration の 1 により、$K=g(\mathbb{N})$ となる単射な計算可能関数 $g$ がある。一方 $K$ は決定可能でないので、2 により、$K$ を小さい順に並べる計算可能関数はない。

計算可能関数を上から押さえる関数

計算可能関数の中には Ackermann 関数のように急速に増えるものがあるが、すべての計算可能関数を同時に上から押さえる関数は計算できない。

計算可能関数を押さえる関数は計算できない

$$ F(n):=\max\bigl(\{0\}\cup\{\varphi_e(x)\mid e\le n,\ x\le n,\ \varphi_e(x)\!\downarrow\}\bigr) $$
とおく（有限集合の最大値なので $F\colon\mathbb{N}\to\mathbb{N}$ は全域的に定まる）。

どの計算可能関数 $g\colon\mathbb{N}\to\mathbb{N}$ についても、ある $N$ があって、$n\ge N$ ならば $g(n)\le F(n)$ である。
1 の性質をもつ関数 $h\colon\mathbb{N}\to\mathbb{N}$（どの計算可能関数 $g$ にも $N_g$ があって $n\ge N_g$ なら $g(n)\le h(n)$ となる関数）は計算可能でない。とくに $F$ は計算可能でない。

1：prop-cf-index により $g=\varphi_e$ となる $e$ がある。$N:=e$ とおく。$n\ge e$ なら、$e\le n$、$x:=n\le n$ で $\varphi_e(n)=g(n)$ が定義されるので、$g(n)$ は $F(n)$ の最大値をとる集合に属し、$g(n)\le F(n)$ である。
2：$h$ が計算可能だとすると、$g(n):=h(n)+1$ も計算可能関数である。$h$ の性質から、ある $N$ があって $n\ge N$ で $h(n)+1=g(n)\le h(n)$ となり、矛盾する。1 により $F$ はこの性質をもつので計算可能でない。$\square$

$F(n)$ の定義は、有限個の組 $(e,x)$ について「$\varphi_e(x)$ が定義されるかどうか」を知っていれば計算できる形をしている。計算できないのは、まさにその判定ができないためである（停止問題）。停止問題の記事の系「停止時間は計算可能な関数で押さえられない」も同じ現象を、停止までのステップ数について述べている。

番号付けについてのそのほかの基本定理

OLT26 第 30 章は、計算のモデルを 1 つ固定して標準形 $\varphi_e(x)\simeq U(\mu s\,T(e,x,s))$ で定めた番号付け（p. 450）について、次の定理を示している。同書は s-m-n 定理を、Turing 機械の番号に対して「入力の前に引数を書き足してから動かす機械の番号」を求める操作として説明している（p. 451）。以下の $\varphi_e$、$\varphi^{(n)}_e$ は同書の番号付けを表す。いずれもこの記事では証明しない。

s-m-n 定理：原始再帰関数 $s^m_n$ があって $\varphi^{(n)}_{s^m_n(e,\vec a)}(\vec y)\simeq\varphi^{(m+n)}_e(\vec a,\vec y)$ が成り立つ。番号に引数の一部を「埋め込む」操作が計算できることを述べる（Theorem 30.3、p. 450。s-m-n定理）。
Kleene の再帰定理：どの部分計算可能関数 $g(x,y)$ にも、すべての $y$ で $\varphi_e(y)\simeq g(e,y)$ となる番号 $e$ がある（Lemma 30.25・Theorem 30.26、p. 468。Kleeneの再帰定理）。
Rice の定理：部分計算可能関数の集まり $\mathcal{C}$ について、$\{e\mid\varphi_e\in\mathcal{C}\}$ が決定可能なら、$\mathcal{C}$ は空か部分計算可能関数の全体である（Theorem 30.23、p. 465。Riceの定理）。たとえば $\{e\mid\varphi_e\text{ は全域的}\}$ は決定可能でない（Proposition 30.22、p. 464）。

反例：条件を外すと成り立たない

外す条件	反例	成り立たなくなること
$f$ が全域的（thm-cf-graph の 2）	$f(x)=0$（$x\in K$）、$f(x)$ は定義されない（$x\notin K$）	グラフ $\Gamma_f$ が決定可能であること
$g$ が狭義単調増加（単射にとどめる）	$K=g(\mathbb{N})$ となる単射な計算可能関数 $g$	値域 $g(\mathbb{N})$ が決定可能であること
$f$ が全射（逆写像を $\mathbb{N}$ 全体へ延ばす）	$K=g(\mathbb{N})$ となる単射な $g$ の逆写像を、$K$ の外で $0$ とおいた関数 $\tilde g$	計算可能であること
番号付けで部分関数を許す	計算可能関数だけを $\psi(e,\cdot)$ として並べる全域的な $\psi$	そのような $\psi$ が計算可能であること

反例の確かめ

1 行目：$K$ は半決定可能なので（停止問題の記事の定理「停止集合は半決定可能」）、$K=\operatorname{dom}k$ となる部分計算可能関数 $k$ がある。$f(x)\simeq Z(k(x))$（$Z$ はゼロ関数）なので $f$ は部分計算可能である。$\Gamma_f=K\times\{0\}$ が決定可能なら $\chi_K(x)=\chi_{\Gamma_f}(x,0)$ も計算可能になり、停止問題の記事の定理「停止問題の決定不能性」に反する。
2 行目：ex-cf-enumerate-k の $g$ である。$g$ は単射な計算可能関数だが、値域 $K$ は決定可能でない。
3 行目：$\tilde g(y)=g^{-1}(y)$（$y\in K$）、$\tilde g(y)=0$（$y\notin K$）とする。$\tilde g$ が計算可能なら、$y\in K\iff g(\tilde g(y))=y$ である（$y\in K$ なら $g(g^{-1}(y))=y$、$y\notin K$ なら $g(\tilde g(y))\in K$ なので $y$ と異なる）。よって $\chi_K(y)=\overline{\mathrm{sg}}(\lvert g(\tilde g(y))-y\rvert)$ が計算可能になり、矛盾する。cor-cf-inverse では値域の上の部分関数 $g^{-1}$ が部分計算可能であることしか言えず、その定義域 $K$ の外への延長は計算できない。
4 行目：μ再帰関数の記事の定理「全域再帰関数の普遍関数の不存在」による。部分関数を許した $\varphi_e$ では、対角線論法の $d(x):\simeq\varphi_x(x)+1$ も部分計算可能関数として番号をもつが、$d(e)$ が定義されないことが分かるだけで矛盾しない。

補足

関数と集合の計算可能性. 集合の計算可能性は特性関数で定義した。部分関数の計算可能性をグラフで言い換えると（thm-cf-graph）、部分関数は「半決定可能な集合」に、全域関数は「決定可能な集合」に対応する。部分関数を最初から扱うことで、番号付け $\varphi_e$ と万能関数が得られ、それが停止問題や再帰定理の土台になる。
自然数以外の対象. 整数・有理数・文字列・有限グラフなど、有限の情報で表せる対象は自然数で符号化でき、その符号の上の計算可能関数として計算可能性を定める。たとえば有理数の加法は、符号化 $\pm a/b\mapsto\langle s,a,b\rangle$ の上で原始再帰関数になる。