原始再帰関数

同義語：primitive recursive function原始帰納的関数原始再帰primitive recursion

概要

前提知識: 自然数, 再帰的定義, 数学的帰納法

自然数の加法は「$x+0=x$、$x+(y+1)=(x+y)+1$」、乗法は「$x\cdot0=0$、$x\cdot(y+1)=x\cdot y+x$」と、1 つ前の値から次の値を決める形で定義できる。この「1 つ前の値から次を決める」定義のしかた（原始再帰）と、関数への代入（合成）だけを使い、ゼロ・後者（$1$ を足す）・射影という最も単純な関数から作られる関数を 原始再帰関数 という。加法・乗法・冪・階乗・素数の判定・「$n$ 番目の素数」など、数論に現れるふつうの関数はほとんどすべて原始再帰関数である。原始再帰関数は、手順をあらかじめ決まった回数だけ繰り返す計算（for ループだけで書ける計算）で求まる関数にあたる。
一方、原始再帰関数で計算できる関数のすべてが尽くされるわけではない。Ackermann 関数は再帰的な等式で定義され、具体的に計算できるが、どの原始再帰関数よりも速く増えるので原始再帰関数ではない。本記事では、原始再帰関数を定義し、有界な和・積・量化・最小化と場合分けで閉じていることと素数に関する関数が原始再帰であることを示したうえで、Ackermann 関数が原始再帰でないことを証明する。
以下、$\mathbb{N}=\{0,1,2,\dots\}$ とし、関数はすべて $\mathbb{N}^k\to\mathbb{N}$（$k\ge1$）の全域的な関数とする。$\vec x=(x_1,\dots,x_k)$ と略記する。

定義

基本関数・合成・原始再帰

基本関数 とは、次の関数である。
- ゼロ関数 $Z\colon\mathbb{N}\to\mathbb{N}$、$Z(x)=0$。
- 後者関数 $S\colon\mathbb{N}\to\mathbb{N}$、$S(x)=x+1$。
- 射影 $P^k_i\colon\mathbb{N}^k\to\mathbb{N}$、$P^k_i(x_1,\dots,x_k)=x_i$（$1\le i\le k$）。
$g\colon\mathbb{N}^m\to\mathbb{N}$ と $h_1,\dots,h_m\colon\mathbb{N}^k\to\mathbb{N}$ の合成とは、$f(\vec x)=g(h_1(\vec x),\dots,h_m(\vec x))$ で定まる $f\colon\mathbb{N}^k\to\mathbb{N}$ のことである。
$g\colon\mathbb{N}^k\to\mathbb{N}$ と $h\colon\mathbb{N}^{k+2}\to\mathbb{N}$（$k\ge1$）から 原始再帰 で定まる関数とは、
$$ f(\vec x,0)=g(\vec x),\qquad f(\vec x,y+1)=h(\vec x,y,f(\vec x,y)) $$
を満たす $f\colon\mathbb{N}^{k+1}\to\mathbb{N}$ のことである。パラメータのない場合（$k=0$）は、$a\in\mathbb{N}$ と $h\colon\mathbb{N}^2\to\mathbb{N}$ から $f(0)=a$、$f(y+1)=h(y,f(y))$ で定まる $f\colon\mathbb{N}\to\mathbb{N}$ をいう。

原始再帰の等式を満たす $f$ はただ 1 つ存在する。各 $\vec x$ を固定すると、$y\mapsto f(\vec x,y)$ は初期値 $g(\vec x)$ と規則 $(y,w)\mapsto h(\vec x,y,w)$ で定まる数列であり、その存在と一意性は再帰的定義の記事の定理「段数に依存する再帰」による。

原始再帰関数

基本関数をすべて含み、合成と原始再帰で閉じた関数の集まりのうち最小のものを $\mathcal{PR}$ と書き、その元を 原始再帰関数（primitive recursive function）という。言い換えると、$f$ が原始再帰関数であるとは、基本関数から始めて合成と原始再帰を有限回使って $f$ に至る列（構成の列）があることである。
$R\subset\mathbb{N}^k$ が 原始再帰的な関係 であるとは、その特性関数 $\chi_R$（$\vec x\in R$ なら $1$、そうでなければ $0$）が原始再帰関数であることをいう。

