<p>No, it's not. I know two major classes of techniques for avoiding inconsistency/Turing completeness.</p>

<ol>
<li><p>The first line of attack is to set up the system so that syntax can be arithmetized, but Godel's fixed point theorem doesn't go through. Dan Willard has worked extensively on this and given consistent self-verifying logical systems. The trick is to eliminate the multiplication and addition function symbols, and replace them with divisibility and subtraction. This gives you enough horsepower to represent syntax arithmetically, but the fixed point theorem doesn't go through since multiplication is not provably total. </p>

<p>See Dan Willard. <a href="http://www.cs.albany.edu/~dew/m/jsl1.pdf">Self-Verifying Axiom Systems, the Incompleteness Theorem and Related Reflection Principles</a>. Journal of Symbolic Logic 66 (2001) pp. 536-596. </p></li>
<li><p>The second line of attack allows more use of fixed points, but to set things up so that syntax doesn't arithmetize. The prettiest systems for this are (IMO) based on variants of linear logic. For example, in Kazushige Terui's Light Affine Set Theory, even the full <em>unrestricted</em> set comprehension principle is sound, but since the ambient logic of the set theory is linear (and hence contraction is not allowed), Russell's paradox is not derivable. </p>

<p>The intuitive reason that arithmetization fails is that the light linear function space $A \multimap B$ is set up so that all its inhabitants are polynomial time. As a result, the light linear version of the Peano axioms can't prove exponentiation total (since exponentiation of unary numbers takes exponential time), and so there is no longer an isomorphism between the natural numbers and bit strings. </p>

<p>Kazushige Terui. <a href="http://www.kurims.kyoto-u.ac.jp/~terui/lastfin.pdf">Light affine set theory: A naive set theory of polynomial time.</a> Studia Logica, Vol. 77, No. 1, pp. 9-40, 2004.</p>

<p>I think this paper is more accessible after reading the following paper of Yves Lafont:</p>

<p>Y. Lafont, <a href="http://iml.univ-mrs.fr/~lafont/pub/soft.ps">Soft Linear Logic and Polynomial Time</a>, Theoretical Computer Science 318 (special issue on Implicit Computational Complexity) p. 163-180, Elsevier (2004)</p>

<p>Terui's set theory is very expressive, but it's hard to compare with traditional set theories, since proof-theoretic ordinals are not a good tool for comparing very weak systems. For example, Terui's set theory obviously cannot prove exponentiation total, and hence its proof-theoretic strength cannot even reach up to $\omega$. Complexity classes are probably better -- it is complete for polytime (it can prove every polytime function total, but no more). </p>

<p>I tend to think of these kinds of systems as proofs-of-concept for the idea that complexity theory can serve as a foundation for certain kinds of ultrafinitism.</p></li>
</ol>

CC BY-SA 3.0
2011-11-04T14:40:11.247Z
I find your answer fascinating, @Neel.  Could you please suggest a good starting point for me to read about either (1) or (2)?  I am slightly more interested in learning about (1), if that matters.
Aaron Sterling
CC BY-SA 3.0
2011-11-04T16:52:19.320Z
I'm more interested in (2): how powerful is this set theory? Is it related to Quinian "new foundations"?
cody
CC BY-SA 3.0
2011-11-08T17:42:27.783Z
@Neel - Interesting answer. I would also like the same thing like Aaron - could you suggest some good starting point for (1). Thanks
Akash Kumar
CC BY-SA 3.0
2011-11-04T06:55:04.397Z
2011-11-07T11:31:08.593Z
2011-11-07T11:31:08.593Z
Neel Krishnaswami
<p>Consider the following machine model. The machine with code $i$, upon input $x$, outputs $0$ always.</p>

