Double recursion: Difference between revisions

Revision as of 14:54, 22 December 2013

Revision as of 14:59, 22 December 2013

Line 4:

* ''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''&nbsp;+&nbsp;1,&nbsp;''x''&nbsp;+&nbsp;1) is obtained by substitution from ''G''(''n''&nbsp;+&nbsp;1,&nbsp;''x''), the function ''G''(''n'',&nbsp;·) and given functions.<ref>{{cite journal | author=Raphael M. Robinson | title=Recursion and Double Recursion | journal=[[Bulletin of the American Mathematical Society]] | year=1948 | volume=54 | pages=987–93 | url=http://proprojecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.bams/1183512393&page=record | doi=10.1090/S0002-9904-1948-09121-2}}</ref>

Robinson goes on to provide a specific double recursive function (originally defined by [[Rózsa Péter]])

* ''G''(0,&nbsp;''x'') = ''x''&nbsp;+&nbsp;1

* ''G''(''n''&nbsp;+&nbsp;1,&nbsp;0) = ''G''(''n'',&nbsp;1)

* ''G''(''n''&nbsp;+&nbsp;1,&nbsp;''x''&nbsp;+&nbsp;1) = ''G''(''n'',&nbsp;''G''(''n''&nbsp;+&nbsp;1,&nbsp;''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]].

== See also ==

* [[Primitive recursion]]

* [[Ackermann function]]

== References ==

{{reflist}}