Two counter machines are universal

Marvin Minsky is a Turing Award winner and one of the founders of the area of artificial intelligence. Early in his career he worked in theory and proved some basic and very pretty theorems. Some are so old that I am afraid many of you may not even know them. This post is about one of these results; besides this result he, along with Seymour Papert, did early lower bounds for linear threshold functions. One wonders what he might have done for theory if he stayed in our area.

The Result

Minsky proved that two counter machines are universal. The proof is from his book: Computation: Finite and Infinite Machines A two counter machine has two unbounded counters and a deterministic finite state control. The machine also has an one way input tape. The machine can test a counter to see if it is zero, add or subtract ${1}$ from a counter. Subtraction, of course, only works when the counter is positive. Minsky theorem is that a two counter machine is universal. The key is he can show how two counters can simulate any number of counters (fixed): it is not hard to show that enough counters can simulate an arbitrary Turing Machine.

Minsky’s proof is quite clever, and if you have not seen it before I think you may agree. The idea is to use

$\displaystyle 2^{a}3^{b}5^{c}7^{d}$

to represent the state of a four counter machine: there is nothing special about four, his method can do any number of counters. You keep this value in one counter, the other counter is used only during operations.

We must show how to add, subtract, and test any one of the counters for zero, while preserving the representation. Let’s do zero testing first. Suppose we want to tell if the counter $c$ is zero. We do this by checking whether or not

$\displaystyle 2^{a}3^{b}5^{c}7^{d}.$

is zero modulo $5$. This is done by copying the value of this counter into the other counter. We subtract from the first and add to the second, all the while keeping track of the value modulo $5$ in the finite state control. We stop when the first counter is zero. The finite state control, then determines whether or not $c$ was zero or not.

The same copying trick is used to add one and subtract one. Suppose, we want to add one to the counter ${c}$: we just decrement the first counter by ${1}$ and add ${5}$ to the second counter. When the first is ${0}$ the second will contain the value

$\displaystyle 2^{a}3^{b}5^{c+1}7^{d}.$

Open Problems

Perhaps the main open problem is why I decided to post this note. I really like the result, I think the encoding trick of prime powers is not at all obvious. Years ago I was quite interested in a variety of decidability questions and counter machines often played an important role. Minsky’s theorem that two counters suffices is sometimes quite useful in proving that some computational model is universal. By the way, it is easy to prove that one counter is not universal. The trick to that is to use the fact that pushdown automata have a decidable emptiness problem.

Gödel uses primes to encode information via his famous $\beta$ lemma. He does this in a related but different method.