12
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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". $\endgroup$ – vzn Apr 26 '15 at 15:48
  • 1
    $\begingroup$ I created an esoteric language called InterpretMe, which can do nothing but express it's own interpreter, so it's certainly not Turing complete. $\endgroup$ – Noncontextual Spelling Mar 16 '17 at 5:52
  • $\begingroup$ Can you explain the second statement? What is $\langle M \rangle$? How is this statement related to the first? $\endgroup$ – reinierpost Mar 17 '17 at 13:26
  • $\begingroup$ @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. $\endgroup$ – Raphael Mar 17 '17 at 13:59
  • $\begingroup$ 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}$. $\endgroup$ – Raphael Mar 17 '17 at 14:02
13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – immibis Sep 27 '16 at 21:28
  • 1
    $\begingroup$ 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? $\endgroup$ – Raphael Mar 16 '17 at 6:35
  • 1
    $\begingroup$ @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. :-) $\endgroup$ – David Richerby Mar 16 '17 at 10:55
  • 1
    $\begingroup$ The answer now says "ignores its input and outputs a copy of its input" - you can't do both. $\endgroup$ – immibis Mar 16 '17 at 21:24
  • $\begingroup$ @immibis I'll come in again. $\endgroup$ – David Richerby Mar 16 '17 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.