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?
Why doesn't this quine-less language contradict Kleene's recursion theorem?
fixed point
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$:The problem of simulating a $P$-program on an input $x$ is r.e.There is a computable transformation $f$ which, given a $P$-program, outputs an equivalent $U$-program.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.