「最小のもの」は、基本関数を含み合成と原始再帰で閉じた関数の集まりすべての共通部分として存在する。構成の列による言い換えは、構成の列をもつ関数の全体がそのような集まりの 1 つであり、しかもそのような集まりにはどの構成の列の関数も含まれることから従う。原始再帰関数についての主張は、構成の列の長さについての帰納法で示せる。この定義は OLT26 Definition 29.1–29.3（pp. 424–425）、Bil03 Definition 13.1・13.2（pp. 87–88）と同じだが、両書は原始再帰をパラメータが 1 つ以上ある場合に限っている。パラメータのない形を加えても原始再帰関数の全体は変わらない（下の ex-primrec-basic の後の注意）。

直感

原始再帰関数は、「$y$ 回繰り返す」という回数があらかじめ決まった繰り返しだけで計算できる関数である。$f(\vec x,y)$ を計算するには、$f(\vec x,0)$ から始めて $h$ を $y$ 回使えばよく、何回繰り返すかは計算を始める前に分かっている。このため原始再帰関数はすべて全域的（どの入力でも値をもつ）であり、計算は必ず止まる。逆に、「答えが見つかるまで探し続ける」繰り返し（上界のない探索）は原始再帰には含まれない。これを加えたものが μ再帰関数である。

例

算術の基本的な関数

次の関数はどれも原始再帰関数である。各行の等式で定まる関数は、等式の右辺に現れる関数と基本関数から合成と原始再帰で作られている（射影を使って引数を並べ替える細部は省く）。

関数	定義の等式
定数 $c_a(x)=a$	$c_0=Z$、$c_{a+1}=S\circ c_a$
加法 $x+y$	$x+0=x$、$x+(y+1)=S(x+y)$
乗法 $x\cdot y$	$x\cdot0=0$、$x\cdot(y+1)=x\cdot y+x$
冪 $x^y$	$x^0=1$、$x^{y+1}=x^y\cdot x$
階乗 $y!$	$0!=1$、$(y+1)!=(y+1)\cdot y!$
前者 $\mathrm{pd}(y)$	$\mathrm{pd}(0)=0$、$\mathrm{pd}(y+1)=y$
切り捨て差 $x\mathbin{\dot-}y$	$x\mathbin{\dot-}0=x$、$x\mathbin{\dot-}(y+1)=\mathrm{pd}(x\mathbin{\dot-}y)$
符号 $\mathrm{sg}(x)$、$\overline{\mathrm{sg}}(x)$	$\mathrm{sg}(x)=1\mathbin{\dot-}(1\mathbin{\dot-}x)$、$\overline{\mathrm{sg}}(x)=1\mathbin{\dot-}x$
差の絶対値 $\lvert x-y\rvert$	$(x\mathbin{\dot-}y)+(y\mathbin{\dot-}x)$

$x\mathbin{\dot-}y$ は $x\ge y$ なら $x-y$、$x< y$ なら $0$ である。$\mathrm{sg}(x)$ は $x>0$ なら $1$、$x=0$ なら $0$、$\overline{\mathrm{sg}}(x)=1-\mathrm{sg}(x)$ である。冪では $0^0=1$ と約束している。
たとえば加法は、$g=P^1_1$、$h(x,y,w)=S(P^3_3(x,y,w))$ とした原始再帰である。階乗と前者はパラメータのない原始再帰で、$h(y,w)=S(y)\cdot w$、$h(y,w)=y$ とすればよい。パラメータのない原始再帰 $f(0)=a$、$f(y+1)=h(y,f(y))$ は、パラメータが 1 つの原始再帰 $F(x,0)=c_a(x)$、$F(x,y+1)=h(y,F(x,y))$ で $F$ を作り、$f(y)=F(Z(y),y)$ とすれば得られる。したがってパラメータのない形を許しても原始再帰関数の全体は変わらない。

関係と特性関数

