The Recursion Theorem
The "recursion theorem" states, very approximately, and with several
assumptions (although they're all assumptions you'd be willing to make),
For every program P, there exists an ASCII character string encoding of a
program Q
(or any other
encoding, with analogous but changed assumptions)
such that the output of program Q, regardless of its input,
is equal to the output of
program P when supplied with input which is that ASCII character string
encoding of Q.
[back to problem session 13 index]
[list of problem session notes]
[main course page]