Editing General recursive function (section)

== Normal form theorem ==

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(T)(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]]:
{{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 {{sfn|Minsky|1972|pp=189}}}}