patternModerate
Is any language that can express its own compiler Turing-complete?
Viewed 0 times
canexpressanylanguageitsownthatcompletecompilerturing
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#19667, answer score: 14
Revisions (0)
No revisions yet.