Python(14)アッカーマン関数のお勉強

前の関連記事：Python(13)ハノイの塔

C言語による計算の理論 (Computer Science Library)でアッカーマン関数が紹介されています。コンピュータの本を2冊購入でこの本を購入してからのにわか勉強の記録なので間違っているところがあるかもしれません。ちゃんと勉強したい人は自分で直接本を読むことをお勧めします。

アッカーマン関数は計算可能な全域関数の特殊な一例

$$ack(x, y)=\begin{cases}
y+1& (x=0)  \\
ack(x-1, 1)& (x>0かつy=0)  \\
ack(x-1,  ack(x, y-1))&(x>0かつy>0)
\end{cases}$$
アッカーマン関数はこのような漸化式で定義される関数です。

「アッカーマン」はこの関数を考案した人の名前に由来します。

C言語による計算の理論 (Computer Science Library)では、アッカーマン関数は、原始帰納的関数ではないのに計算可能な全域関数として紹介されています。(P.85)

「計算可能」というのはそれを計算できるプログラムが存在する、という意味です。

全域関数とは負でない整数をすべてを引数にできる関数のことをいい、例えば$$$f(x)=1/x$$$のような関数は0は引数にできないので、全域関数ではなく、真部分関数と定義されています。

すべての負でない整数も部分といえば部分ですので全域関数もまた部分関数であることに注意が必要です。

真部分関数は部分関数から全域関数を除いたものになります。

原始帰納的関数とは計算可能な全域関数の部分集合を指し、定義がP.70に書いてあります。

「タネとなる関数$$${\rm zero}、{\rm suc}、{\rm proj}^{k}_{i}$$$を関数合成と原始帰納法を好きなだけ繰り返して作られる関数」が原始帰納的関数になります。

タネとなる関数zero()は引数にかかわらず常に0を返す関数、suc()は引数に1を加える関数、$$${\rm proj}^{k}_{i}$$$はk個の引数のうちi番目の引数を返す関数、と定義されています。

関数合成とは関数を引数にして新たな関数を生成することをいいます。

タネとなる関数は計算可能であるのでそれを関数合成して得られる関数はそれもまた計算可能となります。

原始帰納法とは引数の1つを1ずつ減じながら再帰的に定義し、その引数が0になったときに１つのまた別の原始帰納的関数になる関数です。

このように原始帰納的関数から原始帰納法で作った関数も原始帰納的関数になり計算可能となります。

ということで原始帰納的関数はすべて計算可能となります。

計算可能ということはプログラムが永久ループに陥らないということであって、繰り返し部分は繰り返す前にすでに繰り返す回数が決定できる構文（Pythonでいうとfor文）に書き換えられるもの、ということになります。

原始帰納的関数はすべて計算可能ですが、計算可能関数であっても原始帰納的関数ではないものがあります。

それには先に挙げた$$$f(x)=1/x$$$のように定義域が限定された真部分関数があります。

原始帰納的関数はすべて全域関数なので真部分関数は原始帰納的関数には含まれません。
では計算可能な全域関数ならすべて原始帰納的関数に含まれるのかというとそういうわけではなく、計算可能な全域関数なのに原始帰納的関数ではないものがあります。

その一例がアッカーマン関数になります。

すべての計算可能な関数は帰納的部分関数で定義できる

原始帰納的関数の定義に「最小化」という定義を追加したうえで、タネとなる関数に原始帰納的関数だけではなく帰納的部分関数も含めたものが帰納的部分関数になります。

そしてこうやって定義した帰納的部分関数全体と計算可能部分関数全体が一致します、、、とはっきりP89に書いてあります。

帰納的部分関数はその名の通り部分関数なのですが、真部分関数ではないので全域関数も含むので原始帰納的関数も帰納的部分関数となります。

「最小化」というのが理解できないのですよね。

P96に実際のCでの最小化のプログラムの例がでてくるのですけどそれでも私にはわかりません。

def f(x1, x2):
    y = 0
    while g(x1, x2, y) != 0:
        y += 1
    return y

Pythonで書くとこうなると思います。

3変数部分関数g()から2変数部分関数f()を得る例です。

原始帰納的関数と違って繰り返しの前に繰り返し回数は決定できず、while文で次の繰り返しを実行するのかどうか関数g()の結果をみて毎回判断することになります。

これが全然わからないのですよね。

def fib(n):
    y = 0
    while g(n, y) > 0:
        y += 1
    return y
def g(n, y):
    a, b = 1, 1
    for i in range(n-1):
        a, b = a+b, a
    return a - y
print(fib(5))

2変数関数g()からフィボナッチの数列の項を求める1変数関数f()を書いてみました、、、

aですでに答えがでていますのにその回数だけwhile文を回してaをyに移しているだけです。

ちょっといい具体例が思いつきません。

クリーネの標準形定理に至ってはさっぱりわかりません。

とりあえず「最小化」の定義を原始帰納的関数の定義に加えることによってwhile文を含むプログラム(＝すべての条件で繰り返しが止まるわけではない部分を含む）のうち計算可能な関数（繰り返しが止まるもの）のみ抽出できるようです。

これで真部分関数が含まれるのはわかりますが、アッカーマン関数は真部分関数でもないので、「最小化」の定義を追加しただけでアッカーマン関数も帰納的部分関数に含まれるのがまたよくわからないのですよね。

アッカーマン関数は真部分関数の組み合わせて全域関数になっているような気もしますけど、ちょっとわかりません。

「最小化」などの定義は本によって少し異なるようでC言語による計算の理論のP.101の「6.5最小化に関する注意」で考察されています。

「原始再帰関数」は原始帰納的関数primitive recursive functionの直訳になります。

C言語による計算の理論のP.68の欄外にその解説があって、すでに「原始帰納的関数」という訳が一般に使われており、さらに「再帰（的）関数」という用語が「再帰呼び出し使ってプログラミングされた関数」という意味で使われるときもあるので「原始帰納的関数」という言い方を使う、と書いてあります。