# 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. – Noncontextual Spelling 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? – reinierpost 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

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.
• 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