二重再帰法

二重再帰法（にじゅうさいきほう、英: double recursion）とは再帰関数論において、アッカーマン関数の様な原始再帰では無い関数を定義を可能にする原始再帰法(primitive recursion)の拡張である。 ラファエル・M・ロビンソン（英語版）は2つの自然数を持つ G(n, x) の様な関数を二重再帰的（double recursive）と呼んだ。それは次の様な関数だった。

• G(0, x) は変数 xを一つ与えられた関数である。
• G(n + 1, 0)の値は関数G(n, ・)および与えられた関数の代入によって得られる。
• G(n + 1, x + 1)の値はG(n + 1, x)と G(n, ・)および与えられた関数の代入によって得られる^[1]。

ロビンソンは、下記の二重再帰的関数を規定した。（元々ロザ・ペーター（英語版）によって定義されていた）

• G(0, x) = x + 1
• G(n + 1, 0) = G(n, 1)
• G(n + 1, x + 1) = G(n, G(n + 1, x))

ここで、「与えられた関数」は原始再帰的ではあるが、Gは原始再帰的では無い。実際これは現在、アッカーマン関数として知られている関数と全く等しい。

関連項目

• 原始再帰法
• アッカーマン関数

脚注