Comment by Grue3 | Hacker News Reader

Comment by Grue3 | Hacker News Reader

I'm so tired of "CSS is Turing Complete" meme being propagated. TC is a powerful result with important consequences. Namely the impossibility to solve Halting problem. But CSS is deterministic and a CSS "program" always halts.

"But, but, we are making an assumption that a user has to click this particular button until the page doesn't change anymore (assuming infinitely long page [1])"

To which I say, poppycock. The purpose of CSS language is to apply styles to the webpage. Once it is processed, the CSS "program" has done it's purpose and is finished (i.e. halted). Running the same CSS "program" over and over again until it consistently produces identical results is not the point of CSS (unlike, say LaTeX/BibTeX compilation process, where you need to compile one file several times to get citation page numbers right, which is Turing complete). You might want to call it something else, like RCSS (repeated CSS). Then, RCSS is Turing complete, but plain CSS isn't. Much like a calculator that can calculate z^2 + C isn't necessarily Turing complete, while a graphical calculator that can draw a Mandelbrot fractal by iterating that formula is.

[1] which is acceptable, due to infinite memory assumption of a regular Turing machine

I don't consider that a remotely relevant argument. CSS is intended to style webpages at all times, webpages which are dynamic; CSS has never had a 'purpose' of rendering once and only once since oh, I don't know, 1997 or so. You might as well object to the _Magic: the Gathering_ example because it assumes a human to play each card mechanically; or you might as well object to the very first Turing machine in Turing's paper because he asks us to assume a setup where it's a human (or 'computer' as they were then known as) following the instructions mechanically.

While I question the tone of the original post, it is correct.

The difference between being Turing complete and implementing rule 110 is crucial, and any discussion on the subject needs to make clear that these are not the same.

You are obfuscating the role of the driver. In the Turing machine, the driver is part of the Turing machine. In CSS, it is not, and has to be done by the user (or presumably a JS script).

As another post by Grue3 points out, almost any language can implement rule 110, including languages that are not Turing complete, and are explicitly said not to be Turing complete in the CS literature/community.

For example, Coq, Agda, Idris (with totality checking) and other languages based on Martin Lof type theory, are not Turing complete. That it why they are able to prove totality of their functions. But they can all implement rule 110 with no problem.

Just some more on dependently typed languages: The article actually mentions them in footnote 1. So as it stands, the CSS part really doesn't make sense, because everything written about CSS applies to these dependently typed languages.

In particular, you could write some Agda/Coq/Idris program that implements rule 110, and has some trivial user interaction to repeat this until a stable pattern is reached. This simulates a Turing machine.

> Namely the impossibility to solve Halting problem.

Also the possibility to compute anything possible computing with a turing machine. The fact that you can embed this logic into a style description language accidentally is a meme worth propagating, in my opinion.

I don't find it as silly as you do. After all, every programming language needs some physical stuff in the real world to follow the directions the language is encoding. For CSS, there's not a standard runtime, because it's obviously not the intention of CSS. But requiring a human to dumbly follow the rules encoded in this purpose-built CSS is pretty reasonable in this context (which is showing things to be Turing complete which one wouldn't expect to be Turing complete).

With transition:, width:, and :hover, I was able to make an element repeatedly cycle between states with the only user input being to leave a cursor positioned over the page.

Maybe it's a browser-specific quirk; maybe it uses features only implemented after the initial explorations of turing-complete CSS; maybe there isn't any way to hook the two together. CSS will continue to add features over the years, though, and each added feature is another chance to find a missing piece that makes turing-complete CSS easier, more possible, and/or more powerful.

>I'm so tired of "CSS is Turing Complete" meme being propagated.

The article addressed this:

>but the declarations interact with each other just enough to allow an encoding of the cellular automaton Rule 110 (assumption: requires mechanical mouse clicks on the web browser to advance state; see also the Magic: The Gathering example)

[Note: I have omitted links embedded in the original text.]

The claim is not that CSS is Turing-complete, only that it can be used to represent the rules of a Turing-complete automaton. You still need to provide a physical driver.

Rule 110 is so simple that practically everything can represent its rules. You don't need to be Turing complete to do it. Indeed, the rules are even representable in Presburger arithmetic, which, unlike Peano arithmetic, is decidable! You can deduce formulas for every single step of the process, just like with CSS! But I'm sure we can all agree that this is not Turing completeness, otherwise the term itself becomes a farce.

Rule 110 is Turing complete. Therefore anything which can implement/simulate it is also Turing complete.

The same is true of any other model of a Turing machine. If your host computer can simulate a Turing complete machine then the host is also Turing complete.

> You can deduce formulas for every single step of the process, just like with CSS!

You can deduce the formulas, but can you make the formulas self-deducing when driven only by a mechanical clock like a steady mouse-click? Or will it require constant adjustment and intervention by the operator?

> But I'm sure we can all agree that this is not Turing completeness

I'm not sure we can. TC can be tricky. That's why people try to give constructions rather than just claim something or other is TC.

Reply on news.ycombinator.com