Origin

A while ago I read a blog post by Eli Fox-Epstein. Eli is a student of computer science and works in the areas of graph algorithms and computational geometry. I have come to know him as a smart, hard working and very pleasant person. But automata theory is not his main field (nor mine for that matter) and the implementation we are going to discuss was an experiment, a quick hack before a technical talk, not an attempt on a formal proof.

I would like to point out that as far as I know Eli has not made any claim that his toy program is a proof of turing completeness. At least not publicly. But others keep using his implementation as proof though so let’s get on that, sorry Eli :/

Minimal theoretical computer science

Disclaimer 1: This article is about theoretical computer science, it might hurt your brain. But hang in there, I’ll try to make it as easy to understand as possible.

Disclaimer 2: This article is about theoretical computer science, for ordinary developers. I might (probably “will”) misuse formal terms and gloss over a lot of highly interesting details. Feel free to send me angry emails when I do, but I want this article to be accessible and giving a quick CS major grounding would really make the post too long. While I’m a CS major student not all of you are likely to be so we need to lay some groundwork (if you are a CS major or similar you can opt to jump to “The claim”, or read it all as a refresher … it’s up to you). I will be talking about Turing completeness and proofs and stuff here. It might all seem overwhelming so let’s summarise the most important bits:

Proof

A proof in this context means that we can, using maths and logic and stuff, derive that what we claim follows from other things we know. This is important since it leaves no room for “I think”, either it is proven or it is not.

Disproof

The second part here is that no proof is not the same as disproof. Just because we can’t prove something doesn’t mean it’s not true, just that we don’t know if it is, yet.

Turing completeness

Proving Turing completeness proves that an instruction set has a certain complexity level, that it can be used to solve a certain class of problems. Turing completeness is important since it’s the tightest definition, the definition that allows for the least amount of unnecessary extras, for instruction sets that can be used to implement any algorithm we have. It’s the basic bound that any general purpose programming language needs to achieve.

So, with these most basic stepping stones in place let’s look at some more formal definitions. We need to talk about Turing completeness, as I mentioned, and to do that it helps a lot if one knows what a Turing machine is, so let’s start there…

Turing machines

The wikipedia article about turing machines is really good, so let’s copy the “Informal description” section from there:

The Turing machine mathematically models a machine that mechanically operates on a tape. On this tape are symbols, which the machine can read and write, one at a time, using a tape head. Operation is fully determined by a finite set of elementary instructions such as “in state 42, if the symbol seen is 0, write a 1; if the symbol seen is 1, change into state 17; in state 17, if the symbol seen is 0, write a 1 and change to state 6;” etc. In the original article (“On computable numbers, with an application to the Entscheidungs problem”, see also references below), Turing imagines not a mechanism, but a person whom he calls the “computer”, who executes these deterministic mechanical rules slavishly (or as Turing puts it, “in a desultory manner”). More precisely, a Turing machine consists of:

1. A tape divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol (here written as ‘0’) and one or more other symbols. The tape is assumed to be arbitrarily extendable to the left and to the right, i.e., the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written before are assumed to be filled with the blank symbol. In some models the tape has a left end marked with a special symbol; the tape extends or is indefinitely extensible to the right.

2. A head that can read and write symbols on the tape and move the tape left and right one (and only one) cell at a time. In some models the head moves and the tape is stationary.

3. A state register that stores the state of the Turing machine, one of finitely many. Among these is the special start state with which the state register is initialised. These states, writes Turing, replace the “state of mind” a person performing computations would ordinarily be in.

4. A finite table (occasionally called an action table or transition function) of instructions [snip] Note that every part of the machine (i.e. its state and symbol-collections) and its actions (such as printing, erasing and tape motion) is finite, discrete_ and distinguishable; it is the potentially unlimited amount of tape that gives it an unbounded amount of storage space.

I cut the formal parts from point 4 since they are not that important here, you should read the entire article if you want a more in depth, formal description of Turing machines. Anyway, the ending of point 4 is rather important. The most important part is the “finite, discrete and distinguishable” part.

What this means is that even though the input to the machine might be infinite, we don’t know since we can only see one symbol at a time, the rules we use to manipulate the symbol and move the tape must be a finite set of rules.

Turing completeness

We need to define this as well, but with Turing machines in the bag this is easy - the first lines from the wikipedia article on turing completeness:

In computability theory, a system of data-manipulation rules (such as a computer’s instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing machine.

There is also the pesky little details surrounding terminology. Real Turing machines, and therefore Turing completeness, require unlimited time and space. In reality we have have limitations on execution time and storage space, so no real computer system is a Turing machine nor any language truly Turing complete. But even serious computer scientists choose to gloss over that fact for the sake of getting on with the job and actually getting something done.

The correct term for our finite systems is actually “linear bounded automaton”, but normally the terms “Turing machine” and “Turing complete” are used to describe systems that have limited resources as well since the other parts of the maths surrounding Turing machines work for them as well. Given the mentioned limitations of course.

Proving turing completeness

Proving that an instruction set is Turing complete is an arduous task. To avoid generally proving it mathematically every time the question arises some shortcuts have arisen. We know that Turing completeness is a bound on computational complexity and it then follows that there exist some class of problems that can not be solved without a Turing complete instruction set.

An example of such a problem is that of implementing a simple Turing machine, more precisely a universal Turing machine, a Turing machine that can simulate any Turing machine.

These are very simple machines and not what you would want to use for any practical work, they are research tools. There are many examples of such machines and we will look at one in particular. You guessed it; the Rule 110 automaton.

Rule110

To give you a view of what this looks like I wrote an implementation of the Rule 110 automaton on JSFiddle that you can play with. It can be played with using the URL, just change the string of ones and zeros at the end to change the input you give the automaton.

The example below is what you get from this URL: http://jsfiddle.net/dPixie/8ae9X/8/show/#00010011011111000100110111110001001101111100010011011111. Oh and by the way; mine is written in Javascript, not CSS/HTML, just so there is no confusion :)

The rules for the Rule110 automaton is pretty simple (and if my short explanation doesn’t suffice you can find a longer, and excellent, exposé about it here: http://natureofcode.com/book/chapter-7-cellular-automata/).

Say you have a piece of paper, a strip from a squared notepad with a single row of squares on it. You can colour in the squares, or leave them blank, as you wish. That first strip, with it’s mix of colored and blank squares, will be the input to our automaton.

Ok, so we have some input, of any length, and we want to produce some output. To go from input to output we need some rules so let’s set some up:

This set of rules says that to know how to “calculate” the result for a cell we need to look at the cell on the row above us and its two neighbors, the cells up and to the left and right of it. So if the cell above is ■ and its neighbour to the left is ■ as well but the neighbour to the right is □ we should use the ■■□-rule and our square would be ■.

The ends of the paper will be a problem of cause, since the first cell has no left side neighbour and the last cell has no neighbour to the right, but it’s easy to solve as well. If we are filling in the first square of our output strip we only have to square above and the one to the right of it. To “fill in” the missing square to the left we “borrow” the last square on the input strip and use that.

So if the input strip is: ■□□■□■we would get ?■□ and borrow the rightmost square to make it ■■□. Imagine that you tape the input strip end to end, to form a circle. With the circle you have not such problem and can fill in any cell below based on the three cells above. That is basically how it’s done but if it’s still unclear, visit the link above. They have illustrations and stuff :)

That is the basis for the Rule 110 automaton, that set of rules. There are many other automatons that use the same structure but has other rules and produce different results from the same original input.

The other thing to notice is that the result of running the automaton is a strip of paper with black or blank boxes (this is normally an array of 1’s and 0’s when programming this). So we can then run the automaton again on the output from the last run. We can do that as many times as we want and it will print a new row for each run over the last row.

Major points

As we have just seen the automaton is very simple. It’s a “mechanical” process, moving where you look to find data and record the result, and it has a very simple set of rules.

The mechanical man

In the context of implementing a Turing machine one is allowed to disregard the mechanical parts, it could be the process of pen and paper as described above, or maybe cranking the handle of a truly mechanical machine, using power to flip bits in a computer or repeatedly pressing a mouse button to step the process along.

The input tape

One can also skip the representation of the input and output. We used strips of paper in the earlier example, a mechanical device might use an infinite set of punch cards or the DOM created from an HTML document.

Rule set size

The definition is very strict in that a Turing machine has a fixed, finite set of rules regardless of the length of the input etc.

Our rules above, described as for a person in a box, are a small, finite set of rules that describe the Rule 110 automaton. These rules stay the same regardless of the size of the input.

The claim

The claim is that Eli’s implementation of the Rule 110 automaton is complete and therefore constitutes proof that CSS+HTML is Turing complete. Let’s examine that a bit.

The implementation is a 10 by 10 grid of checkboxes and labels. The checkboxes are not visible and the labels are the actual squares of the grid.

Each label gets its value and colors with the help of CSS and the :checked pseudo class. In essence each time a cell is clicked the label gets its style by lookbehind rules that look at the different combinations of checked checkboxes in the previous row.

The lookbehind is achieved using the adjacent selector, +, together with the any selector, *. A rule like:

input:checked +*+ input:checked +*+ input:checked +*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ label {
  background: #fff;
}

checks if the relevant cells on the previous row represents ■■■ by only targeting the current cell if the cells 9,10 and 11 steps behind it was checked. If so it sets the background to white, indicating that the cell represents □. The checking, or not, of boxes are solved by performing a set of manual steps for each checked box, boxes that evaluate to unchecked are skipped thanks to some use of display: none; to remove the relevant elements from the tab order.

The problems

Feel free to skip the intro unless you care about why I started looking into Eli’s project in the first place :)

