コンピュータサイエンス 4/27

「計算可能な関数とはどんなものか」を調べる試みとして原始帰納的関数がある。以下入力、出力ともに自然数であるとする。

1.定数関数をK[m,n](x1,x2,...,xn)=mで定義する。これは一定個数の任意の入力に対してある定数を返す関数である。例えば:
K[3,4](3,5,7)=4
この関数は入力の値を無視して常に4を返す。
2.射影関数をP[n,i](x1,x2,...,xn)=xiで定義する。これは一定個数の任意の入力に対してある個数番目の引数を返す関数である。例えば:
P[3,2](3,5,7)=5
3.後者(successor)関数をS(x)=x+1で定義する。これは引数の次の自然数を返す関数である。例えば:
S(5)=6

これらを次のルールで組み合わせて得られる任意の関数を原始帰納的関数とよぶ。

1.定数関数、射影関数、後者関数は原始帰納的である。これを初期関数とよぶ。
2.m個の入力をもつ関数fとn個の入力をもつ関数f1～fmが原始帰納的ならば、n個の変数をもつ合成関数
g(x1,x2,...,xn)=f(f1(x1,x2,...,xn),f2(x1,x2,...,xn),...,fn(x1,x2,...,xn))
は原始帰納的である。例えば:

f(x1,x2,x3)=x1+x2+x3
f1(x1,x2)=x1+x2
f2(x1,x2)=x1+2*x2
f3(x1,x2)=2*x1+x2

とするとき合成関数g(x1,x2)=f(x1+x2,x1+2*x2,2*x1+x2)=4*x1+4*x2
3.n個の入力をもつ関数fとn+2個の入力をもつ関数gが原始帰納的ならば
h(x1,...,xn,0)=f(x1,...,xn)
h(x1,...,xn,y+1)=g(x1,...,xn,y,h(x1,...,xn,0))
で定義されるhは原始帰納的である。

さて、以上で定義した原始帰納的関数がどのような意義をもつのか。直感的に、原始帰納的関数は計算可能（プログラミング可能）である。例えば足し算をする関数をadd(x,y)とすると、これは

add(x,0)=P[1,1](x)=x(つまり恒等関数、入力をそのまま返す関数)
add(x,y+1)=S(P[3,3](x,y,add(x,y)))（既に定義されているadd(x,y)の次の自然数を返している:x+(y+1)=(x+y)+1）

で定義してやればよい。他に引き算、掛け算、べき、階乗、最大値、最小値や平方根の整数部、円周率のn桁目など殆ど思いつく限りの実用的（整数値）関数は原始帰納的である。

では逆はどうか？計算可能な関数は常に原始帰納的、つまり上のルールに則る初期関数の組み合わせに還元できるのか。
答えはnoだ。（これがyesなら計算可能性の数学的定義は完了したことになるのだが・・・）
例えばAckermann関数というものが存在する:

ack(0,n)=n+1
ack(m+1,0)=ack(m,1)
ack(m+1,n+1)=ack(m,ack(m+1,n))

具体的には:

ack(0,1)=2
ack(0,1)=3
ack(1,0)=ack(0,1)=2
ack(1,1)=ack(0,ack(1,0))=ack(0,2)=3

Ackermann関数はどんな原始帰納的関数よりも早く増加する関数である。例えば:

ack(2,1)=ack(1,ack(2,0))=ack(1,ack(1,1))=5
ack(3,1)=ack(2,ack(3,0))=ack(2,ack(2,1))=13
ack(4,1)=ack(3,ack(4,0))=ack(3,ack(3,1))=65533

この関数は原始帰納的ではないが計算可能であり、プログラムも書ける。このように、原始帰納的関数は計算可能性を定義するには不十分なのである。（ちなみに、Ackermann関数が原始帰納的でないことを示す例題もあるが難しいらしい）