Kleene's recursion theorem: Difference between revisions

Revision as of 00:16, 16 March 2021

Revision as of 00:20, 16 March 2021

Line 65:

(eval (list Q p nil))

</syntaxhighlight>

=== Application to elimination of recursion ===

Suppose that <math>g</math> and <math>h</math> are total computable functions that are used in a recursive definition for a function <math>f</math>:

:<math>f(0,y) \simeq g(y),</math>

:<math>f(x+1,y) \simeq h(f(x,y),x,y),</math>

The second recursion theorem can be used to show that such equations define a computable function, where the notion of computability does not have to allow, prima facie, for recursive definitions (for example, it may be defined by [[M-recursive function|&mu;-recursion]], or by [[Turing machine]]s). This recursive definition can be converted into a computable function <math>\varphi_{F}(e,x,y)</math> that assumes <math>e</math> is an index to itself, to simulate recursion:

:<math>\varphi_{F}(e,0,y) \simeq g(y),</math>

:<math>\varphi_{F}(e,x+1,y) \simeq h(\varphi_e(x,y),x,y).</math>

The recursion theorem establishes the existence of a computable function <math>\varphi_f</math> such that <math>\varphi_f(x,y) \simeq \varphi_{F}(f,x,y)</math>. Thus <math>f</math> satisfies the given recursive definition.

=== Reflexive programming ===