2
$\begingroup$

Kleene's recursion theorem implies that every Turing complete programming language that satisfies certain properties have quines. This website claims that this is incorrect, and that there is a Turing complete without a quine.

I give a slightly simplified version of what they gave. Start with a Turing complete programming language $P$. Create a programming language $P'$ that is interpreted according to the following rules:

  • Try running the program according to the rules for $P$
  • If the input was empty, and if it outputs it own source code and then would terminate according to the rules of $P$, throw an error instead. We'll call this error a "quine error".

For example, $Python'$ is like $Python$, except that when given no input, if the program outputs its own source, it will throw a quine error instead of terminating normally.

What is the resolution to this apparent paradox?

$\endgroup$
3
$\begingroup$

The recursion theorem only applies to admissible programming languages. A programming language $P$ is admissible if it satisfies the following three properties, with respect to some reference programming language $U$:

  1. The problem of simulating a $P$-program on an input $x$ is r.e.

  2. There is a computable transformation $f$ which, given a $P$-program, outputs an equivalent $U$-program.

  3. There is a computable transformation $g$ which, given a $U$-program, outputs an equivalent $P$-program.

In your case the first two properties hold, so the third must fail. You can try to implement $g$ by "compiling" a $U$-program to a $P$-program, but this compilation would fail if the resulting program attempts to print its own source code. The recursion theorem shows that there is no way around this problem.

$\endgroup$
  • $\begingroup$ Why does 2 hold? $\endgroup$ – Ariel Jun 1 '17 at 16:50
  • 1
    $\begingroup$ Since we can simulate $P$ (or rather $P'$) in the universal language. We simulate the program as usual, and then we compare the output (if the program terminates) to the source code. If they match, we follow the rules of $P'$. This doesn't require solving the halting problem. $\endgroup$ – Yuval Filmus Jun 1 '17 at 16:59
  • $\begingroup$ Oh, you're obviously right, great answer! $\endgroup$ – Ariel Jun 1 '17 at 17:04

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.