General recursive function: Difference between revisions

Revision as of 14:44, 31 August 2021

Revision as of 06:48, 24 September 2021

Line 48:

The number ''e'' is called an '''index''' or '''Gödel number''' for the function ''f''.<ref>{{cite journal | doi=10.1090/S0002-9947-1943-0007371-8 | url=https://www.ams.org/journals/tran/1943-053-01/S0002-9947-1943-0007371-8/S0002-9947-1943-0007371-8.pdf | author=Stephen Cole Kleene | title=Recursive predicates and quantifiers | journal=Transactions of the American Mathematical Society | volume=53 | number=1 | pages=41&ndash;73 | date=Jan 1943 | doi-access=free }}</ref>{{rp|52–53}} A consequence of this result is that any μ-recursive function can be defined using a single instance of the μ operator applied to a (total) primitive recursive function.

[[Marvin Minsky (1967)|Minsky]] observes (as does Boolos-Burgess-Jeffrey (2002) pp.&nbsp;94–95) that the <math>U</math> defined above is in essence the μ-recursive equivalent of the [[universal Turing machine]]:

:{{blockquote |text=To construct U is to write down the definition of a general-recursive function U(n, x) that correctly interprets the number n and computes the appropriate function of x. to construct U directly would involve essentially the same amount of effort, ''and essentially the same ideas'', as we have invested in constructing the universal Turing machine. (italics in original, {{sfn|Minsky (|1967) p. |pp=189)}}}}

== Symbolism ==