<p>Note that any machine $M$ in this model is universal, as $M(\langle \ulcorner M&#39; \urcorner, x \rangle ) = M&#39;(x) = 0$ for all $M&#39;, x$.</p>

<p>This is clearly not Turing complete but also clearly has universal machines.</p>

CC BY-SA 3.0
2011-11-08T04:52:44.613Z
Of course $0$ plays no special role here, and can be replaced by any nonnegative integer. That is, every TM in the set of TMs that compute a given *constant* function, is universal for that set --even though that set of TMs is not Turing complete.
r.e.s.
CC BY-SA 3.0
2011-11-12T17:30:58.587Z
I gave [a similar answer for the cross post on Math.SE](http://math.stackexchange.com/questions/78734/is-an-abstract-machine-turing-complete-if-it-can-simulate-itself/78795#78795) which received no up-votes. :)
Kaveh
CC BY-SA 3.0
2011-11-26T04:29:22.523Z
@Kaveh: Ironically, it seems I misjudged this answer as being prior to yours, and so upvoted, edited & commented only here. Crossposts can be such a pain.
r.e.s.
CC BY-SA 3.0
2011-11-26T06:37:14.527Z
@r.e.s., I think the level of sites create different voting patterns. On math.se even very good answer by other high rep user here don't get that much up-voted, so I find it normal. :) (Also my answer is not as clear and understandable as David's answer here.)
Kaveh
CC BY-SA 3.0
2011-11-04T14:32:05.920Z
2011-11-07T16:20:14.337Z
2011-11-07T16:20:14.337Z
David Harris
<p>Not necessarily. For instance, the two-dimensional <a href="http://en.wikipedia.org/wiki/Block_cellular_automaton">block cellular automaton</a> with two states, in which a cell becomes live only when its four predecessors have exactly two adjacent live cells, can simulate itself with a factor of two slowdown and a factor of two size blowup, but is not known to be Turing complete. See <a href="http://dx.doi.org/10.1007/978-1-84996-217-9_7">The B36/S125 “2x2” Life-Like Cellular Automaton</a>
by Nathaniel Johnston for more on this block automaton and on the B36/S125 rule for the Moore neighborhood which is also capable of simulating this block automaton.</p>

CC BY-SA 3.0
2011-11-03T21:48:23.927Z
What if the machine has some measure of complexity? I guess that would have to be unrelated to Turing-completeness...
Jeremy Kun
CC BY-SA 3.0
2011-11-03T21:49:45.837Z
But then again, the block automaton you mentioned could still be Turing complete. You're just saying the implication isn't known to be true. Not that this represents a counterexample.
Jeremy Kun
CC BY-SA 3.0
2011-11-04T01:24:44.267Z
If one considers only block automaton states with a finite number of live cells, then with this restriction it is still the case that it can simulate itself in the same way. But the restricted automaton is certainly not Turing complete, because no pattern can escape its bounding diamond, so every pattern's fate can be determined in only exponential time.
David Eppstein
CC BY-SA 3.0
2011-11-03T21:36:47.220Z
2011-11-03T21:36:47.220Z
David Eppstein
<p>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).</p>

<p>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.</p>

CC BY-SA 3.0
2011-11-03T21:16:02.693Z
Before I attempt to answer, can you be a bit more specific what you mean by "a logical system can simulate itself"? Do you mean something like "can encode its own syntax and provability"?
Andrej Bauer
CC BY-SA 3.0
2011-11-03T21:17:31.930Z
I think "logical system" was the wrong choice of words. I mean something like an automata, but I don't want to restrict it to automata, but rather abstract machines. Updated in the original post.
Jeremy Kun
CC BY-SA 3.0
2011-11-03T21:58:13.753Z
Precisely what do you mean by a "simulation"? In particular, how do you define simulation so that it still makes sense, e.g., in the context of Game of Life, but does not make the question entirely trivial (e.g., a machine that does nothing simulates a machine that does nothing)?
Jukka Suomela
CC BY-SA 3.0
2011-11-03T22:08:47.840Z
Crosspost: http://math.stackexchange.com/q/78734/3330
Raphael
CC BY-SA 3.0
2011-11-04T00:42:21.593Z
Bean, simultaneous cross-posting is strongly discouraged on cstheory, please see the [poilicy](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231). ps: I am not sure if this question is on-topic on cstheory, please also check the FAQ to understand the scope of cstheory.
Kaveh
CC BY-SA 3.0
2011-11-04T18:56:59.407Z
The "do nothing" machine can simulate itself.
Max
<computability><automata-theory><turing-machines>
If an abstract machine can simulate itself, does that make it Turing complete?
Jeremy Kun
# If an abstract machine can simulate itself, does that make it Turing complete?

(Asked by: username_0 on 2011-11-03)

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.

**Tags:** computability, automata-theory, turing-machines
> **Comments:**
> **username_1**: Before I attempt to answer, can you be a bit more specific what you mean by "a logical system can simulate itself"? Do you mean something like "can encode its own syntax and provability"?  
> **username_0**: I think "logical system" was the wrong choice of words. I mean something like an automata, but I don't want to restrict it to automata, but rather abstract machines. Updated in the original post.  
> **username_2**: Precisely what do you mean by a "simulation"? In particular, how do you define simulation so that it still makes sense, e.g., in the context of Game of Life, but does not make the question entirely trivial (e.g., a machine that does nothing simulates a machine that does nothing)?  
> **username_3**: Crosspost: http://math.stackexchange.com/q/78734/3330  
> **username_4**: Bean, simultaneous cross-posting is strongly discouraged on cstheory, please see the [poilicy](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231). ps: I am not sure if this question is on-topic on cstheory, please also check the FAQ to understand the scope of cstheory.  
> **username_5**: The "do nothing" machine can simulate itself.  

---

## 3 answers

### Answer by username_12 on 2011-11-03. Score: 25 | Accepted answer

