Problem Detail: 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?
Asked By : Raphael
Answered By : David Richerby
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 ignores its input and outputs a copy of itself.” 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 Mrangle$ 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)_{igeq 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/19667