0

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

Hsien-Chih Chang 張顯之
  • 7,638
  • 4
  • 44
  • 83
Elliot JJ
  • 745
  • 2
  • 8
  • 12
  • 7
    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 04:15
  • 2
    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 JJ Jan 20 '11 at 04:21
  • 1
    I see. Do note though that since no one has (yet) broken the "effective" CT hypothesis, you're unlikely to find that any of the Turing-complete models can solve an NP-complete problem in P time, or take provably exponential time. – Suresh Venkat Jan 20 '11 at 04:53
  • 4
    (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 05:46
  • 3
    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
  • 1
    Guys, you are being a bit too stuffy. The guy didn't pose the question well, but we know what he means. Say, since typically you prove that a computation system is turing-complete by having it simulate a turing machine, he's asking to keep the complexity of the simulation low (low constant factor if you want O() complexity) or low Cyclomatic complexity or low character entropy. Take your pick. Say he asks for all the turing complete systems with Cyclomatic complexity M. – Dr G Jan 21 '11 at 20:20
  • @Peter: Do you have a reference for the Rule-110 result? – Jeffε Jan 21 '11 at 21:25
  • Wikipedia has a bunch of references, including Cook's first proof. – Peter Shor Jan 22 '11 at 01:56
  • 2
    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 05:53
  • jeffE-- I cited martinez et al here which is the latest simplification of rule 110 TM completeness Ive heard of and maybe what PS is alluding to – vzn Jun 27 '12 at 14:59
  • think there is a reasonable question in here if its rewritten as EJ writes in the comment above. "are there different kinds of Turing completeness". at the minimum there are different efficiencies of translation, possibly still within the effective CT thesis as SV writes. however efficiency of TM completeness translations is not studied so much because its more a study of "whether" something is computable rather than "how efficiently". rule 110 however is a good example/case study in the literature where both computability and efficiency are being actively researched somewhat in parallel. – vzn Jun 27 '12 at 15:03

2 Answers2

16

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.

Peter Boothe
  • 1,791
  • 13
  • 17
0

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.

Andrew Rashenda
  • 1
  • 1
    C is not Turing-complete at all. See https://cstheory.stackexchange.com/questions/2547/maximum-computational-power-of-a-c-implementation . Anyway, your question does not have much meaning if you don’t define what you mean by “weak” and “strong” Turing completeness. – Emil Jeřábek May 19 '20 at 07:26