等号 $x=y$ の特性関数は $\overline{\mathrm{sg}}(\lvert x-y\rvert)$、大小 $x< y$ の特性関数は $\mathrm{sg}(y\mathbin{\dot-}x)$ なので、どちらも原始再帰的な関係である。偶数全体は特性関数 $e(0)=1$、$e(y+1)=1\mathbin{\dot-}e(y)$ をもつので原始再帰的である。

性質

有界な操作で閉じていること

有界な和・積・量化・最小化

$g\colon\mathbb{N}^{k+1}\to\mathbb{N}$ を原始再帰関数、$R,R'\subset\mathbb{N}^k$ と $Q\subset\mathbb{N}^{k+1}$ を原始再帰的な関係とする。

有界和 $\sum_{z< y}g(\vec x,z)$ と有界積 $\prod_{z< y}g(\vec x,z)$（$y=0$ のときはそれぞれ $0$ と $1$）は、$(\vec x,y)$ の原始再帰関数である。
補集合 $\mathbb{N}^k\setminus R$、共通部分 $R\cap R'$、和集合 $R\cup R'$ は原始再帰的である。
有界量化 $\{(\vec x,y)\mid\exists z< y\ Q(\vec x,z)\}$ と $\{(\vec x,y)\mid\forall z< y\ Q(\vec x,z)\}$ は原始再帰的である。
場合分け：原始再帰関数 $g_1,g_2\colon\mathbb{N}^k\to\mathbb{N}$ に対し、$\vec x\in R$ なら $g_1(\vec x)$、そうでなければ $g_2(\vec x)$ をとる関数は原始再帰関数である。
有界最小化：$Q(\vec x,z)$ を満たす $z< y$ があればその最小のもの、なければ $y$ をとる関数 $\mu z< y\ Q(\vec x,z)$ は、$(\vec x,y)$ の原始再帰関数である。原始再帰関数 $b\colon\mathbb{N}^k\to\mathbb{N}$ に対し、$\mu z< b(\vec x)\ Q(\vec x,z)$ も $\vec x$ の原始再帰関数である。

1：$s(\vec x,y):=\sum_{z< y}g(\vec x,z)$ は $s(\vec x,0)=0$、$s(\vec x,y+1)=s(\vec x,y)+g(\vec x,y)$ を満たすので、$g$・加法・射影から原始再帰で作れる。有界積も $p(\vec x,0)=1$、$p(\vec x,y+1)=p(\vec x,y)\cdot g(\vec x,y)$ で同様である。
2：$\chi_{\mathbb{N}^k\setminus R}=1\mathbin{\dot-}\chi_R$、$\chi_{R\cap R'}=\chi_R\cdot\chi_{R'}$、$\chi_{R\cup R'}=\mathrm{sg}(\chi_R+\chi_{R'})$ である。
3：$\exists z< y\ Q(\vec x,z)$ の特性関数は $\mathrm{sg}\bigl(\sum_{z< y}\chi_Q(\vec x,z)\bigr)$、$\forall z< y\ Q(\vec x,z)$ の特性関数は $\prod_{z< y}\chi_Q(\vec x,z)$ であり、1 により原始再帰関数である。
4：求める関数は $g_1(\vec x)\cdot\chi_R(\vec x)+g_2(\vec x)\cdot(1\mathbin{\dot-}\chi_R(\vec x))$ に等しい。
5：
$$ m(\vec x,y):=\sum_{u< y}\ \prod_{z< u+1}\bigl(1\mathbin{\dot-}\chi_Q(\vec x,z)\bigr) $$
とおくと、1 により $m$ は原始再帰関数である（内側の積は $(\vec x,u+1)$ の原始再帰関数に $u\mapsto u+1$ を合成したもの）。内側の積は、$z\le u$ のどれも $Q(\vec x,z)$ を満たさないとき $1$、そうでなければ $0$ である。$Q(\vec x,z)$ を満たす最小の $z=w$ が $w< y$ にあれば、内側の積は $u< w$ で $1$、$u\ge w$ で $0$ なので $m(\vec x,y)=w$ である。そのような $z< y$ がなければ、すべての $u< y$ で内側の積は $1$ で、$m(\vec x,y)=y$ である。よって $m(\vec x,y)=\mu z< y\ Q(\vec x,z)$ である。後半は $m$ に $b$ を合成すればよい。$\square$

