μ再帰関数

同義語：μ-recursive function部分再帰関数partial recursive function再帰関数全域再帰関数一般再帰関数部分帰納的関数μ作用素

概要

前提知識: 原始再帰関数, 部分写像, 自然数

原始再帰関数は、回数があらかじめ決まった繰り返しで計算できる関数であり、必ず値をもつ。しかし実際の計算には「条件を満たす数が見つかるまで $0,1,2,\dots$ と順に探す」という、何回で終わるか前もって分からない繰り返しもある。この探索を表す操作が μ 作用素（最小化）で、$\mu y\,[g(\vec x,y)=0]$ は「$g(\vec x,y)=0$ となる最小の $y$」を表す。そのような $y$ がなければ探索は終わらず、値は定まらない。原始再帰関数を作る操作に μ 作用素を加えて得られる関数を μ再帰関数（部分再帰関数）という。μ再帰関数は一般に部分関数であり、すべての入力で値をもつものを（全域）再帰関数という。
μ再帰関数は、計算できる関数を Turing 機械のような機械を使わずに、関数を作る操作だけで捉えたものである。Ackermann 関数は原始再帰関数ではないが μ再帰関数であり、μ 作用素が原始再帰関数の範囲を真に広げることを示す。一方で、すべての全域再帰関数を 1 つの全域再帰関数で番号付けることはできない。値をもたないことがある部分関数を許すことが、計算できる関数の理論を閉じたものにするために必要になる。本記事では、μ再帰関数を定義し、これらのことを証明する。
以下、$\mathbb{N}=\{0,1,2,\dots\}$、$\vec x=(x_1,\dots,x_k)$ とする。原始再帰関数の記号（$Z,S,P^k_i$、$\mathbin{\dot-}$、$\mathrm{sg}$、$\overline{\mathrm{sg}}$、特性関数 $\chi_R$）は原始再帰関数の記事にそろえる。

定義

$\mathbb{N}^k$ の部分集合 $D$ 上で定義された写像 $f\colon D\to\mathbb{N}$ を、$\mathbb{N}^k$ から $\mathbb{N}$ への 部分関数 といい、$f\colon\mathbb{N}^k\rightharpoonup\mathbb{N}$ と書く（部分写像）。$\vec x\in D$ のとき $f(\vec x)$ は 定義される といい $f(\vec x)\!\downarrow$ と書き、そうでないとき $f(\vec x)\!\uparrow$ と書く。$D=\mathbb{N}^k$ のとき $f$ は 全域的 である。2 つの式 $e_1,e_2$ について $e_1\simeq e_2$ は、「両辺とも定義されて等しいか、両辺とも定義されない」ことを表す。

部分関数の合成・原始再帰・μ 作用素

合成：部分関数 $g\colon\mathbb{N}^m\rightharpoonup\mathbb{N}$ と $h_1,\dots,h_m\colon\mathbb{N}^k\rightharpoonup\mathbb{N}$ に対し、$f(\vec x)\simeq g(h_1(\vec x),\dots,h_m(\vec x))$ と定める。右辺は、すべての $h_i(\vec x)$ が定義され、さらに $g$ がその値の組で定義されるときに限り定義される。
原始再帰：部分関数 $g\colon\mathbb{N}^k\rightharpoonup\mathbb{N}$、$h\colon\mathbb{N}^{k+2}\rightharpoonup\mathbb{N}$ に対し、$f(\vec x,0)\simeq g(\vec x)$、$f(\vec x,y+1)\simeq h(\vec x,y,f(\vec x,y))$ と定める（$f(\vec x,y)$ が定義されなければ $f(\vec x,y+1)$ も定義されない）。パラメータのない形（$f(0)=a$、$f(y+1)\simeq h(y,f(y))$）も同様である。
μ 作用素：部分関数 $g\colon\mathbb{N}^{k+1}\rightharpoonup\mathbb{N}$ に対し、$f(\vec x)\simeq\mu y\,[g(\vec x,y)=0]$ を次で定める。$y$ が存在して、$g(\vec x,y)=0$ であり、かつすべての $z< y$ で $g(\vec x,z)$ が定義されて $0$ でないとき、$f(\vec x)$ はそのような $y$（ただ 1 つに決まる）である。そのような $y$ がなければ $f(\vec x)$ は定義されない。

μ再帰関数

