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 : el.dbpedia.org associated with source document(s)

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)
rdfs:comment	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)
sameAs	Double recursion
dbp:wikiPageUsesTemplate	dbt:Reflist dbt:Mathlogic-stub
Subject	Computability theory Recursion
gold:hypernym	Extension
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Double_recursion?oldid=950925296&ns=0
Wikipage page ID	25354354 (xsd:integer)
page length (characters) of wiki page	1763 (xsd:nonNegativeInteger)
Wikipage revision ID	950925296 (xsd:integer)
Link from a Wikipage to another Wikipage	Ackermann function Computability theory Recursion General recursive function Primitive recursive function Rózsa Péter History of numbers Raphael M. Robinson
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)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Double_recursion
is Link from a Wikipage to another Wikipage of	Ackermann function
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Double_recursion

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (71 GB total memory, 2 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software