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

Berkeley, California October 21-October 24

DOI Bookmark:

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

47th Annual IEEE Symposium on Foundat ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	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

	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

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.