20
$\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.

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ 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"? $\endgroup$
    – Andrej Bauer
    Nov 3, 2011 at 21:16
  • 4
    $\begingroup$ 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)? $\endgroup$
    – Jukka Suomela
    Nov 3, 2011 at 21:58
  • 5
    $\begingroup$ Crosspost: math.stackexchange.com/q/78734/3330 $\endgroup$
    – Raphael
    Nov 3, 2011 at 22:08
  • 1
    $\begingroup$ Bean, simultaneous cross-posting is strongly discouraged on cstheory, please see the poilicy. ps: I am not sure if this question is on-topic on cstheory, please also check the FAQ to understand the scope of cstheory. $\endgroup$
    – Kaveh
    Nov 4, 2011 at 0:42
  • 5
    $\begingroup$ The "do nothing" machine can simulate itself. $\endgroup$
    – Max
    Nov 4, 2011 at 18:56

3 Answers 3

Reset to default
24
$\begingroup$

Not necessarily. For instance, the two-dimensional 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 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ What if the machine has some measure of complexity? I guess that would have to be unrelated to Turing-completeness... $\endgroup$
    – Jeremy Kun
    Nov 3, 2011 at 21:48
  • 4
    $\begingroup$ 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. $\endgroup$
    – Jeremy Kun
    Nov 3, 2011 at 21:49
  • 9
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Nov 4, 2011 at 1:24
25
$\begingroup$

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. 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. 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, 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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Aaron Sterling
    Nov 4, 2011 at 14:40
  • $\begingroup$ I'm more interested in (2): how powerful is this set theory? Is it related to Quinian "new foundations"? $\endgroup$
    – cody
    Nov 4, 2011 at 16:52
  • $\begingroup$ @Neel - Interesting answer. I would also like the same thing like Aaron - could you suggest some good starting point for (1). Thanks $\endgroup$
    – Akash Kumar
    Nov 8, 2011 at 17:42
9
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – r.e.s.
    Nov 8, 2011 at 4:52
  • $\begingroup$ I gave a similar answer for the cross post on Math.SE which received no up-votes. :) $\endgroup$
    – Kaveh
    Nov 12, 2011 at 17:30
  • $\begingroup$ @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. $\endgroup$
    – r.e.s.
    Nov 26, 2011 at 4:29
  • $\begingroup$ @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.) $\endgroup$
    – Kaveh
    Nov 26, 2011 at 6:37

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.