基本関数 $Z,S,P^k_i$ をすべて含み、合成・原始再帰・μ 作用素で閉じた部分関数の集まりのうち最小のものの元を μ再帰関数（μ-recursive function）または 部分再帰関数（partial recursive function）という。μ再帰関数のうち全域的なものを 再帰関数（recursive function）または 全域再帰関数 という。$R\subset\mathbb{N}^k$ は、特性関数 $\chi_R$ が再帰関数であるとき 再帰的な関係（決定可能な関係）であるという。

この定義は OLT26 §29.15 と Definition 29.26・29.27（pp. 441–443）、Gal15 Definition 7.7.6（p. 358）と同じである。原始再帰関数は全域的な μ再帰関数、すなわち再帰関数である（構成の列で μ 作用素を使わなければよい）。日本語では「帰納的関数」「部分帰納的関数」ともいう。
μ 作用素の定義で「$z< y$ のすべてで $g(\vec x,z)$ が定義されている」ことを要求するのは、$\mu y$ を「$g(\vec x,0),g(\vec x,1),\dots$ を順に計算して、初めて $0$ が出たところで止まる」手順に合わせるためである。途中で値が定義されない（計算が止まらない）$z$ があれば、手順はそこで止まらなくなる。この条件を外すと計算できない関数が定義できてしまう（Gal15 p. 358 の注意）。

正則な関数への最小化

全域関数 $g\colon\mathbb{N}^{k+1}\to\mathbb{N}$ が正則であるとは、すべての $\vec x$ について $g(\vec x,y)=0$ となる $y$ が存在することをいう。μ 作用素を全域的で正則な関数にだけ使うことにして、基本関数から合成・原始再帰・この制限された μ 作用素で作られる関数を 一般再帰関数 という（OLT26 Definition 29.30、p. 445、Bil03 Definition 13.5・13.6、p. 92）。一般再帰関数はすべて全域的な再帰関数であり、逆に全域的な再帰関数はすべて一般再帰関数である（OLT26 p. 445）。1 変数の関数 $f$ については、下の thm-mu-normal-form により $f(x)=U(\mu s\,T(e,x,s))$ と書け、$f$ が全域的なので、この μ は正則な原始再帰関数 $(x,s)\mapsto1\mathbin{\dot-}\chi_T(e,x,s)$ に施されていることから分かる。

直感

原始再帰関数は「for ループ」、μ 作用素は「while ループ」にあたる。for ループだけのプログラムは必ず止まるが、while ループは条件によっては永久に回り続ける。μ再帰関数が部分関数になるのはこのためである。値が定義されない入力は、計算が止まらない入力に対応する。計算できる関数の理論では、「止まらないこともある」計算を最初から認めたほうが見通しがよい。全域的な関数だけに限ると、計算できる関数の全体を 1 つの計算できる関数で番号付けることができなくなる（thm-mu-no-universal）からである。

例

μ 作用素による部分関数

どこでも定義されない関数：$g(x,y)=x+y+1$ は全域的な原始再帰関数だが $0$ にならないので、$\mu y\,[g(x,y)=0]$ はどの $x$ でも定義されない（Gal15 p. 358）。
平方根：$g(x,y)=\lvert y\cdot y-x\rvert$ とすると、$\mu y\,[g(x,y)=0]$ は $x$ が平方数なら $\sqrt{x}$、そうでなければ定義されない。
引き算：$g(x_1,x_2,y)=\lvert x_2+y-x_1\rvert$ とすると、$\mu y\,[g(x_1,x_2,y)=0]$ は $x_1\ge x_2$ なら $x_1-x_2$、$x_1< x_2$ なら定義されない。
全域的な例：$g(x,y)=\overline{\mathrm{sg}}(\chi_{\mathrm{P}}(y)\cdot\chi_{<}(x,y))$（$\mathrm{P}$ は素数全体、$\chi_{<}(x,y)$ は $x< y$ の特性関数）とすると、$\mu y\,[g(x,y)=0]$ は $x$ より大きい最小の素数であり、素数が無限にあるのでどの $x$ でも定義される。この関数は原始再帰関数でもある（原始再帰関数の記事の命題「素数の判定と $n$ 番目の素数」の証明）。

性質

グラフによる特徴付け

全域関数 $f\colon\mathbb{N}^k\to\mathbb{N}$ の グラフ を $G_f:=\{(\vec x,y)\mid f(\vec x)=y\}\subset\mathbb{N}^{k+1}$ とする。

グラフが再帰的な全域関数

