1
$\begingroup$

I read in Sipser's book that a machine can make copies of itself using a special function $q(w)$ which takes a string $w$ as input and prints out the string $w$.

A $TM$ $SELF$ can print out its own description $AB$ using two parts. For the first part $A$ prints out $<B>$ since it has the description for $B$ inside its finite control. For the second part, $B$ looks at the tape for its own description $<B>$, and uses $q$ to come up with $<A>$. Both descriptions are then concatenated to come up with $<AB>$.

I understand the proof above, but I couldn't get it yet why $SELF$ should have two parts. If its own description is writtten in its finite control, couldn't it just use $q$ to print out its own descrition?

$\endgroup$
  • $\begingroup$ This is how this specific proof works. There might be other proofs. Have you tried writing a proof along the lines you suggest? $\endgroup$ – Yuval Filmus Oct 2 '17 at 10:12
3
$\begingroup$

No, it can't.

Intuitively, $A$ can be described by print "B". Whatever $B$ is, there is such an $A$. Note that, by construction, $A$ is a program "longer" (roughly speaking) than $B$.

If we try to write $A$ as print "A", we incur in a problem, since $A$ should be "longer" than itself. Hence, such a definition is ill-posed.

For the same reason, you can't write a description of a TM inside its own finite control: you would need an infinite amount of states for that.


You can search the web for "quines": programs printing their own source code. Virtually all of them have to workaround the fact that they can't include their own source code in themselves, and have finite length. Hence, they must exploit something analogous to the $q()$ function you mention.

A typical quine can be designed as follows. Start from a clumsy attempt:

myself=""
print myself

Obvious partial fix: copy its source code within myself

myself="myself=\"\" \n print myself "
print myself

Not yet there: we should replicate the source code inside the innermost quotes, and so on, infinitely many times. Not good.

Instead, we use a placeholder for that "infinite" replication, which we replace at runtime with the whole code.

myself="myself=\"PH\" \n print myself "
print replace(myself, "PH", myself)

Obvious fix

myself="myself=\"PH\" \n print replace(myself, \"PH\", myself)"
print replace(myself, "PH", myself)

Assuming that replace only replaces the first occurrence of the placeholder PH, and that we fix the whitespace precisely in myself, this is now a program printing itself -- a quine.

Note how the replacement of PH must be done at runtime. Similarly, in the Sipser proof, we must compute q() at runtime -- we can't encode that in the finite control.

$\endgroup$
  • $\begingroup$ Great answer (as always). I think I get it now, in the example above,, relating it to the Sipser proof, $B$ is analogously: $B=\text{"myself=\"PH\" \n print replace(myself, \"PH\", myself)"}$, and this is fed to the 'replace' function which does exactly the same thing as $q$, to come up with $A$ and then $AB$, (or the entire program : if the 1st placeholder is replaced) $\endgroup$ – Link L Oct 3 '17 at 1:49

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.