BerandaComputers and TechnologyIs CSS Turing Complete?

Is CSS Turing Complete?

One aspect of Turing completeness is the halting problem.

This means that, if CSS is Turing complete, then there’s no general algorithm for determining whether a CSS program will finish running or loop forever.

But we can derive such an algorithm for CSS! Here it is:

  • If the stylesheet doesn’t declare any animations, then it will halt.

  • If it does have animations, then:

    • If any animation-iteration-count is infinite, and the containing selector is matched in the HTML, then it will not halt.

    • Otherwise, it will halt.

That’s it. Since we just solved the halting problem for CSS, it follows that CSS is not Turing complete.

(Other people have mentioned IE 6, which allows for embedding arbitrary JavaScript expressions in CSS; that will obviously add Turing completeness. But that feature is non-standard, and nobody in their right mind uses it anyway.)


Daniel Wagner brought up a point that I missed in the original answer. He notes that while I’ve covered animations, other parts of the style engine such as selector matching or layout can lead to Turing completeness as well. While it’s difficult to make a formal argument about these, I’ll try to outline why Turing completeness is still unlikely to happen.

First: Turing complete languages have some way of feeding data back into itself, whether it be through recursion or looping. But the design of the CSS language is hostile to this feedback:

  • @media queries can only check properties of the browser itself, such as viewport size or pixel resolution. These properties can change via user interaction or JavaScript code (e.g. resizing the browser window), but not through CSS alone.

  • ::before and ::after pseudo-elements are not considered part of the DOM, and cannot be matched in any other way.

  • Selector combinators can only inspect elements above and before the current element, so they cannot be used to create dependency cycles.

  • It’s possible to shift an element away when you hover over it, but the position only updates when you move the mouse.

That should be enough to convince you that selector matching, on its own, cannot be Turing complete. But what about layout?

The modern CSS layout algorithm is very complex, with features such as Flexbox and Grid muddying the waters. But even if it were possible to trigger an infinite loop with layout, it would be hard to leverage this to perform useful computation. That’s because CSS selectors inspect only the internal structure of the DOM, not how these elements are laid out on the screen. So any Turing completeness proof using the layout system must depend on layout alone.

Finally – and this is perhaps the most important reason – browser vendors have an interest in keeping CSS not Turing complete. By restricting the language, vendors allow for clever optimizations that make the web faster for everyone. Moreover, Google dedicates a whole server farm to searching for bugs in Chrome. If there were a way to write an infinite loop using CSS, then they probably would have found it already 😉

Read More

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments