Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Some things, like the computer language C, turing machines, lambda calculus, etc. seem to be "naturally" Turing-Complete. That is, they're just Turing-Complete from the bottom up.

On the other hand, cellular automata, many relatively simple Newtonian physics simulations and even Legoes, are also Turing Complete. This seems, somehow, just wrong, yet reductions are so common in TCS, how can we fault the reduction of Lego-brand blocks (and motor) to a Turing Machine by literally building a Turing Machine?

Is there any non-arbitrary way to say when the reduction required of a system is just too weird to consider it "non-ridiculously-Turing-Complete"?

share|improve this question
vote to close: not sure what the question really is trying to get at. Elliot, "too weird" is a subjective statement, as is "non-ridiculously" - I'm not sure what you're looking for. –  Suresh Venkat Jan 20 '11 at 4:15
Essentially any distinction between Turing-Complete languages is all I'm looking. Non-ridiculously is deliberately left vague exactly because I don't know what the distinction is. However, the actual answer might be along the lines "a Turing-Complete language for which all NP-Complete problems can be answered but only in exponential time" –  Elliot Jans Jan 20 '11 at 4:21
(Vote to close) While I think "modeling" is a proper TCS role, in the sense of taking vague/abstract concepts and giving them rigor/precision, I agree with @Suresh that this question lacks sufficient direction... @Elliot, knowing how to distinguish what a right answer would look like from what a wrong answer looks like is an important characteristic for all good questions (and is the piece it seems you're missing). Perhaps you could think about this some and re-ask this question with a little more focus? –  Daniel Apon Jan 20 '11 at 5:46
Are you thinking of Matthew Cook's first proof showing Wolfram's rule 110 is Turing complete? Since then, there has been a proof showing Rule 110 is more naturally Turing complete. I don't know if there are any relatively natural systems which are Turing complete but which don't have efficient reductions. I don't even know whether people have come up with contrived systems which provably have this property. –  Peter Shor Jan 21 '11 at 10:51
It seems that you are conflating a computational model and its implementation. "Legos" is not a model of computation, but Legos can be used to implement a machine. The rules describing the evolution of an abstract physical system is a model of computation: the system itself is an implementation. –  Mark Reitblatt Jan 23 '11 at 5:53

1 Answer 1

up vote 15 down vote accepted

Ridiculous-seeming things can be (and often are) true. The fact that you find them ridiculous indicates that there is a mismatch between your intuition and reality. The fix for this is not to define a "ridiculousness" metric, but is instead to fix your intuition.

However, one can define an "efficiency of simulation" metric - if the simulation technique causes a more-than-constant slowdown, then it's not as efficient, and that may be kind of like what you are looking for. Regrettably for your purposes, the Lego and Newtonian physics examples exhibit only a constant-factor slowdown. Reality simply is that strange, and computational systems really are that pervasive.

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