| dbo:abstract
|
- In recursive function theory, double recursion is an extension of primitive recursion which allows the definition of non-primitive recursive functions like the Ackermann function. Raphael M. Robinson called functions of two natural number variables G(n, x) double recursive with respect to given functions, if
* G(0, x) is a given function of x.
* G(n + 1, 0) is obtained by substitution from the function G(n, ·) and given functions.
* G(n + 1, x + 1) is obtained by substitution from G(n + 1, x), the function G(n, ·) and given functions. Robinson goes on to provide a specific double recursive function (originally defined by Rózsa Péter)
* G(0, x) = x + 1
* G(n + 1, 0) = G(n, 1)
* G(n + 1, x + 1) = G(n, G(n + 1, x)) where the given functions are primitive recursive, but G is not primitive recursive. In fact, this is precisely the function now known as the Ackermann function. (en)
- 二重再帰法（にじゅうさいきほう、英: double recursion）とは再帰関数論において、アッカーマン関数の様な原始再帰では無い関数を定義を可能にする原始再帰法(primitive recursion)の拡張である。は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, ・)および与えられた関数の代入によって得られる。 ロビンソンは、下記の二重再帰的関数を規定した。（元々によって定義されていた）
* G(0, x) = x + 1
* G(n + 1, 0) = G(n, 1)
* G(n + 1, x + 1) = G(n, G(n + 1, x)) ここで、「与えられた関数」は原始再帰的ではあるが、Gは原始再帰的では無い。実際これは現在、アッカーマン関数として知られている関数と全く等しい。 (ja)
|
| rdfs:comment
|
- 二重再帰法（にじゅうさいきほう、英: double recursion）とは再帰関数論において、アッカーマン関数の様な原始再帰では無い関数を定義を可能にする原始再帰法(primitive recursion)の拡張である。は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, ・)および与えられた関数の代入によって得られる。 ロビンソンは、下記の二重再帰的関数を規定した。（元々によって定義されていた）
* G(0, x) = x + 1
* G(n + 1, 0) = G(n, 1)
* G(n + 1, x + 1) = G(n, G(n + 1, x)) ここで、「与えられた関数」は原始再帰的ではあるが、Gは原始再帰的では無い。実際これは現在、アッカーマン関数として知られている関数と全く等しい。 (ja)
- In recursive function theory, double recursion is an extension of primitive recursion which allows the definition of non-primitive recursive functions like the Ackermann function. Raphael M. Robinson called functions of two natural number variables G(n, x) double recursive with respect to given functions, if
* G(0, x) is a given function of x.
* G(n + 1, 0) is obtained by substitution from the function G(n, ·) and given functions.
* G(n + 1, x + 1) is obtained by substitution from G(n + 1, x), the function G(n, ·) and given functions. (en)
|