全域関数 $f\colon\mathbb{N}^k\to\mathbb{N}$ について、$f$ が再帰関数であることと、グラフ $G_f$ が再帰的な関係であることは同値である。

$f$ が再帰関数なら、$\chi_{G_f}(\vec x,y)=\overline{\mathrm{sg}}(\lvert f(\vec x)-y\rvert)$ は再帰関数の合成なので再帰関数である（$\lvert u-v\rvert$ と $\overline{\mathrm{sg}}$ は原始再帰関数）。
逆に $\chi_{G_f}$ が再帰関数なら、$g(\vec x,y):=1\mathbin{\dot-}\chi_{G_f}(\vec x,y)$ は全域的な再帰関数で、$g(\vec x,y)=0\iff y=f(\vec x)$ である。$g$ は全域的なので μ 作用素の「途中の値が定義されている」条件は自動的に満たされ、$g(\vec x,y)=0$ となる $y$ は $f(\vec x)$ ただ 1 つなので、$\mu y\,[g(\vec x,y)=0]=f(\vec x)$ である。右辺は μ再帰関数なので、全域的な $f$ は再帰関数である。$\square$

この命題は、「値を当てる」よりも「答えが正しいかを確かめる」ほうが計算として易しい場合に、確かめる手続きと探索を組み合わせて値を求めるという、μ 作用素の典型的な使い方を表している。次の節の Ackermann 関数の計算可能性もこの形で示す。

Ackermann 関数は再帰関数である

Ackermann 関数 $A\colon\mathbb{N}^2\to\mathbb{N}$ は $A(0,y)=y+1$、$A(x+1,0)=A(x,1)$、$A(x+1,y+1)=A(x,A(x+1,y))$ で定まる全域関数であり、原始再帰関数でない（原始再帰関数の記事の系「Ackermann 関数は原始再帰でない」）。この節では $A$ が再帰関数であることを示す。方針は、「$A$ の値の計算の記録」を有限の表として表し、表が正しいかどうかの確認が原始再帰的にできることを示して、正しい表を μ 作用素で探すことである。

閉じた表

$\mathbb{N}^3$ の有限部分集合 $T$ が 閉じた表 であるとは、$T$ のすべての元 $(a,b,c)$ が次を満たすことをいう。

$a=0$ なら $c=b+1$。
$a>0$、$b=0$ なら $(a-1,1,c)\in T$。
$a>0$、$b>0$ なら、ある $d$ で $(a,b-1,d)\in T$ かつ $(a-1,d,c)\in T$。

3 つの条件は Ackermann 関数の 3 つの等式をそのまま写したもので、$(a,b,c)\in T$ は「$A(a,b)=c$ と記録されている」と読む。閉じた表は、各記録の根拠となる記録をすべて含む表である。条件はどれも「$T$ にある元が含まれる」という形なので、閉じた表どうしの和集合は閉じた表である。

閉じた表の正しさと存在

$T$ が閉じた表で $(a,b,c)\in T$ ならば $c=A(a,b)$ である。
すべての $(a,b)\in\mathbb{N}^2$ について、$(a,b,A(a,b))$ を含む閉じた表が存在する。

$\mathbb{N}^2$ に辞書式順序（$(a',b')<(a,b)$ とは $a'< a$、または $a'=a$ かつ $b'< b$）を入れる。空でない部分集合は、第 1 成分が最小のもののうち第 2 成分が最小のものを最小元にもつので、この順序は整列順序であり、これについての帰納法が使える。
1：$(a,b)$ についての辞書式順序の帰納法で、「すべての閉じた表 $T$ とすべての $c$ について、$(a,b,c)\in T$ なら $c=A(a,b)$」を示す。$a=0$ なら条件 1 から $c=b+1=A(0,b)$。$a>0$、$b=0$ なら条件 2 から $(a-1,1,c)\in T$ で、$(a-1,1)<(a,0)$ なので帰納法の仮定により $c=A(a-1,1)=A(a,0)$。$a>0$、$b>0$ なら条件 3 の $d$ について、$(a,b-1)<(a,b)$ から $d=A(a,b-1)$、$(a-1,d)<(a,b)$ から $c=A(a-1,d)=A(a-1,A(a,b-1))=A(a,b)$ である。
2：同じく辞書式順序の帰納法による。$a=0$ なら $\{(0,b,b+1)\}$ が閉じた表である。$a>0$、$b=0$ なら、帰納法の仮定で $(a-1,1,A(a-1,1))$ を含む閉じた表 $T'$ をとり、$T:=T'\cup\{(a,0,A(a,0))\}$ とする。$A(a,0)=A(a-1,1)$ なので新しい元は条件 2 を満たし、$T'$ の元は $T'$ の中で条件を満たしているので $T$ の中でも満たす。$a>0$、$b>0$ なら、$d:=A(a,b-1)$ とし、帰納法の仮定で $(a,b-1,d)$ を含む閉じた表 $T_1$ と、$(a-1,d,A(a-1,d))$ を含む閉じた表 $T_2$ をとる（$(a-1,d)<(a,b)$ に注意）。$T:=T_1\cup T_2\cup\{(a,b,A(a,b))\}$ とすると、$A(a,b)=A(a-1,d)$ なので新しい元は $d$ を証拠として条件 3 を満たし、$T$ は閉じた表である。$\square$

