|
(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|μ-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 ===
|
