Question

Give an example in the spirit of the recursion theorem of a program in a real programming language (or a reasonable approximation thereof) that prints itself out.

Short answer

Example of Recursive Equation: $r\left(w\right)=t\left(\left(R\right).w\right)$

Step-by-step solution

Introduction Recursion

Recursion is the phenomena where a particular function repeatedly calls itself until reach to base condition (terminating point).

Defining Recurrence relation

First let us assume two Turing Machine T and R such that:

• T compute a function $t:\sum _{}^{*}\times \sum _{}^{*}\to \sum _{}^{*}$
• R compute a function $t:\sum _{}^{*}\to \sum _{}^{*}$

We will create TM R based on T :

For every string w ,

$r\left(w\right)=t\left(\left(R\right).w\right)$

So, we our recursion program will have to work like:

$SELF=onanyinput$

• Obtain own description through recursion theorem
• Print

Writing LISP Program

Use LISP programming language which is compatible for recursion theorem.

Following LISP program is in spirit of recursion:

$\left(defineSELF\left(lambda\left(w\right)\right)\right)$

$\left(listw\left(list\left(quotequote\right)w\right)\right)$

)

(quote(lambda(w)

(list w(quote quote)w)

))