Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For instance, in programming languages it's common to write an X-in-X compiler/interpreter, but on a more general level many known Turing-complete systems can simulate themselves in impressive ways (e.g. simulating Conway's Game of Life in Conway's Game of Life).

So my question is: is a system being able to simulate itself sufficient to prove it's Turing complete? It certainly is a necessary condition.

share|cite|improve this question
Certainly the empty machine simulates itself perfectly. More generally I am not really sure how to give a precise definition of "simulates itself" that doesn't trivially imply that every machine is constantly simulating itself all the time. – Qiaochu Yuan Nov 3 '11 at 21:19
"E.g." is not something I would expect to find in a "rigorous definition" of anything. – Henning Makholm Nov 3 '11 at 21:38
I'm asking this question here because I don't know the rigorous definitions of these sorts of things... I've seen explicit instances of common abstract machines which can simulate their own state and transition rules. I don't know what that means as a definition (heck I've never even heard of the definition of an "abstract machine" in general, just definitions for specific machines), but I want to know if it implies Turing-completeness. – JeremyKun Nov 3 '11 at 21:42
Well all the time we abstract the idea of encoding a Turing machine by just saying <T> is the encoding of a Turing machine suitable as an input to a Turing machine. We can't do that for other machines? Let <L,s> be a Life-encoding of a game of Life with an initial state... I'm sure there's more work behind encodings of Turing machines, but the same ideas don't apply? – JeremyKun Nov 3 '11 at 21:51
Crosspost: – Raphael Nov 3 '11 at 22:09
up vote 6 down vote accepted

Here is a counterexample. At least I hope you'll agree that it's a counterexample.

Consider the small programming language $L$ with the following grammar: $$\sigma ::= \text{x} \mid (\text{car } \sigma) \mid (\text{cdr } \sigma) \mid (\text{eval } \sigma)$$ The language has a single variable "$\text{x}$" whose value is always the input to the program, which is a lisp-like data item. The "car" and "cdr" functions work as usual. The "eval" function takes one argument, which must be a cons cell. It interprets the car of that cons cell as an $L$ program and runs it recursively with the cdr as input. Then it returns the result. If the operand to either of the three primitives is an atom, the same atom is returned unchanged.

There are at least two meaningful, observationally different $L$ programs, namely $(\text{car x})$ and $(\text{cdr x})$. So the language is simple but not completely degenerate -- meaning that the output depends on the input in a way that the program influences.

It is simple to show that $L$ programs always terminate, by induction on the sum of the sizes of the program and the input. Therefore $L$ is not Turing-complete. On the other hand, the program $(\text{eval x})$ is an universal $L$ program. It takes an input the combination of another $L$ program and its input, and computes what the other $L$ program does. Thus, $L$ satisfies your premise but not your conclusion.

Do you think this is cheating? Perhaps because I defined the semantics in terms of an explicit eval function? That was just for ease of presentation; I could also have given a completely syntactic formal semantics for $L$ where it just happened that some input constructions behaved like an universal program. If that is cheating, then it is difficult to see what an appropriate formal condition for not cheating would be.

share|cite|improve this answer
The folks at CSTheory gave an answer similar to my example of Life:… – JeremyKun Nov 3 '11 at 22:45

A machine model having a universal machine does not imply that the machine model is TM complete. The trivial example is take the machine model that can only compute the function 0. Even if you add conditions that the model can compute some tasks (e.g. polynomial time computable functions), existence of a universal machine in the class does not imply the model is TM complete.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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