0
$\begingroup$

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

$\endgroup$
11
  • 7
    $\begingroup$ 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. $\endgroup$ Jan 20, 2011 at 4:15
  • 2
    $\begingroup$ 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" $\endgroup$
    – Elliot JJ
    Jan 20, 2011 at 4:21
  • 4
    $\begingroup$ (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? $\endgroup$ Jan 20, 2011 at 5:46
  • 3
    $\begingroup$ 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. $\endgroup$ Jan 21, 2011 at 10:51
  • 2
    $\begingroup$ 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. $\endgroup$ Jan 23, 2011 at 5:53

2 Answers 2

16
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

There already is a distinction, between "weak" turing complete systems, and "strong" turing complete systems. Legoes would fall under being "weakly" turing complete, and rule 101 as well. Interestingly, C is likely "weakly" turing complete as well.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.