二重再帰法
この項目「二重再帰法」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。（原文：en:double recursion） 修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。ノートページや履歴も参照してください。（2017年9月） |
二重再帰法（にじゅうさいきほう、英: 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は原始再帰的では無い。実際これは現在、アッカーマン関数として知られている関数と全く等しい。
関連項目 編集
脚注 編集
- ^ Raphael M. Robinson (1948). “Recursion and Double Recursion”. アメリカ数学会紀要 54: 987?93. doi:10.1090/S0002-9904-1948-09121-2. オリジナルの2011年6月7日時点におけるアーカイブ。.
 | この項目は、数理論理学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。 |