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