かしのブログ

競技プログラミングとか

原始帰納関数についてまとめメモ

計算モデル論の授業で学習した「原始帰納関数」を忘れないうちにメモ

初期関数

初期関数は以下の3つで定義される。

$succ$ ：後者関数（successorは後継者という意味の英語、次の自然数を返す）
$zero$ ：定数ゼロ関数（常にゼロを返す）
$u^n_i$ ：射影関数（n個の引数をとり、i個目の要素を返す）

例えば

$succ(5) = 6$
$zero(2) = 0$
$u^3_2(1,2,3) = 2$

関数の合成

関数 $\displaystyle g：\mathcal{N}^m \rightarrow \mathcal{N}$ 、 $\displaystyle g_1, \cdots , g_m ：\mathcal{N}^n \rightarrow \mathcal{N}$ を用いて、

$f({\bf x}) = g(g_1({\bf x}), \cdots, g_m({\bf x}))$

なる関数 $\displaystyle \mathcal{N}^n \rightarrow \mathcal{N}$ を作る。正直、関数 $g_i$ がわざわざ $n$ 個の引数を持つ必要が内容に思えたが、こうやって一般化しておくと適応する時に脳死で使用できるので、そっちに旨味があるのかなあといった感じ。

原始帰納法

関数 $\displaystyle g：\mathcal{N}^n \rightarrow \mathcal{N}$ 、 $\displaystyle h：\mathcal{N}^{n+2} \rightarrow \mathcal{N}$ を用いて、

$f({\bf x}, 0) = g({\bf x})、f({\bf x}, k+1) = h(f({\bf x}, k), k, {\bf x})$

なる関数 $\displaystyle \mathcal{N}^(n+1) \rightarrow \mathcal{N}$ を作る。最後の引数が0かどうかを判定して処理が変わるので、数学的帰納法を使って動作を証明することができる。なんで0しかないんだろうと思ったが、自然数に対して行なっていて、かつ自然数の一番下を0と定義しているので0まで下がると処理が終わるようになっている。

原始帰納関数

初期関数に関数の合成と原始帰納法のみを有限回繰り返し適用して得られる関数を原始帰納
的関数と言う。
原始帰納関数でいろんな関数を定義すると以下のようになる。

定数関数

定数 $n$ を返す関数は次のように定義できる。

$f_n(x) = succ(succ(\cdots succ(zero(x))\cdots ))$

結局(((0+1)+1)+1)+...を $n$ 回繰り返して $n$ を実現している。

前者関数

1つ大きい数を返す後者関数に対して、1つ小さい数を返す。ただし、0の前者は0。

$pred(0) = 0、pred(k+1) = u^2_2(pred(k), k)$

$pred$ 関数の中で $pred$ を呼び出し、引数の値が1つ小さくなるので再帰的に呼び出されている。
実装するときに、値呼び出しだったらどうするんだろうとか思ったけど、検証について使うので野暮な心配だった気がする。

加算関数

$add(x, 0) = u^1_1(x)、add(x, k+1) = succ(u^3_2(add(x, k), x, k))$

乗法関数

$mult(x, 0) = zero() = 0、mult(x, k+1) = add(u^3_1(mult(x, k), x, k), u^3_2(mult(x, k), x, k))$

$add$ 関数は原始帰納関数なので、初期関数と原始帰納関数の合成と原始帰納法だけで構成しているので、これも原始帰納関数である。

減算関数

$sub(x, 0) = x、sub(x, k+1) = pred(sub(x, k))$

比較関数

$ge(x, y) = sub(1, sub(y, x))$
$gt(x, y) = sub(1, sub(succ(y), x))$
$eq(x, y) = sub(1, add(sub(x, y), sub(y, x)))$

帰納法は使ってないが、原始帰納関数の組み合わせで作ってるので、同様に原始帰納関数である

指数関数

$pow(x, 0) = 1、pow(x, k+1) = mult(u^3_1(pow(x, k), x, k), u^3_2(pow(x, k), x, k))$

max、min

$max(x, y) = add(mult(ge(x, y), x), mult(gt(y, x), y))$
$min(x, y) = sub(add(x, y), max(x, y))$

$max$ 関数は、「xがy以上」と「yがxより大きい」で仮想的に場合分けした気分で実装。等しい時はxによるようにしたのがポイント。
この辺からあんまり自身がない。もっと簡単な書き方がありそう...

また、3つ以上の引数に対して、2変数の $max$ 関数を用いて実装できる

$max3(x, y, z) = max(x, max(y, z))$

$max$ 関数は原始帰納関数なので、 $max3$ も言わずもがな原始帰納関数である。

まとめ
原始帰納関数は今までのプログラムの数式とかとは大きく考え方が違うようで、なかなかしっくりこない。
初期関数と帰納法の考え方はしっかり覚える必要がありそう