Kleene's recursion theorem: Difference between revisions

Revision as of 18:02, 11 May 2020

Revision as of 21:33, 30 May 2020

Line 71:

:<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, aprima priorifacie, 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>