<p>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.</p>

CC BY-SA 4.0
2020-05-19T07:26:41.487Z
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
CC BY-SA 4.0
2020-05-19T02:55:30.250Z
2020-05-19T02:55:30.250Z
Andrew Rashenda
<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-01-23T04:27:36.127Z
2011-01-23T04:27:36.127Z
Peter Boothe
<p>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.</p>

<p>On the other hand, cellular automata, many relatively simple Newtonian physics simulations and even <a href="http://www.youtube.com/watch?v=cYw2ewoO6c4" rel="nofollow">Legoes</a>, 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?</p>

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

CC BY-SA 3.0
2012-06-27T14:59:01.750Z
jeffE-- I cited martinez et al [here](http://cstheory.stackexchange.com/a/11661/7884) which is the latest simplification of rule 110 TM completeness Ive heard of and maybe what PS is alluding to
vzn
CC BY-SA 3.0
2012-06-27T15:03:31.243Z
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
CC BY-SA 2.5
2011-01-20T04:15:08.180Z
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
CC BY-SA 2.5
2011-01-20T04:21:23.927Z
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
CC BY-SA 2.5
2011-01-20T04:53:48.210Z
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
CC BY-SA 2.5
2011-01-20T05:46:15.850Z
(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
CC BY-SA 2.5
2011-01-21T10:51:00.050Z
Are you thinking of Matthew Cook's first proof showing [Wolfram's rule 110](http://en.wikipedia.org/wiki/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 
CC BY-SA 2.5
2011-01-21T20:20:54.587Z
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
CC BY-SA 2.5
2011-01-21T21:25:17.283Z
@Peter: Do you have a reference for the Rule-110 result?
Jeffε
CC BY-SA 2.5
2011-01-22T01:56:53.053Z
[Wikipedia](http://en.wikipedia.org/wiki/Rule_110) has a bunch of references, including Cook's first proof.
Peter Shor 
CC BY-SA 2.5
2011-01-23T05:53:46.013Z
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
<computability><turing-machines>
Is there any way to differentiate between "sort of" Turing-Complete and "really" Turing-Complete?
Elliot JJ
# Is there any way to differentiate between "sort of" Turing-Complete and "really" Turing-Complete?

(Asked by: username_0 on 2011-01-20)

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](http://www.youtube.com/watch?v=cYw2ewoO6c4), 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"?

**Tags:** computability, turing-machines

> **Comments:**
> **username_2**: 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.  
> **username_0**: 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"  
> **username_2**: 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.  
> **username_3**: (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?  
> **username_4**: Are you thinking of Matthew Cook's first proof showing [Wolfram's rule 110](http://en.wikipedia.org/wiki/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.  
> **username_5**: 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.  
> **username_6**: @Peter: Do you have a reference for the Rule-110 result?  
> **username_4**: [Wikipedia](http://en.wikipedia.org/wiki/Rule_110) has a bunch of references, including Cook's first proof.  
> **username_7**: 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.  
> **username_1**: jeffE-- I cited martinez et al [here](http://cstheory.stackexchange.com/a/11661/7884) which is the latest simplification of rule 110 TM completeness Ive heard of and maybe what PS is alluding to  
> **username_1**: 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.  

---

## 2 answers

### Answer by username_10 on 2011-01-23. Score: 16 | Accepted answer

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.


---

### Answer by username_8 on 2020-05-19. Score: 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.

> **Comments:**
> **username_9**: 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.  

---

