Conference Publication Details
Mandatory Fields
Neary, Turlough; Woods, Damien
MCU: 5th International Conference on Machines, Computations and Universality
Four small universal Turing machines
2007
January
Published
1
14 ()
Optional Fields
242
254
We present small polynomial time universal Turing machines with state-symbol pairs of (5,5), (6,4), (9,3) and (18,2). These machines simulate our new variant of tag system, the bi-tag system and are the smallest known universal Turing machines with 5, 4, 3 and 2-symbols respectively. Our 5-symbol machine uses the same number of instructions (22) as the smallest known universal Turing machine by Rogozhin.
Grant Details