HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Can every program be turned into a quine?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
canquineintoeveryprogramturned

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#23848, answer score: 5

Revisions (0)

No revisions yet.