About: Double recursion

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Double recursion Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Software, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FDouble_recursion

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.

Attributes	Values
rdf:type	software
rdfs:label	Double recursion (en) 二重再帰法 (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)
dcterms:subject	Recursion Computability theory
Wikipage page ID	25354354 (xsd:integer)
Wikipage revision ID	950925296 (xsd:integer)
Link from a Wikipage to another Wikipage	Recursion Ackermann function Computability theory Natural number Raphael M. Robinson Rózsa Péter Primitive recursion Recursive function theory
sameAs	Double recursion Double recursion Double recursion Double recursion
dbp:wikiPageUsesTemplate	dbt:Reflist dbt:Mathlogic-stub
has 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)
gold:hypernym	Extension
prov:wasDerivedFrom	wikipedia-en:Double_recursion?oldid=950925296&ns=0
page length (characters) of wiki page	1763 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Double_recursion
is Link from a Wikipage to another Wikipage of	Primitive recursive function Ackermann function
is foaf:primaryTopic of	wikipedia-en:Double_recursion

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (61 GB total memory, 51 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software