Double recursion: Difference between revisions

Revision as of 01:40, 8 December 2009

Revision as of 18:43, 9 December 2009

Line 1:

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''&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://projecteuclid.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]].