# Is there any way to differentiate between “sort of” Turing-Complete and “really” Turing-Complete?

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"?

-
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