loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
On the time complexity of 2-tag systems and small universal Turing machines
Berkeley, California
October 21-October 24
ISBN: 0-7695-2720-5
ASCII Text
x 
 
Damien Woods, Turlough Neary, "On the time complexity of 2-tag systems and small universal Turing machines," Foundations of Computer Science, IEEE Annual Symposium on, pp. 439-448, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/FOCS.2006.58,
author = {Damien Woods and Turlough Neary},
title = {On the time complexity of 2-tag systems and small universal Turing machines},
journal ={Foundations of Computer Science, IEEE Annual Symposium on},
volume = {0},
year = {2006},
issn = {0272-5428},
pages = {439-448},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.58},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, IEEE Annual Symposium on
TI - On the time complexity of 2-tag systems and small universal Turing machines
SN - 0272-5428
SP439
EP448
A1 - Damien Woods,
A1 - Turlough Neary,
PY - 2006
KW - null
VL - 0
JA - Foundations of Computer Science, IEEE Annual Symposium on
ER -
 
Damien Woods, University College Cork, Ireland
Turlough Neary, National University of Ireland, Ireland
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.
Citation:
Damien Woods, Turlough Neary, "On the time complexity of 2-tag systems and small universal Turing machines," focs, pp.439-448, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.