General recursive function: Difference between revisions

Revision as of 10:00, 13 November 2021

Revision as of 10:01, 13 November 2021

Line 55:

A [[Kleene's T predicate#Normal form theorem|normal form theorem]] due to Kleene says that for each ''k'' there are primitive recursive functions <math>U(y)\!</math> and <math>T(y,e,x_1,\ldots,x_k)\!</math> such that for any μ-recursive function <math>f(x_1,\ldots,x_k)\!</math> with ''k'' free variables there is an ''e'' such that

:<math>f(x_1,\ldots,x_k) \simeq U(\mu y\, T(y,e,x_1,\ldots,x_k))</math>.

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|Minsky]] observes the <math>U</math> defined above is in essence the μ-recursive equivalent of the [[universal Turing machine]]: