Ackermann関数(Ackermann function)とは、$A(0,y)=y+1$、$A(x+1,0)=A(x,1)$、$A(x+1,y+1)=A(x,A(x+1,y))$ で定まる自然数の 2 変数関数である。辞書式順序が整礎なので全域的に定まって計算もできるが、第 $x$ 行は加法・乗法・冪・冪の塔と 1 段ずつ速く増え、$m\ge3$ で $A(m,y)=2\uparrow^{m-2}(y+3)-3$ となる。各行は原始再帰関数だが、どの原始再帰関数もある行で抑えられるので、対角線 $A(x,x)$ はそれらを追い越し、$A$ は原始再帰関数でない。逆関数は極端に遅く増え、計算量の評価に現れる。
Ackermann関数(Ackermann function)とは、自然数の組 $(x,y)$ に対し、次の 3 つの等式で定まる関数 $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\bigl(x,\ A(x+1,y)\bigr).
$$
値は機械的に計算でき、$A$ は全域的な計算可能関数である。しかし増え方が極端に速く、第 1 引数を 1 増やすごとに加法・乗法・冪・冪の塔…と演算が 1 段ずつ強くなる。その結果、対角線 $x\mapsto A(x,x)$ はどの原始再帰関数よりも最終的に大きくなり、$A$ は原始再帰関数でない。計算できる関数が原始再帰関数より真に広いことを示す最初期の具体例の一つとして知られ、現在の形は Péter が Ackermann の結果を簡単にしたものなので、Ackermann–Péter 関数とも呼ぶ(OLT26 p. 984)。
| 問い | 答え |
|---|---|
| 定義の仕方 | 2 変数の入れ子の再帰(def-ack-def) |
| 全域的に定まる理由 | $\mathbb{N}^2$ の辞書式順序が整礎だから(prop-ack-well-defined) |
| 各行の形 | $A(m,y)=2\uparrow^{m-2}(y+3)-3$($m\ge3$)(prop-ack-rows) |
| 各行は原始再帰か | はい(prop-ack-rows-pr) |
| $A$ 自身は | 原始再帰でない(cor-ack-not-pr) |
| 逆関数 | ほとんど定数とみなせるほど遅く増え、計算量の評価に現れる |
関数 $A\colon\mathbb{N}^2\to\mathbb{N}$ で、すべての $x,y\in\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))
$$
を満たすものを Ackermann 関数 という。$x$ を固定した 1 変数関数 $A(x,\cdot)$ を $A$ の 第 $x$ 行 と呼ぶ。
3 つ目の等式では、内側で計算した値 $A(x+1,y)$ を外側の第 2 引数に入れている。これを 入れ子の再帰 という。原始再帰関数 の原始再帰は、1 つの変数を 1 ずつ減らし、前の値を「材料」として使うだけで、前の値を引数の位置に戻すことはしない。
def-ack-def の等式を満たす関数 $A$ はただ 1 つ存在する。さらに、等式を左辺から右辺への書き換え規則として使う計算は、どの $(x,y)$ から始めても有限回で終わり、その値 $A(x,y)$ を与える。
$\mathbb{N}^2$ に辞書式順序 $(x',y')\prec(x,y)\iff x'< x$、または $x'=x$ かつ $y'< y$ を入れる。これは整礎関係である(無限に減少する列があれば、第 1 成分は有限回しか減らないので、ある先から第 1 成分が一定になり、第 2 成分が無限に減少して矛盾する。Gal15 p. 11 で Example 2.1.1 の直前にこの議論がある)。
等式の右辺に現れる $A$ の引数は、どれも左辺の引数より $\prec$ で小さい。実際、$(x,1)\prec(x+1,0)$、$(x+1,y)\prec(x+1,y+1)$ であり、外側の $(x,A(x+1,y))$ も第 1 成分が $x< x+1$ なので、第 2 成分がいくつであっても $(x+1,y+1)$ より小さい。
存在と計算の停止。 $(x,y)$ についての $\prec$ による帰納法(整礎帰納法)で、「$(x,y)$ から始めた計算は有限回で終わり、値が定まる」ことを示す。$x=0$ なら 1 回で $y+1$ になる。$(x+1,0)$ は $(x,1)$ の計算に帰着し、それは帰納法の仮定で終わる。$(x+1,y+1)$ では、まず $(x+1,y)$ の計算が仮定により終わって値 $w$ を返し、次に $(x,w)$ の計算も仮定により終わる。こうして得た値を $A(x,y)$ とすると、等式が成り立つ(Gal15 Example 2.1.1、p. 11 はこの帰納法で全域性を示している)。
一意性。 等式を満たす $A,A'$ があれば、$A(x,y)=A'(x,y)$ を同じ帰納法で示せる。右辺は $\prec$ で小さい引数の値だけで決まり、そこでは仮定により $A$ と $A'$ が一致するからである。$\square$
各行ごとに見ると、再帰的定義 の 1 変数の再帰だけでも定義できる。$a_0(y):=y+1$ とし、$a_x$ が決まったら $a_{x+1}$ を初期値 $a_{x+1}(0):=a_x(1)$ と規則 $a_{x+1}(y+1):=a_x(a_{x+1}(y))$ の数列として定める。$A(x,y)=a_x(y)$ である。この見方は次の節で使う。
$A(2,1)$ を書き換えで計算すると次のようになる。
$$
\begin{aligned}
A(2,1)&=A(1,A(2,0))=A(1,A(1,1))=A(1,A(0,A(1,0)))=A(1,A(0,A(0,1)))\\
&=A(1,A(0,2))=A(1,3)=A(0,A(1,2))=A(0,A(0,A(1,1)))=\cdots=A(0,A(0,A(0,A(0,1))))=5.
\end{aligned}
$$
途中の $\cdots$ では、すでに求めた $A(1,1)=3$ を展開し直している。小さな引数でも、未計算の外側の呼び出しが積み重なっていく。値の表は次のとおりである。
| $x\backslash y$ | $0$ | $1$ | $2$ | $3$ | $4$ | 第 $x$ 行の式 |
|---|---|---|---|---|---|---|
| $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $y+1$ |
| $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $y+2$ |
| $2$ | $3$ | $5$ | $7$ | $9$ | $11$ | $2y+3$ |
| $3$ | $5$ | $13$ | $29$ | $61$ | $125$ | $2^{y+3}-3$ |
| $4$ | $13$ | $65533$ | $2^{65536}-3$ | $2^{2^{65536}}-3$ | $\cdots$ | $2\uparrow\uparrow(y+3)-3$ |
$A(4,2)=2^{65536}-3$ は十進で 19729 桁である。
演算の階段を Knuth の矢印記法 で表す。正の整数 $a,b$ と $k\ge1$ について
$$
a\uparrow^1b:=a^b,\qquad a\uparrow^k1:=a,\qquad a\uparrow^{k}(b+1):=a\uparrow^{k-1}\bigl(a\uparrow^kb\bigr)\quad(k\ge2)
$$
と定める。$a\uparrow^2b=a\uparrow\uparrow b$ は $a$ を $b$ 段積み上げた冪の塔 $a^{a^{\cdot^{\cdot^{a}}}}$ で、テトレーション である。どの $k\ge1$ でも $2\uparrow^k2=4$ である($k=1$ では $2^2=4$、$k\ge2$ では $2\uparrow^k2=2\uparrow^{k-1}(2\uparrow^k1)=2\uparrow^{k-1}2$ と下げていける)。
すべての $y\in\mathbb{N}$ について
$$
A(1,y)=y+2,\qquad A(2,y)=2y+3,\qquad A(3,y)=2^{y+3}-3,
$$
であり、一般に $m\ge3$ について $A(m,y)=2\uparrow^{m-2}(y+3)-3$ である。とくに $A(4,y)=2\uparrow\uparrow(y+3)-3$ である。
各行の 2 つの等式 $A(x+1,0)=A(x,1)$、$A(x+1,y+1)=A(x,A(x+1,y))$ を $y$ についての帰納法で使う。
$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$。$A(3,0)=A(2,1)=5=2^3-3$、$A(3,y+1)=2A(3,y)+3$ なので、$A(3,y)+3=2^{y+3}$ なら $A(3,y+1)+3=2(A(3,y)+3)=2^{y+4}$ である。
$m\ge3$ で $A(m,y)+3=2\uparrow^{m-2}(y+3)$ がすべての $y$ で成り立つとして、$m+1$ の場合を $y$ についての帰納法で示す。$y=0$ では
$$
A(m+1,0)+3=A(m,1)+3=2\uparrow^{m-2}4=2\uparrow^{m-2}\bigl(2\uparrow^{m-1}2\bigr)=2\uparrow^{m-1}3
$$
である。$y$ で成り立てば
$$
A(m+1,y+1)+3=A(m,A(m+1,y))+3=2\uparrow^{m-2}\bigl(A(m+1,y)+3\bigr)=2\uparrow^{m-2}\bigl(2\uparrow^{m-1}(y+3)\bigr)=2\uparrow^{m-1}(y+4)
$$
となる。最後の等号は矢印記法の定義である。$m=3$ の場合は上で示した。$\square$
$A(m,y)+3$ を見ると、$m=1$ では $2+(y+3)$、$m=2$ では $2\cdot(y+3)$、$m=3$ では $2^{y+3}$ と、第 $m$ 行は「$2$ と $y+3$ の第 $m$ 段の演算」から $3$ を引いたものになっている。第 1 引数は演算の段数を数える変数である。
各 $x\in\mathbb{N}$ について、第 $x$ 行 $a_x=A(x,\cdot)$ は原始再帰関数である。
$x$ についての帰納法による。$a_0$ は後者関数である。$a_x$ が原始再帰関数なら、$a_{x+1}$ は $a_{x+1}(0)=a_x(1)$(定数)と $a_{x+1}(y+1)=h(y,a_{x+1}(y))$、$h(y,w):=a_x(w)$ による、パラメータのない原始再帰で得られる(原始再帰関数 の記事の定義「基本関数・合成・原始再帰」)。$h$ は $a_x$ と射影の合成なので原始再帰関数である。$\square$
したがって、原始再帰でなくなるのは 第 1 引数も動かしたとき である。行ごとの定義では、$a_x$ から $a_{x+1}$ を作る操作を $x$ 回繰り返す必要があり、その回数が入力によって変わる。
まず、$A$ が両方の引数について増加することを確かめる。
すべての $x,y\in\mathbb{N}$ について次が成り立つ。
要点:1 を二重の帰納法で示し、残りは 1 から順に出す。
1:$x$ についての帰納法で、各段で $y$ についての帰納法を行う。$x=0$ では $A(0,y)=y+1$。$x+1$ では、$A(x+1,0)=A(x,1)>1>0$ であり、$A(x+1,y)>y$ なら $A(x+1,y+1)=A(x,A(x+1,y))>A(x+1,y)\ge y+1$ である(どちらも外側の帰納法の仮定「第 $x$ 行で 1 が成り立つ」を使った)。
2:$x=0$ では明らか。$A(x+1,y+1)=A(x,A(x+1,y))>A(x+1,y)$ は 1 による。2 から、各行は狭義単調増加である。
3:$y$ についての帰納法。$y=0$ では等式 $A(x+1,0)=A(x,1)$ そのもの。$A(x,y+1)\le A(x+1,y)$ なら、1 より $y+2\le A(x,y+1)\le A(x+1,y)$ なので、第 $x$ 行の単調性から $A(x,y+2)\le A(x,A(x+1,y))=A(x+1,y+1)$。
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 と第 $x$ 行の狭義単調性から $A(x,A(x+1,y))>A(x,A(x,y))$。
6:4 を繰り返して $A(x,0)>A(x-1,0)>\cdots>A(0,0)=1$。最後の主張は 4 と 2 を繰り返し使えばよい。
以下、$\vec x=(x_1,\dots,x_k)$ について $\lvert\vec x\rvert:=\max\{x_1,\dots,x_k\}$ と書く。関数 $f\colon\mathbb{N}^k\to\mathbb{N}$ が 第 $m$ 行で抑えられる とは、すべての $\vec x$ で $f(\vec x)< A(m,\lvert\vec x\rvert)$ となることをいう。lem-ack-monotone の 4 により、第 $m$ 行で抑えられればそれより下の行でも抑えられる。
どの原始再帰関数 $f\colon\mathbb{N}^k\to\mathbb{N}$ も、Ackermann 関数のある行で抑えられる。すなわち、ある $m$ があって、すべての $\vec x\in\mathbb{N}^k$ について $f(\vec x)< A(m,\lvert\vec x\rvert)$ が成り立つ。
原始再帰関数の構成の列についての帰納法で示す。番号は lem-ack-monotone の項目である。$M:=\lvert\vec x\rvert$ とおく。
基本関数。 ゼロ関数は $0< A(0,M)$、射影は $x_i\le M< A(0,M)$ で第 $0$ 行、後者関数は $x+1< x+2=A(1,x)$ で第 $1$ 行で抑えられる(prop-ack-rows)。
合成。 $f(\vec x)=g(h_1(\vec x),\dots,h_l(\vec x))$ で、$g,h_1,\dots,h_l$ がすべて第 $p$ 行で抑えられるとする(行の番号の最大値を $p$ とすればよい)。$N:=\max_ih_i(\vec x)$ とおくと $N< A(p,M)$ である。第 $p$ 行の狭義単調性(2)と 5 から
$$
f(\vec x)< A(p,N)< A\bigl(p,A(p,M)\bigr)< A(p+2,M)
$$
となり、$f$ は第 $p+2$ 行で抑えられる。
パラメータのある原始再帰。 $f(\vec x,0)=g(\vec x)$、$f(\vec x,y+1)=h(\vec x,y,f(\vec x,y))$ で、$g,h$ が第 $p$ 行で抑えられるとする。$q:=p+1$ とおき、まず
$$
f(\vec x,y)< A(q,M+y)\qquad(\dagger)
$$
を $y$ についての帰納法で示す。$y=0$ では $f(\vec x,0)< A(p,M)< A(q,M)$。$y$ で ($\dagger$) が成り立てば、1 より $M$ と $y$ も $A(q,M+y)$ より小さいので、$K:=\max\{M,y,f(\vec x,y)\}< A(q,M+y)$ である。よって
$$
f(\vec x,y+1)< A(p,K)< A\bigl(p,A(q,M+y)\bigr)=A\bigl(q,M+y+1\bigr)
$$
となる(最後は定義の 3 つ目の等式、$q=p+1$)。
次に $L:=\max\{M,y\}=\lvert(\vec x,y)\rvert$ とおくと $M+y\le2L< 2L+3=A(2,L)$ である。$r:=\max\{q,2\}$ とすると、($\dagger$)、2、単調性、5 から
$$
f(\vec x,y)< A(q,M+y)< A\bigl(q,A(2,L)\bigr)\le A\bigl(r,A(r,L)\bigr)< A(r+2,L)
$$
となり、$f$ は第 $r+2$ 行で抑えられる。
パラメータのない原始再帰。 $f(0)=a$、$f(y+1)=h(y,f(y))$ で、$h$ が第 $p$ 行で抑えられるとする。$q:=\max\{p+1,a\}$ とおき、$f(y)< A(q,y)$ を $y$ についての帰納法で示す。$y=0$ では 6 より $A(q,0)\ge q+1>a$。$f(y)< A(q,y)$ なら 1 とあわせて $\max\{y,f(y)\}< A(q,y)$ で、$q-1\ge p$ なので
$$
f(y+1)< A\bigl(p,\max\{y,f(y)\}\bigr)\le A\bigl(q-1,\max\{y,f(y)\}\bigr)< A\bigl(q-1,A(q,y)\bigr)=A(q,y+1)
$$
である。よって $f$ は第 $q$ 行で抑えられる。$\square$
$d(x):=A(x,x)$ とおく。
1:thm-ack-domination の $m$ をとると、$x\ge m$ で $f(x)< A(m,x)\le A(x,x)=d(x)$(lem-ack-monotone の単調性)。
2:$d$ が原始再帰関数なら、thm-ack-domination の $m$ について $d(m)< A(m,m)=d(m)$ となり矛盾する。$A$ が原始再帰関数なら、$d(x)=A(x,x)$ は $A$ と射影の合成で原始再帰関数になってしまう。$\square$
1 の形の主張は Bil03 Theorem 13.9、2 は Corollary 13.10(p. 91)にあり、定義は Example 13.4(p. 90)と同じである。証明のしくみは、構成の列の 1 段ごとに使う行が、前の段の行(パラメータのない原始再帰では初期値 $a$ も)で決まる分だけしか下がらないので、どの原始再帰関数もその構成の列から決まる 1 つの行で抑えられる、というものである。$d$ はすべての行を対角線で越えていく。
計算できること。 $A$ は prf-ack-well-defined の書き換えで計算でき、未処理の外側の呼び出しをスタックに積む素朴な手順がそのまま計算の手順になる。$A$ が μ再帰関数 であることは、その記事の定理で示されている。したがって $A$ は、原始再帰関数より真に広い計算可能関数のクラスに属する。
$A(k,k)$ は $k$ について狭義単調増加で、$1,3,7,61,2\uparrow\uparrow7-3,\dots$ と増える。そこで正の整数 $n$ に対し
$$
\alpha(n):=\min\{k\in\mathbb{N}\mid A(k,k)\ge n\}
$$
とおき、逆 Ackermann 関数 と呼ぶ。
$A(0,0)=1$、$A(1,1)=3$、$A(2,2)=7$、$A(3,3)=61$、$A(4,4)=2\uparrow\uparrow7-3$ なので、
$$
\alpha(1)=0,\quad\alpha(n)=1\ (2\le n\le3),\quad\alpha(n)=2\ (4\le n\le7),\quad\alpha(n)=3\ (8\le n\le61),
$$
$62\le n\le2\uparrow\uparrow7-3$ では $\alpha(n)=4$ である。$2\uparrow\uparrow7$ は $2$ を 7 段積んだ冪の塔で、$2\uparrow\uparrow5=2^{65536}$ がすでに十進で 19729 桁ある。現実に現れるどんな入力の大きさでも $\alpha(n)\le4$ である。一方、$n>A(k,k)$ なら $\alpha(n)\ge k+1$ なので、$\alpha$ は有界でなく $\infty$ に発散する。
アルゴリズムの計算量の評価には、この $\alpha$ のように Ackermann 関数の逆として定めた関数が現れる。たとえば単一化閉包の問題には $O(m\,\alpha(m))$ 時間の算法があり、$\alpha$ は Ackermann 関数の関数としての逆である(Gal15 p. 457)。計算量の文献では、逆関数を定める式の細部(どの行を使うか、初期値など)が文献ごとに異なる。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 初期値 $A(x+1,0)=A(x,1)$(cor-ack-not-pr) | 初期値を $B(x+1,0)=0$ に替えた $B$ | $B$ は原始再帰関数になる |
| 第 1 引数も動かすこと(cor-ack-not-pr) | 第 3 行 $A(3,y)=2^{y+3}-3$ | 原始再帰関数である(prop-ack-rows-pr) |
| $f$ が原始再帰であること(thm-ack-domination) | 対角線 $d(x)=A(x,x)$ | 計算できる全域関数だが、どの行でも抑えられない |
| 右辺の引数が辞書式順序で小さいこと(prop-ack-well-defined) | 3 つ目を $B(x+1,y+1)=B(x+1,B(x,y+1))$ に替える | 計算が止まらず、等式を満たす関数も一意でない |
要点:1・4 行目は等式を 1 か所だけ替え、2・3 行目は主張の仮定を 1 つだけ外している。
1 行目:$B(0,y)=y+1$、$B(x+1,0)=0$、$B(x+1,y+1)=B(x,B(x+1,y))$ とする(全域性と一意性は prf-ack-well-defined と同じ議論で成り立つ)。$B(1,y+1)=B(1,y)+1$ から $B(1,y)=y$。$B(2,y+1)=B(1,B(2,y))=B(2,y)$ から $B(2,y)=0$。$x\ge2$ で $B(x,\cdot)=0$ なら $B(x+1,y+1)=B(x,B(x+1,y))=0$ なので、$x\ge2$ の行はすべて $0$ である。よって $B(x,y)$ は $x=0$ なら $y+1$、$x=1$ なら $y$、$x\ge2$ なら $0$ で、場合分けで定まる原始再帰関数である(原始再帰関数 の記事の命題「有界な和・積・量化・最小化」の場合分け)。
2 行目:prop-ack-rows-pr による。
3 行目:cor-ack-not-pr の 2 の証明が示すとおり、$d$ が第 $m$ 行で抑えられれば $d(m)< d(m)$ となる。$d$ が計算できることは上の「計算できること」による。
4 行目:$B(1,1)=B(1,B(0,1))=B(1,2)=B(1,B(0,2))=B(1,3)=\cdots$ と、第 2 引数が増え続けて計算が終わらない。右辺の $(x+1,B(x,y+1))$ は第 1 成分が同じで第 2 成分が大きくなりうるので、辞書式順序で小さくない。また、任意の正の整数 $c$ について、$B(0,y)=y+1$、$B(1,0)=2$、$x\ge1$ かつ $(x,y)\ne(1,0)$ では $B(x,y)=c$ と定めると 3 つの等式がすべて成り立つ($B(x,y+1)\ge1$ なので右辺はいつも $c$ になる)。$c$ を変えれば別の解になるので、一意性も成り立たない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する