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]