Lara Schenck

Last night I did a preview of my talk for a great group of folks at Code & Supply, and it went well! There were lots of great comments and questions, and it’s answering the tough ones that bring the best insights down the line. Justin Reese, the organizer of the space (and of Abstractions II the conference, check it out!), very kindly sent me a message with one of my answers to said tough questions. It’s a key takeaway from the talk and needs more slide real estate: “CSS can be your mental model, your spring board into other languages and concepts”.

Because that’s the thing…CSS is a programming language so you can learn other languages by linking new concepts back to what you already know about CSS!

It spurred me to dive into some experiments to truly understand some concepts I presented in my talk: namely, that CSS is Turing complete…or is it?

I have a section where I show an example of someone else’s implementation of Rule 110 (we’ll get to what that is), but that was copy pasta and it didn’t actually run. There’s a lot of debate about this topic, and until my adventures today, I was making a claim about something I did not actually understand. Yikes! I mean, people do that all the time, but still…

Okay, let’s get to it.

What does it mean to be Turing complete?

Actually, we need to back up even more…who was Alan Turing?

Alan Turing was a computer scientist and mathematician during World War II who developed a machine that could compute any math problem, and, suitably, that machine was called a Turing machine. That machine is the foundation of all modern digital devices…and it was invented in 1936!! He called it a-machine for short.

In the simplest terms, for a language or machine to be Turing complete, it means that it is capable of doing what a Turing machine could do: perform any calculation, a.k.a. universal computation. After all, programming was invented to do math although we do a lot more with it now, of course!

The requirements for being Turing complete (and thus capable of universal computation) are as follows:

1. Conditional branching, or the ability to determine if a thing is true or false according to the state of another thing.
2. Arbitrary memory, or that the machine can fall victim to a problem that is undecidable. Undecidable refers to a class of math and logic problems for which it is proven to be impossible to write an algorithm for a Turing machine that will return a correct answer. These problems will result in an infinite loop, causing the machine to run forever and consume an arbitrary amount of memory.

The thing is…there is no device on planet earth that has arbitrary memory, so how can we really know if a problem is undecidable or not? Every program will halt at some point because we are limited by the physical world! The second requirement for Turing completeness is, therefore, often disregarded.

Rule 110 is Turing Complete

Okay, now we are going to make a big jump, and I haven’t quite connected the dots enough to explain it in my own words, so here is a blanket statement and some sources:

Rule 110 is a cellular automaton (we’ll get to that in a moment) that is capable of universal computation and is therefore Turing complete.

I don’t entirely understand how cellular automata are capable of computation, but apparently there are systems modeled after certain automata and those systems are Turing complete. At least, according to this Stack Overflow thread that references this research paper that I did not read.

So, from what I can gather, Rule 110, is a kind of litmus test for Turing completeness: if the language can encode Rule 110, then it is Turing complete.

Cellular Automata 101

Cellular automata are rules for single cells of a grid to either be 1 or 0 (black or white) depending on their nearest neighbors. They are the source of much generative art (Conway’s Game of Life is a common one); the idea is you define some rules, set a value 1 or 0, and from that you can determine the rest of the values by following the nearest neighbor rules provided.

The elementary cellular automata are the simplest of them all, and I highly recommend watching this Youtube video from The Coding Train to get a deeper understanding.

You could have a rule like this:

Think of the bottom square as the focus point and its state (black or white / 1 or 0) is determined according to the three cells that touch it: the one to its top left, the one above it top, and the cell its top left. These rule sets can result in cool, generative formations like so:

Let’s look at this in CSS! We can use checkbox inputs to hold the state of each cell, and determine the state of the ones following it with adjacent sibling combinators (the +).

Let’s say we want to encode the fourth digit in the rule above: black/white/white => black, or 101 => 1. In CSS, the selector (this is where the conditional branching happens) would be:

input:checked + input:not(:checked) + input:not(:checked) + * {
   /* Declarations to indicate 1 */
}

This is the exact same logic as an imperative statement, like this:

if ( cellOne == 1 && cellTwo == 0 && cellThree == 0 ) {
   cellFour = 1;
}

The difference (which will bite us later) is that we cannot actually assign the value of 1 (i.e. :checked) to * using this approach, so it requires a click from a human to actually update the state.

Here is a CodePen with an example of the single cell. Try clicking to check/uncheck each one in the top row. The bottom cell will only be a 1 when the top three are set to 1 0 0, which is the logic that we programmed.

See the Pen Elementary Cellular Automaton – Single Cell by Lara Schenck (@laras126) on CodePen.

Hey, look! We are learning computer science…with declarative CSS! So cool!

Rule 190 in CSS

I started off programming rule 190 – it’s a little easier to visualize as it created one big triangle from the top down.

You will notice a bit of Sass in the below CodePen – all of the logic for the automaton itself comes from CSS, and I used Sass to help DRY things out a bit so the pen is easier to modify. The JavaScript is there for an “Unchecker” button so that I could reset the Pen to test out the logic. At this point, I was like, “How could write a test for this?!”. I’m not sure what that would look like, but it’s a cool thought and would have been useful in testing the logic.

Here is Rule 190 – click the top center cell to start, and click the following X cells to populate the next row:

See the Pen Rule 190 in CSS by Lara Schenck (@laras126) on CodePen.

It was very straightforward to translate this to Rule 110 – all I had to do is update the encoding rules to correspond to the rules of 110 vs 190.

Rule 110

And here we have it…the automata that, apparently, shows that CSS is Turing complete!

Not so fast. In this implementation, that is incorrect. Alone, CSS is not Turing complete. CSS plus HTML plus user input is Turing complete!

Click anywhere to start the program (the top right-most corner is a good place to start), and like above, click the pink Xs to run the program.

See the Pen Rule 110 in CSS by Lara Schenck (@laras126) on CodePen.

Given that CSS is a domain-specific language for styling user interface, this makes a lot of sense! CSS + HTML + Human = Turing complete.

At the end of that day, as CSS developers that is the language we really write. CSS is incomplete without HTML, and a styled interface is incomplete without a human to use it. All three together (CSS/HTML/Human) are extremely powerful! I wonder if we need a name for that language.

Help, CSS friends!

That being said, there very well may be a way to accomplish what the user input does with CSS animations or even CSS Grid. Actually, maybe the entire thing could be accomplished with CSS Grid. Any ideas, CSS friends?

Sources

Here are my sources – lots of good stuff!

1. Turing Machine on Wikipedia
2. Turing Complete on Computerphile
3. Undecideability Tangent on Computerphile
4. Miriam Nadler’s Sass Cellular Automata pen
5. Eli Fox-Epsteins’s Rule 110 in HTML/CSS
6. This excellent video from The Coding Train about Elementary Cellular Automata
7. This Stack Overflow thread for “Is CSS Turing Complete?”
8. Elementary Cellular Automaton on Wolfram Alpha