Not necessarily. For instance, the two-dimensional [block cellular automaton](http://en.wikipedia.org/wiki/Block_cellular_automaton) with two states, in which a cell becomes live only when its four predecessors have exactly two adjacent live cells, can simulate itself with a factor of two slowdown and a factor of two size blowup, but is not known to be Turing complete. See [The B36/S125 “2x2” Life-Like Cellular Automaton](http://dx.doi.org/10.1007/978-1-84996-217-9_7)
by Nathaniel Johnston for more on this block automaton and on the B36/S125 rule for the Moore neighborhood which is also capable of simulating this block automaton.

> **Comments:**
> **username_0**: What if the machine has some measure of complexity? I guess that would have to be unrelated to Turing-completeness...  
> **username_0**: But then again, the block automaton you mentioned could still be Turing complete. You're just saying the implication isn't known to be true. Not that this represents a counterexample.  
> **username_12**: If one considers only block automaton states with a finite number of live cells, then with this restriction it is still the case that it can simulate itself in the same way. But the restricted automaton is certainly not Turing complete, because no pattern can escape its bounding diamond, so every pattern's fate can be determined in only exponential time.  

---

### Answer by username_6 on 2011-11-04. Score: 26

No, it's not. I know two major classes of techniques for avoiding inconsistency/Turing completeness.

1. The first line of attack is to set up the system so that syntax can be arithmetized, but Godel's fixed point theorem doesn't go through. Dan Willard has worked extensively on this and given consistent self-verifying logical systems. The trick is to eliminate the multiplication and addition function symbols, and replace them with divisibility and subtraction. This gives you enough horsepower to represent syntax arithmetically, but the fixed point theorem doesn't go through since multiplication is not provably total.

   See Dan Willard. [Self-Verifying Axiom Systems, the Incompleteness Theorem and Related Reflection Principles](http://www.cs.albany.edu/~dew/m/jsl1.pdf). Journal of Symbolic Logic 66 (2001) pp. 536-596.
2. The second line of attack allows more use of fixed points, but to set things up so that syntax doesn't arithmetize. The prettiest systems for this are (IMO) based on variants of linear logic. For example, in Kazushige Terui's Light Affine Set Theory, even the full *unrestricted* set comprehension principle is sound, but since the ambient logic of the set theory is linear (and hence contraction is not allowed), Russell's paradox is not derivable.

   The intuitive reason that arithmetization fails is that the light linear function space $A \multimap B$ is set up so that all its inhabitants are polynomial time. As a result, the light linear version of the Peano axioms can't prove exponentiation total (since exponentiation of unary numbers takes exponential time), and so there is no longer an isomorphism between the natural numbers and bit strings.

   Kazushige Terui. [Light affine set theory: A naive set theory of polynomial time.](http://www.kurims.kyoto-u.ac.jp/~terui/lastfin.pdf) Studia Logica, Vol. 77, No. 1, pp. 9-40, 2004.

   I think this paper is more accessible after reading the following paper of Yves Lafont:

   Y. Lafont, [Soft Linear Logic and Polynomial Time](http://iml.univ-mrs.fr/~lafont/pub/soft.ps), Theoretical Computer Science 318 (special issue on Implicit Computational Complexity) p. 163-180, Elsevier (2004)

   Terui's set theory is very expressive, but it's hard to compare with traditional set theories, since proof-theoretic ordinals are not a good tool for comparing very weak systems. For example, Terui's set theory obviously cannot prove exponentiation total, and hence its proof-theoretic strength cannot even reach up to $\omega$. Complexity classes are probably better -- it is complete for polytime (it can prove every polytime function total, but no more).

   I tend to think of these kinds of systems as proofs-of-concept for the idea that complexity theory can serve as a foundation for certain kinds of ultrafinitism.

> **Comments:**
> **username_7**: I find your answer fascinating, @Neel.  Could you please suggest a good starting point for me to read about either (1) or (2)?  I am slightly more interested in learning about (1), if that matters.  
> **username_8**: I'm more interested in (2): how powerful is this set theory? Is it related to Quinian "new foundations"?  
> **username_9**: @Neel - Interesting answer. I would also like the same thing like Aaron - could you suggest some good starting point for (1). Thanks  

---

### Answer by username_10 on 2011-11-04. Score: 10

Consider the following machine model. The machine with code $i$, upon input $x$, outputs $0$ always.

Note that any machine $M$ in this model is universal, as $M(\langle \ulcorner M' \urcorner, x \rangle ) = M'(x) = 0$ for all $M', x$.

This is clearly not Turing complete but also clearly has universal machines.

> **Comments:**
> **username_11**: Of course $0$ plays no special role here, and can be replaced by any nonnegative integer. That is, every TM in the set of TMs that compute a given *constant* function, is universal for that set --even though that set of TMs is not Turing complete.  
> **username_4**: I gave [a similar answer for the cross post on Math.SE](http://math.stackexchange.com/questions/78734/is-an-abstract-machine-turing-complete-if-it-can-simulate-itself/78795#78795) which received no up-votes. :)  
> **username_11**: @Kaveh: Ironically, it seems I misjudged this answer as being prior to yours, and so upvoted, edited & commented only here. Crossposts can be such a pain.  
> **username_4**: @r.e.s., I think the level of sites create different voting patterns. On math.se even very good answer by other high rep user here don't get that much up-voted, so I find it normal. :) (Also my answer is not as clear and understandable as David's answer here.)  

---

