Skip to content

Minsky Did Theory

March 19, 2009


Two counter machines are universal

images12

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.

About these ads
2 Comments leave one →
  1. March 30, 2009 7:25 pm

    The encoding trick of using prime powers to encode a vector of integers in an integer is indeed nonobvious and very clever, but it may be worth pointing out that it is not original with Minsky; as you know, Gödel famously used it in his 1931 paper, and it may have a longer history than that. (If I were a mathematician or a theoretician I would presumably have a better chance of knowing the relevant literature; I only know of Gödel’s theorem because of GEB, which IIRC actually omits the 2ⁿ3ⁿ5ⁿ7ⁿ… scheme.)

    • rjlipton permalink*
      March 30, 2009 10:16 pm

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,689 other followers