The complexity of small universal Turing machines : a survey

DSpace/Manakin Repository

Show simple item record

dc.contributor.author Neary, Turlough
dc.contributor.author Woods, Damien
dc.date.accessioned 2011-11-24T15:24:24Z
dc.date.available 2011-11-24T15:24:24Z
dc.date.copyright 2008 Elsevier B.V. en
dc.date.issued 2009-02-17
dc.identifier.citation Theoretical Computer Science en
dc.identifier.issn 0304-3975
dc.identifier.uri http://hdl.handle.net/10197/3341
dc.description.abstract We survey some work concerned with small universal Turing machines, cellular automata, tag systems, and other simple models of computation. For example it has been an open question for some time as to whether the smallest known universal Turing machines of Minsky, Rogozhin, Baiocchi and Kudlek are efficient (polynomial time) simulators of Turing machines. These are some of the most intuitively simple computational devices and previously the best known simulations were exponentially slow. We discuss recent work that shows that these machines are indeed efficient simulators. In addition, another related result shows that Rule 110, a well-known elementary cellular automaton, is efficiently universal. We also discuss some old and new universal program size results, including the smallest known universal Turing machines. We finish the survey with results on generalised and restricted Turing machine models including machines with a periodic background on the tape (instead of a blank symbol), multiple tapes, multiple dimensions, and machines that never write to their tape. We then discuss some ideas for future work. en
dc.description.sponsorship Science Foundation Ireland en
dc.format.extent 268138 bytes
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher Elsevier en
dc.rights This is the author’s version of a work that was accepted for publication in Theoretical Computer Science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Theoretical Computer Science 410(4-5), Feburary 2009, pp 443-450 DOI: 10.1016/j.tcs.2008.09.051 en
dc.subject Universal Turing machine en
dc.subject Small universal Turing machine en
dc.subject Simple universal Turing machines en
dc.subject Computational complexity en
dc.subject Polynomial time en
dc.subject Tag systems en
dc.subject Cellular automata en
dc.subject.lcsh Turing machines en
dc.subject.lcsh Computational complexity en
dc.subject.lcsh Cellular automata en
dc.title The complexity of small universal Turing machines : a survey en
dc.type Journal Article en
dc.internal.availability Full text available en
dc.internal.webversions http://dx.doi.org/10.1016/j.tcs.2008.09.051 en
dc.status Peer reviewed en
dc.identifier.volume 410 en
dc.identifier.issue 4-5 en
dc.identifier.startpage 443 en
dc.identifier.endpage 450 en
dc.identifier.doi 10.1016/j.tcs.2008.09.051
dc.neeo.contributor Neary|Turlough|aut| en
dc.neeo.contributor Woods|Damien|aut| en
dc.description.admin Extended version of Theoretical Computer Science 410(4-5), Feburary 2009, pp 443-450 so I'm adding doi and rights info for Elsevier: not sure if that's right? - AV 11/10/2011 ke - kpw10/11/11 en


This item appears in the following Collection(s)

Show simple item record

This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.

If you are a publisher or author and have copyright concerns for any item, please email research.repository@ucd.ie and the item will be withdrawn immediately. The author or person responsible for depositing the article will be contacted within one business day.

Search Research Repository


Advanced Search

Browse