[d-Pixie]

1. Sure, but just since finite input can be handled quickly doesn't mean it's not turing complete. A million cell tape for the Rule 110 automaton in any language will probably execute in milliseconds, if at all optimised... There might be other turing complete problems that can reuse tape the way you suggest, but Rule 110 isn't one of them.

2. In Turings own paper he envisions the "crank" to be a human. I think we can all agree that a human is more than turing complete. The process of feeding the next cell etc isn't part of what makes something Turing complete. There is no requirement that it be self-cranking in Turings papers, nor the current formal definitions I have read. Could you supply an example of where this is brought up as a formal requirement?

3. Well, yes. The point here lies in the _rules_. The method of executing the rules doesn't really matter, as discussed in 2. Humans are > Turing complete ...

[vectorjohn]

About 2, sure. But when people say "X shown Turing complete", that doesn't have much meaning unless the X is somehow doing it without external input. Why? Because otherwise everything is Turing complete. Literally, "series of bits proven Turing complete!", "line of rocks on a sidewalk Turing complete!"

Because, the fact that computers exist is not a surprise. I mean, the original concept of a Turing machine is literally a tape and a read head.

[smitherfield]

I'm sorry if I totally butcher the fundamental concepts of Turing completeness here; I was neither a CS nor a math major.

But as I understand it a Turing machine is a physical impossibility because it is defined as having an infinite stream of data being inputted. And the physical presence of an infinity of information is a physical impossibility (I also wasn't a physics major, so I'm not sure if this violates physical laws or is just a practical impossibility, but either way it's obviously impossible).

So instead of an infinite stream of input, we usually define something as "Turing complete" if it's possible for it perform arbitrary computations on arbitrary input supplied in real time. CSS3 cannot do this; programming languages with real-time I/O can do this.

So CSS3 is "weakly" Turing-complete because it can perform arbitrary computations on arbitrary data input supplied ahead of time. With an infinite amount of random HTML-formatted data input ahead of time (same as a Turing machine), it can be equivalent to a Turing machine. C or Javascript are "strongly" Turing-complete because they can perform arbitrary computations on arbitrary, properly-formatted data input supplied ahead-of-time or in real time.

[Dylan16807]

1. I was making a point more about runtime complexity. This system can't take an input of size n and then perform more than O(n) computation. Because you don't just input the first line. Rule 110 has to be at least n^2, probably much more before you get an 'answer'? I don't feel like looking up papers at the moment.

2. But the behavior upon turning the crank is defined as part of the machine. The human can emulate it mentally, but they're not whole-cloth adding something that wasn't already in the machine.

3. The point here lies in the _rules_.

I agree. Which is why CSS is not Turing complete. CSS + a specific web page of enormous unending length + someone holding down a few keys is the minimum to reach Turing complete.

CSS is like "110", the number, by itself. It's not Turing complete without a bunch of rules that have absolutely nothing to do with CSS itself to push it along.