素数に関する関数

素数の判定と $n$ 番目の素数

次は原始再帰的である。

整除関係 $x\mid y$。
素数全体の集合。
$n$ 番目の素数 $p(n)$（$p(0)=2$、$p(1)=3$、$p(2)=5,\dots$）。

1：$x\mid y$ は「ある $z$ で $x\cdot z=y$」であり、そのような $z$ があれば $y=0$ なら $z=0$ ととれ、$y\ge1$ なら $z\le y$ である。よって $x\mid y\iff\exists z< y+1\ (x\cdot z=y)$ であり、ex-primrec-relations と prop-primrec-bounded の 3（上界 $y+1$ を合成する）により原始再帰的である。
2：$x$ が素数であることは「$x\ge2$ かつ、$z< x$ で $z\mid x$ となるのは $z=1$ だけ」すなわち $2\le x\ \land\ \forall z< x\ (z\mid x\to z=1)$ と同値である（$z=0$ は $x\ge2$ を割らない）。$A\to B$ は $(\text{not }A)\lor B$ なので、prop-primrec-bounded の 2・3 により原始再帰的である。
3：まず、どの $w\ge2$ についても $w$ より大きく $w!+1$ 以下の素数があることを示す。$w!+1\ge2$ なので、$w!+1$ の素因数 $q$ がある。$q\le w$ なら $q\mid w!$ なので $q\mid(w!+1)-w!=1$ となり矛盾する。よって $w< q\le w!+1$ である。
そこで $\nu(w):=\mu z< w!+2\ \bigl(w< z\ \land\ z\text{ は素数}\bigr)$ とおくと、prop-primrec-bounded の 5 により $\nu$ は原始再帰関数であり、$w\ge2$ なら $\nu(w)$ は $w$ より大きい最小の素数である（上で示したことから、条件を満たす $z$ は $z< w!+2$ の範囲にある）。$p(0)=2$、$p(n+1)=\nu(p(n))$ はパラメータのない原始再帰なので、$p$ は原始再帰関数である。$p(n)\ge2$ が帰納法で保たれるので、$p(n+1)$ は $p(n)$ の次の素数であり、$p(n)$ は確かに $n$ 番目の素数である。$\square$

同じ方法で、$x$ を $p(i)$ が割る最大の回数（素因数分解の指数）なども原始再帰関数であることが分かり、有限列を 1 つの自然数に符号化して扱えるようになる（OLT26 §29.10–29.11、pp. 434–437）。これが Gödel数化の基礎である。

Ackermann 関数は原始再帰でない

Ackermann 関数（Ackermann–Péter 関数）$A\colon\mathbb{N}^2\to\mathbb{N}$ を次の等式で定める。
$$ A(0,y)=y+1,\qquad A(x+1,0)=A(x,1),\qquad A(x+1,y+1)=A(x,A(x+1,y)). $$
各 $x$ について $a_x:=A(x,\cdot)\colon\mathbb{N}\to\mathbb{N}$ とおくと、$a_0(y)=y+1$ であり、$a_{x+1}$ は初期値 $a_x(1)$ と規則 $a_x$ による数列 $a_{x+1}(0)=a_x(1)$、$a_{x+1}(y+1)=a_x(a_{x+1}(y))$ である。よって再帰的定義の記事の定理「再帰定理」を $y$ について使えば $a_x$ から $a_{x+1}$ がただ 1 つに決まり、さらに $x$ についての再帰（値を写像 $\mathbb{N}\to\mathbb{N}$ にとる）で列 $(a_x)$ がただ 1 つに決まる。こうして $A$ は全域的な関数として矛盾なく定まる。値を計算すると $A(1,y)=y+2$、$A(2,y)=2y+3$、$A(3,y)=2^{y+3}-3$ であり、$A(4,y)$ は $2$ の冪を $y+3$ 段積み重ねたものから $3$ を引いた数になる。

