On the time complexity of 2-tag systems and small universal Turing machines

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Damien Woods Articles by Turlough Neary

47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)

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, Annual IEEE 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, Annual IEEE 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, Annual IEEE 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, Annual IEEE Symposium on ER -

Damien Woods, University College Cork, Ireland

Turlough Neary, National University of Ireland, Ireland

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.58

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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.