Intro

The thing that got me interested in this i the first place was that I had recently (then recently, not now recently) read some comments on the www-style mailing list, originally implicated by a blog post by Shaun Inman.

Shaun’s post is discussing the possible implementation of an qualifying or parent selector, like the child selector, >, but selecting based on elements AFTER the one the rules apply to.

The general consensus was that it’s not wise since it would mean you could get into infinite loops and stuff. Anyway the gist, best described by Webkit engineer Dave Hyatt, was that the CSS engine is fairly complex, implementing the suggested selector would necessitate multiple render passes and that they don’t want the CSS implementation to be Turing complete since it will mean trouble for them (loops, memory usage, redraws galore etc).

As such the proposal Shaun came with had already been proposed, and disposed of, several times before. So I figured if they don’t want the spec to become too complex (and I think we can agree that Turing complete is too complex) and guard against new rules that might make it so it seemed unlikely it would be.

The rule length

One thing that struck me at once what that the rules were tied to the number of columns in the grid. That means that if you have 8 CSS rules, minimum, that use fixed length adjacent selector chains to solve the problem when there is 10 columns you’d need another 8 rules for a size of 11…

So for every possible size of the input you need some number, R, rules in CSS. So far we have two sizes of inputs, size 10 and size 11. If we go back to the definition of a Turing machine one part stands out: “4. A finite table of instructions …” Wikipedia

So our rule set size increase with the number of sizes we can handle. The Rule 110 automaton should be able to handle any size of the problem so we have a problem here.

Clearly the implementation as it stands do not fulfil the requirements for a complete Rule 110 implementation. We should be able to handle any number of columns and generate any number of rows.

Number of rows

Eli and I have had some long discussions about what can be counted as mechanical cranking and how to square the limitations of our browsers implementation of DOM and HTML with the concepts the standard describes.

Eli convinced me that a fixed sequence of manual operations are the same as a crank (since you could actually make a mechanical device that did all of the actions and was run with a crank I agreed :)).

We also agree that the fact that HTML and the DOM are currently exclusive to the browser, and have limitations such as loading completely before rendering etc, do not actually impact the argument for them as the tape in a theoretical meaning.

One could use a streaming server to produce an endless HTML document for example. The browser would then update the DOM bit by bit and reapply the CSS etc.

So if we assume that the HTML is endless we can produce as many rows as we want. Each new set of HTML elements needed to describe the checkbox, label etc used to describe a cell on the page is simple one symbol in the Turing machine sense of the term.

Number of columns

This is the point at which it falls apart as Mesh says. We have already seen that the rules will grow for every size of columns we need to handle.

What this means is that the problem space that Eli’s implementation handles is a full dimension smaller than the space a true Rule 110 automaton should handle.

But wait!

So someone was wrong on the internet. And I have done my duty. However … While we were talking, Eli met my criticism with CSS :) He has produced a version of his original work that is, at least given the concessions we have agreed to regarding cranking and HTML size, a complete Rule 110 implementation in CSS and HTML.

Go read the short post we put together on it here: CSS3 proven to be turing complete.

And definitely play with it on Eli’s server

Finally

Apparently more than one person was wrong on the internet, it just took me forever to get there. Turns out Eli could do what many claimed he had already done and it turns out I too was wrong. CSS appears to be Turing complete.

Sorry for wasting your time :)

/Jonas

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