表を自然数で符号化する。$\pi(u,v):=2^u(2v+1)-1$ は $\mathbb{N}^2$ から $\mathbb{N}$ への全単射である（正の整数は $2^u\cdot(\text{奇数})$ とただ 1 通りに書ける）。$\langle a,b,c\rangle:=\pi(\pi(a,b),c)$ とし、有限集合 $T\subset\mathbb{N}^3$ を $\ulcorner T\urcorner:=\sum_{t\in T}2^{\langle t\rangle}$ で表す。$t=\langle a,b,c\rangle$ が $T$ に属することは、$\ulcorner T\urcorner$ を 2 進法で書いたときの $2^{\langle t\rangle}$ の位の数字が $1$ であることと同値である。

閉じた表であることの判定

次は原始再帰的である。

$\mathrm{Bit}(s,t)$：$s$ の 2 進法の $2^t$ の位の数字が $1$。
$\mathrm{Cl}(s)$：$s=\ulcorner T\urcorner$ となる閉じた表 $T$ がある（$s$ が表す集合が閉じた表である）。
対の成分を取り出す関数 $K,L$：$K(\pi(u,v))=u$、$L(\pi(u,v))=v$。

要点：各条件を、上界つきの量化と最小化で書き直す。上界は「$\mathrm{Bit}(s,t)$ なら $t< s$」と「$\pi(u,v)\ge u,v$」から得られる。

詳しい証明を開く

3：$2^u\ge u+1$ なので $\pi(u,v)\ge(u+1)(2v+1)-1\ge\max(u,2v)$ であり、$u,v\le\pi(u,v)$ である。よって $K(w)=\mu u< w+1\ \exists v< w+1\ (\pi(u,v)=w)$、$L(w)=\mu v< w+1\ \exists u< w+1\ (\pi(u,v)=w)$ と書け、原始再帰関数の記事の命題「有界な和・積・量化・最小化」により原始再帰関数である。

1：$y\ge1$ のとき $x$ を $y$ で割った商は $q(x,y)=\mu z< x+1\ (x< (z+1)\cdot y)$ で原始再帰関数であり、$\mathrm{Bit}(s,t)$ は $q(s,2^t)\mathbin{\dot-}2\cdot q(q(s,2^t),2)=1$ と同値である。

2：$s$ が表す集合 $T_s:=\{(a,b,c)\mid\mathrm{Bit}(s,\langle a,b,c\rangle)\}$ を考える。$\mathrm{Bit}(s,t)$ なら $2^t\le s$ なので $t< s$ であり、$T_s$ は有限集合で $\ulcorner T_s\urcorner=s$ である。$\langle a,b,c\rangle=t$ なら $a,b,c\le t$ である（3 の評価を 2 回使う）。$\mathrm{Cl}(s)$ は次の式と同値である：すべての $t< s$ について、$\mathrm{Bit}(s,t)$ ならば、ある $a,b,c< t+1$ で $\langle a,b,c\rangle=t$ かつ「$a=0$ かつ $c=b+1$」または「$a>0$ かつ $b=0$ かつ $\mathrm{Bit}(s,\langle a\mathbin{\dot-}1,1,c\rangle)$」または「$a>0$ かつ $b>0$ かつ、ある $d< s$ で $\mathrm{Bit}(s,\langle a,b\mathbin{\dot-}1,d\rangle)$ と $\mathrm{Bit}(s,\langle a\mathbin{\dot-}1,d,c\rangle)$」。条件 3 の $d$ を $d< s$ に限ってよいのは、$\mathrm{Bit}(s,\langle a,b-1,d\rangle)$ なら $d\le\langle a,b-1,d\rangle< s$ だからである。この式は原始再帰関数と上界つきの量化だけで書かれているので、原始再帰的である。$\square$

