1
$\begingroup$

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.

  • 6
    Crosspost: http://cstheory.stackexchange.com/q/8805/15462011-11-03

2 Answers 2

7

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.

  • 0
    The folks at CSTheory gave an answer similar to my example of Life: http://cstheory.stackexchange.com/questions/8805/if-an-abstract-machine-can-simulate-itself-does-that-make-it-turing-complete2011-11-03
0

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.