Ackermann 関数の単調性

すべての $x,y\in\mathbb{N}$ について次が成り立つ。

$A(x,y)>y$。
$A(x,y+1)>A(x,y)$。
$A(x+1,y)\ge A(x,y+1)$。
$A(x+1,y)>A(x,y)$。
$A(x,A(x,y))< A(x+2,y)$。
$A(1,y)=y+2$、$A(2,y)=2y+3$、$A(x,0)\ge x+1$。
とくに 2 と 4 から、$x\le x'$ かつ $y\le y'$ なら $A(x,y)\le A(x',y')$ であり、$y< y'$ なら $A(x,y)< A(x,y')$ である。

要点：1 は $x$ についての帰納法の中で $y$ についての帰納法を行い、2〜5 は 1 から順に導く。

詳しい証明を開く

1：$x$ についての帰納法による。$x=0$ なら $A(0,y)=y+1>y$。$x+1$ の場合を $y$ についての帰納法で示す。$A(x+1,0)=A(x,1)>1>0$ である（$x$ についての帰納法の仮定）。$A(x+1,y)>y$ と仮定すると、$A(x+1,y+1)=A(x,A(x+1,y))>A(x+1,y)\ge y+1$ である（最初の不等号は $x$ についての帰納法の仮定）。

2：$x=0$ なら明らかである。$A(x+1,y+1)=A(x,A(x+1,y))>A(x+1,y)$ は 1 による。

3：$y$ についての帰納法による。$y=0$ では等号である。$A(x+1,y)\ge A(x,y+1)$ と仮定する。1 により $A(x,y+1)>y+1$ なので $A(x+1,y)\ge y+2$ であり、2 から得られる「$A(x,\cdot)$ は増加」により $A(x+1,y+1)=A(x,A(x+1,y))\ge A(x,y+2)$ である。

4：3 と 2 により $A(x+1,y)\ge A(x,y+1)>A(x,y)$。

5：3 により $A(x+2,y)\ge A(x+1,y+1)=A(x,A(x+1,y))$ である。4 により $A(x+1,y)>A(x,y)$ なので、2 により $A(x,A(x+1,y))>A(x,A(x,y))$ である。