Ackermann 関数は再帰関数である

Ackermann 関数 $A$ は再帰関数（全域的な μ再帰関数）である。したがって、原始再帰関数の全体は再帰関数の全体の真部分集合である。

関係 $R(x,y,w)$ を「$\mathrm{Cl}(L(w))$ かつ $\mathrm{Bit}(L(w),\langle x,y,K(w)\rangle)$」で定める。lem-mu-table-pr により $R$ は原始再帰的である。$w=\pi(c,s)$ と書くと、$R(x,y,w)$ は「$s$ が表す集合は閉じた表で、$(x,y,c)$ を含む」ということである。
lem-mu-table の 2 により、$(x,y,A(x,y))$ を含む閉じた表 $T$ があるので、$w=\pi(A(x,y),\ulcorner T\urcorner)$ について $R(x,y,w)$ が成り立つ。lem-mu-table の 1 により、$R(x,y,w)$ が成り立つどの $w$ についても $K(w)=A(x,y)$ である。したがって、全域的な原始再帰関数 $g(x,y,w):=1\mathbin{\dot-}\chi_R(x,y,w)$ はどの $(x,y)$ でも零点をもち、
$$ A(x,y)=K\bigl(\mu w\,[g(x,y,w)=0]\bigr) $$
である。右辺は原始再帰関数への μ 作用素と合成で得られるので、$A$ は再帰関数である。後半は原始再帰関数の記事の系「Ackermann 関数は原始再帰でない」から従う。$\square$

証明で使った μ 作用素は 1 回だけで、しかも全域的で正則な原始再帰関数に施されている。「正しい計算の記録を探し、見つかった記録から答えを読む」というこの形は、どの μ再帰関数にも当てはまる。それを述べるのが次の Kleene の標準形定理である。

Kleene の標準形定理

原始再帰的な関係 $T(e,x,s)$ と原始再帰関数 $U(s)$ があって、任意の 1 変数の μ再帰関数 $f$ に対し、ある $e\in\mathbb{N}$ ですべての $x$ について $f(x)\simeq U(\mu s\,T(e,x,s))$ となる。ここで $\mu s\,T(e,x,s)$ は $\mu s\,[1\mathbin{\dot-}\chi_T(e,x,s)=0]$ の略記である。

標準形定理の出典と番号

この記事では標準形定理を証明しない。主張と証明の考え方は OLT26 Theorem 29.28 とその後の説明（p. 443）にある。関数の構成を番号 $e$ で表し、$T(e,x,s)$ は「$s$ は、番号 $e$ の関数の入力 $x$ での計算の記録である」ことを表す。thm-mu-ackermann の証明は、この考え方を Ackermann 関数という 1 つの関数について実行したものにあたる。$e$ を $f$ の番号（指数）といい、$\varphi_e(x):\simeq U(\mu s\,T(e,x,s))$ と書く。$(e,x)\mapsto\varphi_e(x)$ は 1 つの μ再帰関数で、すべての 1 変数の μ再帰関数を番号付けている。

全域再帰関数は番号付けられない

部分関数を許すと、すべての 1 変数の μ再帰関数を 1 つの μ再帰関数 $\varphi_e(x)$ で番号付けられる（thm-mu-normal-form）。全域関数に限ると、これはできない。

全域再帰関数の普遍関数の不存在

2 変数の全域的な再帰関数 $u\colon\mathbb{N}^2\to\mathbb{N}$ で、「すべての 1 変数の再帰関数 $f$ に対し、ある $e$ ですべての $x$ について $f(x)=u(e,x)$」を満たすものは存在しない。

そのような $u$ があったとし、$d(x):=u(x,x)+1$ とおく。$d$ は再帰関数の合成なので 1 変数の再帰関数である。仮定により、ある $e$ ですべての $x$ について $d(x)=u(e,x)$ となる。$x=e$ とおくと $u(e,e)+1=d(e)=u(e,e)$ となり矛盾する。$\square$

