# Is any language that can express its own compiler Turing-complete?

A comment over on tex.SE made me wonder. The statement is essentially:

If I can write a compiler for language X in language X, then X is Turing-complete.

In computability and formal languages terms, this is:

If $M$ decides $L \subseteq L_{\mathrm{TM}}$ and $\langle M \rangle \in L$, then $F_L = \mathrm{RE}$.

Here $L_{\mathrm{TM}}$ denotes the language of all Turing machine encodings and $F_L$ denotes the set of functions computed by machines in $L$.

Is this true?

• close, think/ agree there must be some real thm close to this like, any "nontrivial" or "sufficiently complex" language that can express its own simulator is TM complete. a compiler is generally nec part of a simulator. it is indeed a "design pattern" found in many TM completeness proofs but maybe hasnt been generalized/ formalized. maybe a topic for further analysis/ discussion in Computer Science Chat. suspect/ conjecture there is some other interesting thm somewhat like "every nontrivial/ sufficiently complex recursive and recursively enumerable language can be mapped/ reduced to every other one".
– vzn
Apr 26 '15 at 15:48
• I created an esoteric language called InterpretMe, which can do nothing but express it's own interpreter, so it's certainly not Turing complete. Mar 16 '17 at 5:52
• Can you explain the second statement? What is $\langle M \rangle$? How is this statement related to the first? Mar 17 '17 at 13:26
• @reinierpost $\langle M \rangle$ typically denotes the number of $M$, given some (admissible) encoding. Hence, $L_{\mathrm{TM}} = \{ \langle M \rangle \mid M \text{ is a Turing machine}\}$. By $F_L$ I denote the set of functions computed by the language $L$ of Turing machines.
– Raphael
Mar 17 '17 at 13:59
• A better way to state the claim would be: "If there is a TM $M$ with $\langle M \rangle \in L$ and $L_M = L$, then $F_L = \mathrm{RE}$.
– Raphael
Mar 17 '17 at 14:02

The informal statement is not true, as shown by the following programming language. Any string of, say, ASCII characters is a valid program and the meaning of every program is, "Output a program that just outputs a copy of its input." Thus, every program in this language is a compiler for the language but the language is not Turing-complete.

I'm not sure if your "computability theory version" is equivalent but it is also not true. By Kleene's second recursion theorem, for any coding of Turing machines, there is a TM that accepts its own coding and rejects all others.1 This machine is a counterexample to the proposition. More concretely, we can achieve the result by choosing a coding. For example, let every odd number code the machine $M$ defined by "If my input is odd, accept it; otherwise, reject" and let the number $2x$ code the machine coded by $x$ in your own favourite coding scheme for Turing machines. $\langle M\rangle$ is in the language $L$ accepted by $M$ but $F_L$ is not Turing complete.

1 Kleene's second recursion theorem says that, for any enumeration $(\phi_i)_{i\geq 0}$ of the partial recursive functions (i.e., for any coding of programs as integers), and any partial recursive function $Q(x,y)$, there is an integer $p$ such that $\phi_p$ is the function that maps $y$ to $Q(p,y)$. So, in particular, let $Q$ be the function that accepts if $x=y$ and rejects otherwise. By the theorem, there is an integer $p$ that codes the program $\phi_p(y) = Q(p,y)$. That is, $\phi_p$ accepts its own coding $p$ and rejects all other inputs.

• In what sense is every program in that language a compiler for that language? Every program is a program that inputs a program in that language and outputs a different program in that language, yes, but quines are generally not considered to be compilers. Sep 27 '16 at 21:28
• I think @immibis has a point: your compiler $c$ is $c(P) = \{ x \Rightarrow \mathtt{return}\ P \}$ whereas all programs in the language are $P(x) = P$, so $c$ is clearly not in the language. Am I missing something?
– Raphael
Mar 16 '17 at 6:35
• @immibis I (belatedly) think you're right. It seems that what I meant to write was that the semantics of every program is just "output your input". That seems close enough to what I wrote that it was probably what I meant to say in the first place. Or maybe I was super-lucky that the edit-distance from my wrong answer to the correct answer was so small. :-) Mar 16 '17 at 10:55
• The answer now says "ignores its input and outputs a copy of its input" - you can't do both. Mar 16 '17 at 21:24
• @immibis I'll come in again. Mar 16 '17 at 21:34