6：$A(1,0)=A(0,1)=2$、$A(1,y+1)=A(0,A(1,y))=A(1,y)+1$ から $A(1,y)=y+2$。$A(2,0)=A(1,1)=3$、$A(2,y+1)=A(1,A(2,y))=A(2,y)+2$ から $A(2,y)=2y+3$。4 を繰り返すと $A(x,0)>A(x-1,0)>\cdots>A(0,0)=1$ なので $A(x,0)\ge x+1$。最後の単調性の主張は、$A(x,y)\le A(x',y)\le A(x',y')$（4 を $x'-x$ 回、2 を $y'-y$ 回使う）から従う。$\square$

次の定理が、原始再帰関数の増え方に上限があることを述べる主定理である。$\vec x=(x_1,\dots,x_k)$ に対し $\max\vec x:=\max\{x_1,\dots,x_k\}$ とおく。

Ackermann 関数による上からの評価

任意の原始再帰関数 $f\colon\mathbb{N}^k\to\mathbb{N}$ に対し、ある $m\in\mathbb{N}$ が存在して、すべての $\vec x\in\mathbb{N}^k$ について
$$ f(\vec x)< A(m,\max\vec x) $$
が成り立つ。

この $m$ を $f$ の 評価番号 とよぶことにする。

$f$ の構成の列についての帰納法で示す。以下 lem-primrec-ackermann-monotone を番号で引用し、$M:=\max\vec x$ とおく。
基本関数：$Z(x)=0< x+1=A(0,x)$、$S(x)=x+1< x+2=A(1,x)$（6）、$P^k_i(\vec x)=x_i\le M< A(0,M)$ なので、評価番号はそれぞれ $0,1,0$ ととれる。
合成：$f(\vec x)=g(h_1(\vec x),\dots,h_l(\vec x))$ とし、$g,h_1,\dots,h_l$ の評価番号を $m_0,m_1,\dots,m_l$、その最大を $m^*$ とする。$N:=\max_i h_i(\vec x)$ とおくと、単調性により $N< A(m^*,M)$ である。よって
$$ f(\vec x)< A(m_0,N)\le A(m^*,N)< A\bigl(m^*,A(m^*,M)\bigr)< A(m^*+2,M) $$
である。2 つ目の不等号は単調性、3 つ目は $N< A(m^*,M)$ と 2、最後は 5 による。評価番号は $m^*+2$ ととれる。
パラメータのある原始再帰：$f(\vec x,0)=g(\vec x)$、$f(\vec x,y+1)=h(\vec x,y,f(\vec x,y))$ とし、$g,h$ の評価番号を $m_g,m_h$、$m:=\max(m_g,m_h)+1$ とする。まず、すべての $\vec x,y$ について
$$ f(\vec x,y)< A(m,M+y)\qquad(\ast) $$
を $y$ についての帰納法で示す。$y=0$ では $f(\vec x,0)=g(\vec x)< A(m_g,M)\le A(m,M)$ である。$y$ で ($\ast$) が成り立つとする。1 により $M\le M+y< A(m,M+y)$、$y< A(m,M+y)$ であり、帰納法の仮定とあわせて $K:=\max(M,y,f(\vec x,y))< A(m,M+y)$ である。$m-1\ge m_h$ なので
$$ f(\vec x,y+1)< A(m_h,K)\le A(m-1,K)< A\bigl(m-1,A(m,M+y)\bigr)=A(m,M+y+1) $$
となり、$y+1$ でも ($\ast$) が成り立つ。最後の等号は Ackermann 関数の定義の 3 つ目の等式である。
次に $L:=\max(M,y)$ とおくと、$M+y\le 2L< 2L+3=A(2,L)$ である（6）。$m':=\max(m,2)$ とすると、($\ast$)、2、単調性、5 により
$$ f(\vec x,y)< A(m,M+y)< A(m,A(2,L))\le A(m',A(m',L))< A(m'+2,L) $$
であり、評価番号は $m'+2$ ととれる。
パラメータのない原始再帰：$f(0)=a$、$f(y+1)=h(y,f(y))$ とし、$h$ の評価番号を $m_h$、$m:=\max(m_h+1,a)$ とする。すべての $y$ で $f(y)< A(m,y)$ を $y$ についての帰納法で示す。$y=0$ では 6 により $A(m,0)\ge m+1>a=f(0)$ である。$f(y)< A(m,y)$ なら、1 により $y< A(m,y)$ でもあるので $\max(y,f(y))< A(m,y)$ であり、$m-1\ge m_h$ から
$$ f(y+1)< A(m_h,\max(y,f(y)))\le A(m-1,\max(y,f(y)))< A(m-1,A(m,y))=A(m,y+1) $$
である。評価番号は $m$ ととれる。$\square$

Ackermann 関数は原始再帰でない

$d(x):=A(x,x)$ は原始再帰関数でない。したがって Ackermann 関数 $A$ も原始再帰関数でない。

$d$ が原始再帰関数なら、thm-primrec-domination により、ある $m$ ですべての $x$ について $d(x)< A(m,x)$ となる。$x=m$ とおくと $A(m,m)< A(m,m)$ となり矛盾する。$A$ が原始再帰関数なら、$d(x)=A(P^1_1(x),P^1_1(x))$ は合成で得られるので原始再帰関数になってしまう。$\square$

thm-primrec-domination は「どの原始再帰関数も、Ackermann 関数のある行 $A(m,\cdot)$ より遅く増える」ことを述べている。行 $A(m,\cdot)$ は $m$ が 1 増えるごとに、加法、乗法、冪、冪の塔、…と 1 段ずつ速く増える演算になっており、対角線 $A(x,x)$ はそのすべてを追い越す。対角線 $A(x,x)$ がどの原始再帰関数の値も十分大きい $x$ で上回ることと、その帰結として $A(x,x)$ が原始再帰でないことは Bil03 Theorem 13.9・Corollary 13.10（p. 91）に述べられており、Ackermann 関数の定義は Bil03 Example 13.4（p. 90）、Gal15 Example 2.1.1（p. 11）にある。Ackermann 関数が計算できる全域関数であること、とくに μ再帰関数であることは、μ再帰関数の記事で示す。
原始再帰関数全体を計算できる形で番号付けし、対角線をずらすことでも、計算できるが原始再帰でない関数が得られる（OLT26 §29.14、pp. 440–441）。Ackermann 関数はその具体例を与える。

仮定を外したときの反例

外す条件	反例	成り立たなくなること
原始再帰を使ってよい（合成だけにする）	加法 $x+y$	作れること：合成だけで作れる関数は $f(\vec x)\le\max\vec x+c$ を満たす
後者関数を基本関数に含める	後者関数 $S$	作れること：$S$ を除くと、作れる関数は $f(\vec x)\le\max(\max\vec x,c)$ を満たす
最小化に上界を付ける（上界なしにする）	$\mu z\,\bigl(\lvert z\cdot z-x\rvert=0\bigr)$	全域的であること：$x$ が平方数でないと値がない
再帰を 1 つの変数についての原始再帰に限る（入れ子の再帰を許す）	Ackermann 関数 $A$	原始再帰関数であること（cor-primrec-ackermann）

反例の確かめ

1 行目：基本関数と合成だけから作れる関数 $f$ には、ある $c$ で $f(\vec x)\le\max\vec x+c$ となる。基本関数では $c=0$ または $1$ である。$f=g(h_1,\dots,h_l)$ で $h_i(\vec x)\le\max\vec x+c_i$、$g(\vec y)\le\max\vec y+c_0$ なら $f(\vec x)\le\max\vec x+\max_ic_i+c_0$ である。加法は $x+x=2x$ が $x+c$ を超えるので、この形の評価をもたない（1 変数の場合は Bil03 Proposition 12.8、p. 86）。
2 行目：$Z$ と射影から合成と原始再帰（パラメータのない形の初期値 $a$ を含む）だけで作れる関数には、ある $c$ で $f(\vec x)\le\max(\max\vec x,c)$ となる。合成では上と同様に評価が伝わる。原始再帰 $f(\vec x,y+1)=h(\vec x,y,f(\vec x,y))$ では、$h$ の評価と帰納法の仮定から $f(\vec x,y+1)\le\max(\max\vec x,y,f(\vec x,y),c_h)\le\max(\max\vec x,y,c_g,c_h)$ である（パラメータのない形では $c_g$ の代わりに $a$）。$S(x)=x+1$ は $x\ge c$ で $\max(x,c)=x$ を超える。
3 行目：$\lvert z\cdot z-x\rvert$ は原始再帰関数だが、上界のない最小化 $\mu z$（μ再帰関数の記事の定義）を施すと、$x$ が平方数なら $\sqrt{x}$、そうでなければ値をもたない部分関数になる。原始再帰関数はすべて全域的なので、上界のない最小化を許すと原始再帰関数の範囲を出る。
4 行目は cor-primrec-ackermann そのものである。Ackermann 関数の定義の 3 つ目の等式は、内側の $A(x+1,y)$ の値を外側の第 2 引数に入れる入れ子の再帰であり、原始再帰の形をしていない。

補足：計算可能性との関係

原始再帰関数は、基本関数から合成と原始再帰をたどって値を順に計算していけるという意味で計算でき（OLT26 §29.6、pp. 427–428）、Turing 機械でも計算できる（Bil03 Theorem 13.4、p. 89。この記事では証明しない）。ただし、計算できる全域関数のすべてが原始再帰関数ではない（cor-primrec-ackermann）。計算できる関数全体を捉えるには、上界のない最小化を加えた μ再帰関数が必要であり、それは Turing機械で計算できる部分関数の全体と一致する（Gal15 §7.7.1、p. 355）。原始再帰関数は、全域的であることが構成から保証される扱いやすい部分クラスとして、Gödel数化や Gödelの不完全性定理の証明で基本的な役割を果たす。