同じ対角線の議論を部分関数の番号付け $\varphi_e(x)$ に当てはめると、$d(x):\simeq\varphi_x(x)+1$ は μ再帰関数であり、ある $e$ で $d=\varphi_e$ となる。このとき $d(e)\simeq\varphi_e(e)+1\simeq d(e)+1$ だが、両辺がともに定義されないなら矛盾はない。実際、$d(e)$ は定義されないことが分かる。部分関数を許したことで、対角線論法の矛盾が「値をもたない」という形で吸収されている。
この 2 つを合わせると、番号 $e$ が全域関数の番号かどうか（$\varphi_e$ が全域的かどうか）は再帰的に判定できないことが分かる。判定できたとすると、全域関数の番号を小さい順に $e_0< e_1<\cdots$ と並べる関数 $n\mapsto e_n$ が μ 作用素で再帰関数として得られ、$u(n,x):=\varphi_{e_n}(x)$ が thm-mu-no-universal の否定する全域的な普遍関数になってしまうからである（全域関数は無限にあるので $e_n$ はすべての $n$ で定義される）。番号 $e$ と入力 $x$ について $\varphi_e(x)$ が定義されるかどうかを判定できないことは停止問題とよばれ、OLT26 Theorem 29.29（p. 444）が標準形定理を使って示している。

仮定を外したときの反例

外す条件	反例	成り立たなくなること
μ 作用素で途中の値がすべて定義されていること	$g(x,0)$ が定義されず $g(x,1)=0$ となる $g$	「最小の零点」を順に計算して求められること
μ 作用素を施す関数が正則であること	$g(x,y)=x+y+1$	結果が全域的であること（どこでも定義されない）
部分関数を許すこと（全域的な再帰関数だけにする）	全域的な普遍関数 $u(e,x)$ の候補	1 変数の関数全体を 1 つの関数で番号付けられること（thm-mu-no-universal）
上界のない μ 作用素を許すこと（上界つきに限る）	Ackermann 関数	作れること：上界つきの最小化だけでは原始再帰関数しか得られない

反例の確かめ

1 行目：$g(x,y)\simeq\mu z\,[\,\overline{\mathrm{sg}}(y)\cdot(x+z+1)=0\,]$ とおく。$y\ge1$ なら $\overline{\mathrm{sg}}(y)=0$ なので $z=0$ で $0$ になり $g(x,y)=0$ である。$y=0$ なら $x+z+1$ は $0$ にならないので $g(x,0)$ は定義されない。この $g$ は μ再帰関数で、$g(x,0)$ は定義されず $g(x,1)=0$ である。$\mu y\,[g(x,y)=0]$ は定義の条件（$z< 1$ で $g(x,z)$ が定義される）を満たさないので定義されない。途中の値を無視して「$g(x,y)=0$ となる最小の $y$」をとれば $1$ になるが、$g(x,0)$ を計算する手順は止まらないので、この値は $0,1,2,\dots$ と順に計算する手順では得られない。
2 行目は ex-mu-partial の 1 である。3 行目は thm-mu-no-universal そのものである。
4 行目：原始再帰関数は上界つきの最小化で閉じている（原始再帰関数の記事の命題「有界な和・積・量化・最小化」の 5）ので、基本関数から合成・原始再帰・上界つきの最小化で作れる関数はすべて原始再帰関数であり、Ackermann 関数は作れない（原始再帰関数の記事の系「Ackermann 関数は原始再帰でない」）。上界のない μ 作用素を許すと作れる（thm-mu-ackermann）。

1 行目の $g$ のように、「ある入力でだけ止まらない」部分関数を作るには μ 作用素を使う。部分関数の合成では、成分の 1 つが定義されないと全体が定義されない（たとえば $0\cdot g(x,0)$ も定義されない）ので、定義されない値を掛け算などで「消す」ことはできない。また部分関数の原始再帰では、ある $y$ で値が定義されないと、それより大きい $y$ でもすべて定義されない。

補足：Turing 機械との関係と Church–Turing のテーゼ

μ再帰関数の全体は、Turing機械で計算できる部分関数の全体と一致する（Gal15 §7.7.1、p. 355。この記事では証明しない）。全域関数については、再帰関数であることと Turing 機械で計算できることの同値が Bil03 Theorem 13.14・Theorem 14.8・Corollary 14.9（pp. 92–97）に述べられている（同書の recursive は rem-mu-regular の一般再帰関数のことである）。計算できる関数を捉えようとして提案されたほかの定義も、同じ関数の全体を与える（Gal15 同所、OLT26 §31.10、p. 492）。この一致が、「直観的に計算できる関数とは μ再帰関数（Turing 機械で計算できる関数）のことである」という Church–Turingのテーゼの根拠になっている（OLT26 Definition 31.22 の前後、pp. 492–493）。