Index of /~peter/projects/math/post

 Name                    Last modified      Size  Description
 Parent Directory                             -   
 README.html             12-Jul-2007 15:08  1.7K  
 post.py                 12-Jul-2007 15:08  2.2K  

Emil Post, one of the lesser-known founders of computability, developed what he called a "tag system". What you do is, you take a string of 0s and 1s, and chop off the first 3 numbers. Then, if your string began with 0, append 00 to the end of the string, and if it began with 1, put 1101 at the end. Stop if you ever get an empty string. You can see it in action as:

1100111
   01111101
      1110100
         01001101
            0110100
               010000
                  00000
                     0000
                        000
                           END

Actually, he developed the whole concept of a tag system, and tag systems were later proven to be equivalent to Turing Machines by Marvin Minsky, and the whole thing is much more complicated. But the system described above was, he felt, the smallest interesting one. For one thing, nobody has proven that it is guaranteed to not grow to infinity on all input, but nobody has found any input that hasn't eventually gone into either a loop or dwindled away to the empty string. (Aside: Loop? Yes. Sometimes you can get back to a string you've already seen before.) It's not clear that anyone has poked at this problem in the 60 or so years since he published these results. Some stuff has been done about tag systems in general, but once they were proven equivalent to Turing machines, the field moved on.

But I still want to know: Are there any strings which cause this system to run forever without looping? What string of length n causes the machine to run the longest before looping or ending?

If this excites you and you want to poke at the problem, here's some ugly python code to work from.