Title :
On the time complexity of 2-tag systems and small universal Turing machines
Author :
Woods, Damien ; Neary, Turlough
Author_Institution :
Dept. of Math., Boole Centre for Res. in Informatics, Cork
Abstract :
We show that 2-tag systems efficiently simulate Turing machines. As a corollary we find that the small universal Turing machines of Rogozhin, Minsky and others simulate Turing machines in polynomial time. This is an exponential improvement on the previously known simulation time overhead and improves a forty year old result in the area of small universal Turing machines
Keywords :
Turing machines; computational complexity; 2-tag system; polynomial time; simulation time overhead; time complexity; universal Turing machine; Computational complexity; Computational modeling; Computer science; Computer simulation; Councils; Educational institutions; Informatics; Mathematics; Polynomials; Turing machines;
Conference_Titel :
Foundations of Computer Science, 2006. FOCS '06. 47th Annual IEEE Symposium on
Conference_Location :
Berkeley, CA
Print_ISBN :
0-7695-2720-5
DOI :
10.1109/FOCS.2006.58
