4
$\begingroup$

Given a program $P$ which takes a binary string as input, can one always (effectively) construct a program $P'$ such that $P'(0x)$ runs $P(x)$ and $P'(1x)$ outputs the source code of $P'$? I didn't find anything with some googling, but it seems like the kind of thing that could be known.

$\endgroup$
5
$\begingroup$

You are looking for the recursion theorem. Let $F(e)$ be the function that on input $0x$ returns $P(x)$ and on input $1x$ returns $e$. A fixed point $\varphi_e = \varphi_{F(e)}$ is what you're looking for.

If you're interested in how this quine is constructed, take a look at the proof, for example here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.