# Turing Completeness Is Where You Least Expect It

From Magic the Gathering decks to CSS, computers are everywhere.
Michael Coghlan/Flickr

The condition of Turing completeness is almost always explained in terms of the Turing machine. Naturally. A Turing machine is simply a hypothetical black box that performs a small set of mathematical/logical operations on a strip of paper tape that is of potentially unlimited length. The box zips back and forth along the tape reading and writing data into discrete cells, eventually at some point in the future returning the answer to some question. This is what it is to be computable at all—an assurance that the machine won't run forever. Any true computer is just a simulation of this primitive abstraction.

I've always had a hard time with the idea of the Turing machine. Part of the problem is that the Turing machine as described above is often described in terms of what it is—a box that does mathematical operations on cellular divisions of a strip of paper tape—and not what it means. And what the Turing machine means is that there is a condition of being able solve any computational problem given enough time and memory.

For something to be Turing complete, it must be able to solve every problem solvable by any other computer that exists or that could be imagined to exist (such as a Turing machine). It may be easier to see this from the other side: a Turing incomplete computer is unable to solve some known class of problems solvable by another computer. Usually, when we talk about Turing completeness, we're talking about computers-as-programming languages, which are systems that describe how to solve different problems.

Most programming languages you've heard of are Turing complete. There are no computational problems that can be solved by C and not by JavaScript or by Java and not Python or by Python and not Java. And so on. An interesting exception is SQL—the language implementing relational databases—which in its most basic form is generally understood to be Turing incomplete. This makes sense given that SQL doesn't actually exist for general-purpose computation and doesn't need features like loops and if-then conditional branching (which allows sections of code to be skipped under certain circumstances).