In my discussion with Sal Cordova in this post, one point came up which I thought was interesting, and worth taking the time to flesh out as a separate post. It’s about the distinction

between a *Turing equivalent* computing system, and a *Turing complete* computation. It’s true

that in informal use, we often tend to muddy the line between these two related but distinct concepts. But in fact, they are distinct, and the difference between them can be extremely important. In some sense, it’s the difference between “capable of” and “requires”; another way of looking at it is

“sufficient” versus “necessary”.

Let me start by giving you a definition of the two terms.

A *computing system* is called **Turing equivalent** if it is capable of performing any

computation that can be performed on a Turing machine. Another term for a Turing equivalent computing

system is an **effective computing system**. The importance of Turing equivalence comes down to the fact that computation has a fundamental limit; any Turing-equivalent/effective computing system can

perform *any* computation. There’s no computing device more powerful than a Turing machine – Turing machines and all other effective computing systems lie at the maximum point of capability of

mechanical computing devices.

A *computation* is Turing complete if it can only be computed by a Turing-equivalent computing

system. In fact, in the proper formal definition of Turing completeness, a computation *C* is

Turing complete if and only if the fact that a given computing device φ can compute the result of

*C* implies that φ can compute the result of *any other Turing complete computation*.

Why is this distinction so important?

The biggest reason is because it turns out that being Turing equivalent is actually remarkably

trivial. Intuitively, it seems like the maximum computation capability possible for a mechanical

computing device *should be* hard to achieve. But it isn’t! As you can see by perusing the

archives of the pathological programming language topic on this blog, there are lots of ways of producing

Turing-equivalent computing systems, and many of them are incredibly simple. In fact, it’s pretty hard

to design a device capable of performing mechanical computations which is *not*

Turing-equivalent. Almost any mechanical system that’s capable of performing any kind of computation

ends up being Turing equivalent; it’s only by imposing deliberate restrictions on them that we generally achieve less than Turing-equivalent capabilities. The only part of Turing equivalence that’s

difficult at all is unbounded storage; as long as you have the ability to perform anything like iteration or recursion, and you have some theoretically unbounded/expandable storage, you’ve got

a Turing-equivalent computing device.

Turing-completeness, on the other hand, is a rarer beast. Most computations simply *don’t* require the full capability of a Turing machine. There are a number of simpler classes of computing

devices; linear-bounded automata, primitive recursive automata, finite-state automata, etc. Most of the computations that we encounter are actually computable by a member of one of those simpler classes of devices.

To give a couple of concrete examples:

- The common factorial function is primitive recursive. It does
*not*require Turing-equivalent computational capabilities to compute. - Searching a telephone book for a specific person to find their phone number is at worst

linear-bounded; it does not require a Turing-equivalent computing device. - Compiling a program in most programming languages
*does not*require Turing

equivalent capabilities. (The*language*may be capable of expressing Turing-complete

computations, but the process of translating from the language to code for a specific

computing device does not require Turing equivalent computation capabilities.)

The reason that this entered into my debate with Sal is because he, like many other people,

confused these two ideas. Because the DNA molecule can, in fact, perform Turing-complete computations,

you can view DNA (or, more generally, cell biochemistry) as a Turing-equivalent computing system. This

does *not* mean that cells *require* Turing-equivalent computational capabilities.

My argument with Sal is basically that Sal claims that the fact that DNA is Turing-equivalent means that life *requires* Turing-equivalent capabilities – which is another way of saying that *some part* of the basic biochemical processes that make up life are equivalent to a

**Turing-complete** computation. But that is *not* true – it’s an invalid implication. The fact that living things possess a component which is *capable* of Turing-equivalent computation

doesn’t mean that living things *require* Turing-equivalent computation.

To say that life contains DNA, which is a Turing-equivalent computing system, is saying that

Turing equivalent computational capability is *sufficient* for life. It is *not* saying

that it is *necessary* for life. The latter is a *much* stronger claim, and requires

more evidence.