If you got here first you should really check out part one of this blog post that you can find here Duty calls - CSS3 is not proven to be turing complete. It’s a bit longer but handles a lot more of the background to the things in this piece. This was really just written as a short followup to the first one :)

CSS is actually “Turing Complete”

Eli & Jonas

In early 2011, Eli presented an example of CSS and HTML simulating Rule 110 (which is Turing Complete) at a Hack && Tell event. It spread widely online, from Wikipedia’s article on Turing Completeness to Professors’ websites to blogs, reddit, Q&A sites, and YouTube. This post shows that the original is not Turing Complete, but presents a modification to make it “more” Turing complete than C. The new version is here and details are below.

Turing completeness captures the idea of universal computation. Many very different systems for computation have been shown to be capable of computing the exact same things. The canonical system for computation is the Turing machine: a set of rules governing the behaviour of a read/write head on an infinite reel of tape, each cell of which holds one letter from a fixed alphabet.

You can write a simple Turing machine simulator in C. Doing this informally shows that C is Turing complete. But C without I/O isn’t really Turing complete because any implementation is required to decide on a pointer length and that limits how much memory can be stored. So how do we cope with this? One might call this a linear bounded automaton or some relative.

A priori, there’s no limit to the size of HTML documents, but thinking about infinite HTML becomes problematic. For example, with the following CSS, which of an infinite number of divs would be visible?

div { display: none; }
div:last { display: block; }

There are two solutions to this: we can lower our expectations and show CSS is as computationally powerful as C (without I/O) or we can work under a streaming model of HTML.

Assume that the amount of HTML currently loaded is finite but sufficient for all of the state to be properly rendered. Imagine an old-school movie projector changeover system–when one reel is running out, you seamlessly swap to the next. In the world of Turing machines, this would be equivalent to assuming your tape is of finite length but whenever you try to read off one end, someone quickly comes over to the machine and splices in some more tape. For C, maybe after each instruction is executed, the pointer size is magically increased.

The “CSS/HTML machine” we’re implementing consists of a fixed, finite amount of CSS3, along with an infinite (subject to above discussion) amount of HTML broken down into contiguous blocks of characters (analogous to the symbols in a Turing machine), each of which will simulate a Rule 110 cell. In this way, the HTML resembles the tape of a finite automaton or the grid of Rule 110.

Each step, one enforces all the rules of CSS according to the CSS3 specification on all of the currently-existing (finite) DOM. Then the DOM is grows. Finally, a finite, predetermined sequence of mouse and key events are applied to the DOM, updating :focus, :target, :checked CSS pseudo-classes.

In the original source code from a few years ago (see e.g. here), there’s some +*+*+*+ nonsense. This is used to target a cell in the subsequent row. Unfortunately, this means that the size of the CSS (in bits, say) is proportional to the number of columns. Informally, this means that if you’re allowed, say, 10000 bits of CSS, you can never handle, say, 101000000 columns. In particular, all languages that this method of encoding of a Turing machine could recognise can be recognised in PSPACE. This makes Eli’s first example significantly less powerful than Turing machines.

Here’s the gist of fixing it: use anchors and the corresponding “:target” CSS pseudo-class to know what cell to update next. The same style of tabbing order hacks are used: elements with display:none are skipped when pressing tab to jump between checkboxes or links. You can play with it here and check out the CSS here.

Image of course courtesy of the great “Snopes” XKCD strip by the one and only Randall Munroe.