Kleene's recursion theorem: Difference between revisions

Revision as of 06:36, 7 May 2020

Revision as of 18:02, 11 May 2020

Line 48:

<code>Q</code> can be changed to any two-argument function.

<sourcesyntaxhighlight lang="lisp">

(setq Q '(lambda (x y) x))

(setq s11 '(lambda (f x) (list 'lambda '(y) (list f x 'y))))

(setq n (list 'lambda '(x y) (list Q (list s11 'x 'x) 'y)))

(setq p (eval (list s11 n n)))

</syntaxhighlight>

</source>

The results of the following expressions should be the same. <math>\varphi</math> <code>p(nil)</code>

<sourcesyntaxhighlight lang="lisp">

(eval (list p nil))

</syntaxhighlight>

</source>

<code>Q(p, nil)</code>

<sourcesyntaxhighlight lang="lisp">

(eval (list Q p nil))

</syntaxhighlight>

</source>

=== Application to elimination of recursion ===