Conference Publication Details
Mandatory Fields
Woods, Damien; Neary, Turlough
MCU: 5th International Conference on Machines, Computations and Universality
Small semi-weakly universal Turing machines
2007
January
Published
1
12 ()
Optional Fields
303
315
We present two small universal Turing machines that have 3 states and 7 symbols, and 4 states and 5 symbols respectively. These machines are semi-weak which means that on one side of the input they have an infinitely repeated word and on the other side there is the usual infinitely repeated blank symbol. This work can be regarded as a continuation of early work by Watanabe on semi-weak machines. One of our machines has only 17 transition rules making it the smallest known semi-weakly universal Turing machine. Interestingly, our two machines are symmetric with Watanabe's 7-state and 3-symbol, and 5-state and 4-symbol machines, even though we use a different simulation technique.
Grant Details