3 ms·
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 t
by RUBwkVjwLsDKgPw 11y ago
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.