On the time complexity of 2-tag systems and small universal Turing machines
<|reference_start|>On the time complexity of 2-tag systems and small universal Turing machines: 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.<|reference_end|>
@article{woods2006on,
    title={On the time complexity of 2-tag systems and small universal Turing
  machines},
    author={Damien Woods, Turlough Neary},
    journal={FOCS 2006: 47th Annual IEEE Symposium on Foundations of Computer
  Science, IEEE, pages 439-446, Berkeley, CA},
    year={2006},
    doi={10.1109/FOCS.2006.58},
    archivePrefix={arXiv},
    eprint={cs/0612089},
    primaryClass={cs.CC cs.DS}
}