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

fYear

2006

fDate

Oct. 2006

Firstpage

439

Lastpage

448

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Foundations of Computer Science, 2006. FOCS '06. 47th Annual IEEE Symposium on

Conference_Location

Berkeley, CA

ISSN

0272-5428

Print_ISBN

0-7695-2720-5

Type

conf

DOI

10.1109/FOCS.2006.58

Filename

4031379

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2913958