13
$\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?

Improve this question
$\endgroup$
5
  • $\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, 2015 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, 2017 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, 2017 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, 2017 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, 2017 at 14:02

1 Answer 1

Reset to default
14
$\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.

Improve this answer
$\endgroup$
9
  • 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$
    – user253751
    Sep 27, 2016 at 21:28
  • 2
    $\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, 2017 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, 2017 at 10:55
  • 2
    $\begingroup$ The answer now says "ignores its input and outputs a copy of its input" - you can't do both. $\endgroup$
    – user253751
    Mar 16, 2017 at 21:24
  • $\begingroup$ @immibis I'll come in again. $\endgroup$
    – David Richerby
    Mar 16, 2017 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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