[FOM] 2,3 Turing machine proof controversy

[Tjark Weber]

On Tuesday 20 November 2007 02:15, Bob Hearn wrote:
> Speaking of small computing machines, and at the risk of contradicting
> myself that the notion is ill-defined, I was discussing this issue
> with Minsky, and he remarked that:
>
> > In any case, I still would like to know if Post's original 3-Tag
> > system is universal in any sense.  That's the one with the two
> > productions:
> >
> >  0 X X [string] -->  [string] 0 0
> >  1 X X [string] -->  [string] 1 1 0 1
> >
> > because I regard that as the simplest known unsolved machine.

I've written a small C program that emulates tag systems of this kind:
http://www4.in.tum.de/~webertj/software/tag-system/

Nothing fancy (and far from answering Minsky's question), but feel free to 
play with it.  Feedback is appreciated.

Tjark