1. Feeding infinite HTML is not the same as feeding tape. A million tape cells can keep a typical Turing machine running indefinitely. A million rows only keep this running for a million execution steps, which is what, a tenth of a second if optimized?
2. The 'crank' here is not part of CSS. Computer languages that are declared 'Turing complete' need to be able to crank themselves. You need to be able to tell them to go, and wait. I accept that magic the gathering Turing machine, (at least as long as you remove the word 'may'), because it's part of the MtG rule set that you continue performing all the state transitions until you reach a halt.
3. Allowing this completely external pump means that anything that can add and multiply three numbers and then exit would be counted as Turing complete, because you can then instantiate an infinite number of these and pump data through. The Turing complete nature of that construction lies mostly in that pump. It is not at all just a crank that say 'go'.
And 3 is really the important part here. None of the scary implications of 'Turing complete' come into play, because you can't take the result of one arithmetic statement and feed it into more. All of that playing around is roughly O(n) in terms of page size. Not O(unlimited) as 'Turing complete' might imply.
This is entirely correct. The article doesn't fix the original reason why the "CSS turing machine" wasn't actually a turing machine. It doesn't "crank its own tape", so to speak.
Layout in a web browser, which includes CSS styling, is implemented as just a top down + bottom up tree traversal. 2 tree traversals do not a turing machine make.
Maybe an analogy will help. I like the multiplier mentioned in the grandparent. Consider the multiplication circuit. I hope you agree that a multiplication circuit is not turing complete. However, if you apply a "pump" and feed its results into one of its inputs, you can calculate the factorial of any number!
This concept can be extended to take any sequence of steps and calculate recursive functions with them. This doesn't mean a linear sequence of instructions is turing complete! The feedback is a fundamental part of what makes the system turing complete.
The headline would better read "CSS + user input which can trigger a reflow is turing complete", but that wouldn't be nearly as interesting.
In fact, if CSS _was_ turing complete, I can solve the halting problem!
Step 1) Encode a turing machine as CSS + html.
Step 2) Run CSS and layout. This is O(size of css + size of html), since it's two tree traversals.
Step 3) It halts. CSS styling is finished.
CSS is just a tree traversal. It has a lot of rules, but the structure is simple. It is not turing complete.
> 1. Feeding infinite HTML is not the same as feeding
> tape. A million tape cells can keep a typical Turing
> machine running indefinitely. A million rows only keep
> this running for a million execution steps
There are read-only systems that are considered Turing Complete. They also work by concatenating new data (of potentially unbounded size) at each computation step. For example, a one-dimensional cellular automaton called Rule 110: https://en.wikipedia.org/wiki/Rule_110 . The fact that traditional Turing Machines reclaim storage is an implementation detail, not anything fundamental to Turing Completeness or computer science.
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 ...
Indeed, and if they want to make these claims why aren't they applying the same logic to Coq, Agda and Idris? These languages are often lauded (correctly) for giving up Turing completeness in exchange for improved static safety. But they all can implement rule 110.
1) it's not surprising: a lot of very simple systems can compute. It seems to naturally happen as you add flexibility to your rules. See for instance Wang Tiles or some cellular automata.
2) it's not a good thing: it means that the behavior of CSS3 is undecidable in general, which makes it much harder to build tools that can meaningfully analyze it.
Yeah. My initial thought after reading the title was, "Shit. Don't tell people this! Someone's going to be crazy enough to invent something with this knowledge."
Anyone who has worked with CSS long enough knows that:
1) Rule priority can get out-of-hand very quickly.
2) It's a nice thought to have more powerful selectors, but, taking #1 into consideration, perhaps limiting its power isn't such a bad idea after all.
I was already on-board with using PostCSS modules, https://github.com/postcss/postcss, to selectively import functionality for use in CSS rather than the heavy-handed approach of bringing all of SASS, LESS, or Stylus. Leaving powerful expression to languages built for it seems natural -- especially when CSS and JS intermingle so heavily.
I completely agree that it's not a good thing. I know that the browser maintainers also see the increasing complexity of CSS as a bad thing. That's why I was so sceptical to it from the start ...
I'm skeptical a little, in that the article starts off by saying it is "more" Turing complete than C. Something either is or is not Turing complete. The nitpick that a C implementation has a pointer size which limits the memory to !infinite is an unimportant implementation detail. If that's your argument, nothing is Turing complete because the universe is made out of a finite amount of matter and energy.
Also, as others have pointed out, it doesn't "run" unless an external thing is pressing buttons. If you allow what are essentially external programs to run, you might as well have Javascript doing the job, and then the headline becomes a lot less interesting.
So CSS3 is both Turing complete and so low-level that most projects of significant size use a preprocessor like LESS, SASS, etc to write their CSS3 for them.
I've never met an HTML streaming solution that won't just stream this sequentially, which means no </div> for myContainer will ever be emitted (and therefore the HTML will never be well-formed, and the CSS will never have sufficient information to lay out).
If the HTML were streamed such that <html><div class="myContainer"></div></html> were received, and then the interior of myContainer were streamed, that'd be a different story, but that doesn't exist. So I don't think this blog post's argument that CSS3 is Turing complete works for any real implementation.
What relevant CSS rule can't be applied to this? We know our previous context and everything before which is what CSS acts on anyway, no lookahead rules in CSS :)
And yes, there could come an yet as to unknown element later that changes the display, displays on top of using position:absolute; for example, of current content. But not that changes how current content itself is displayed.
[+] [-] Dylan16807|10 years ago|reply
2. The 'crank' here is not part of CSS. Computer languages that are declared 'Turing complete' need to be able to crank themselves. You need to be able to tell them to go, and wait. I accept that magic the gathering Turing machine, (at least as long as you remove the word 'may'), because it's part of the MtG rule set that you continue performing all the state transitions until you reach a halt.
3. Allowing this completely external pump means that anything that can add and multiply three numbers and then exit would be counted as Turing complete, because you can then instantiate an infinite number of these and pump data through. The Turing complete nature of that construction lies mostly in that pump. It is not at all just a crank that say 'go'.
And 3 is really the important part here. None of the scary implications of 'Turing complete' come into play, because you can't take the result of one arithmetic statement and feed it into more. All of that playing around is roughly O(n) in terms of page size. Not O(unlimited) as 'Turing complete' might imply.
[+] [-] RUBwkVjwLsDKgPw|10 years ago|reply
Layout in a web browser, which includes CSS styling, is implemented as just a top down + bottom up tree traversal. 2 tree traversals do not a turing machine make.
Maybe an analogy will help. I like the multiplier mentioned in the grandparent. Consider the multiplication circuit. I hope you agree that a multiplication circuit is not turing complete. However, if you apply a "pump" and feed its results into one of its inputs, you can calculate the factorial of any number!
This concept can be extended to take any sequence of steps and calculate recursive functions with them. This doesn't mean a linear sequence of instructions is turing complete! The feedback is a fundamental part of what makes the system turing complete.
The headline would better read "CSS + user input which can trigger a reflow is turing complete", but that wouldn't be nearly as interesting.
In fact, if CSS _was_ turing complete, I can solve the halting problem!
Step 1) Encode a turing machine as CSS + html.
Step 2) Run CSS and layout. This is O(size of css + size of html), since it's two tree traversals.
Step 3) It halts. CSS styling is finished.
CSS is just a tree traversal. It has a lot of rules, but the structure is simple. It is not turing complete.
[+] [-] lmkg|10 years ago|reply
[+] [-] vectorjohn|10 years ago|reply
[0] http://www.toothycat.net/~hologram/Turing/HowItWorks.html
[+] [-] d-Pixie|10 years ago|reply
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 ...
[+] [-] force_reboot|10 years ago|reply
[+] [-] murbard2|10 years ago|reply
1) it's not surprising: a lot of very simple systems can compute. It seems to naturally happen as you add flexibility to your rules. See for instance Wang Tiles or some cellular automata.
2) it's not a good thing: it means that the behavior of CSS3 is undecidable in general, which makes it much harder to build tools that can meaningfully analyze it.
[+] [-] SeanAnderson|10 years ago|reply
Anyone who has worked with CSS long enough knows that:
1) Rule priority can get out-of-hand very quickly. 2) It's a nice thought to have more powerful selectors, but, taking #1 into consideration, perhaps limiting its power isn't such a bad idea after all.
I was already on-board with using PostCSS modules, https://github.com/postcss/postcss, to selectively import functionality for use in CSS rather than the heavy-handed approach of bringing all of SASS, LESS, or Stylus. Leaving powerful expression to languages built for it seems natural -- especially when CSS and JS intermingle so heavily.
[+] [-] d-Pixie|10 years ago|reply
[+] [-] vectorjohn|10 years ago|reply
Also, as others have pointed out, it doesn't "run" unless an external thing is pressing buttons. If you allow what are essentially external programs to run, you might as well have Javascript doing the job, and then the headline becomes a lot less interesting.
[+] [-] haberman|10 years ago|reply
[+] [-] Spivak|10 years ago|reply
[+] [-] forrestthewoods|10 years ago|reply
[+] [-] PeCaN|10 years ago|reply
In practice it's probably not a problem since you don't have infinite HTML, but it is theoretically slightly disturbing.
I'm an advocate of provably-correct, non-Turing-complete languages, which really should include CSS....
[+] [-] akerro|10 years ago|reply
[+] [-] fixermark|10 years ago|reply
"Assume that the amount of HTML currently loaded is finite but sufficient for all of the state to be properly rendered."
So consider <html> <div class="myContainer"> <div>1</div> <div>2</div> <div>3</div> . . .
I've never met an HTML streaming solution that won't just stream this sequentially, which means no </div> for myContainer will ever be emitted (and therefore the HTML will never be well-formed, and the CSS will never have sufficient information to lay out).
If the HTML were streamed such that <html><div class="myContainer"></div></html> were received, and then the interior of myContainer were streamed, that'd be a different story, but that doesn't exist. So I don't think this blog post's argument that CSS3 is Turing complete works for any real implementation.
[+] [-] d-Pixie|10 years ago|reply
And yes, there could come an yet as to unknown element later that changes the display, displays on top of using position:absolute; for example, of current content. But not that changes how current content itself is displayed.
[+] [-] dheera|10 years ago|reply
[+] [-] yermierc|10 years ago|reply
https://css-tricks.com/snippets/css/a-guide-to-flexbox/
[+] [-] Raphmedia|10 years ago|reply
body { -webkit-align-items: center; -ms-flex-align: center; align-items: center; display: -webkit-flex; display: flex; }
[+] [-] gotchange|10 years ago|reply
[+] [-] neocraftster|10 years ago|reply
[+] [-] d-Pixie|10 years ago|reply