The complexity of small universal Turing machines : a survey

Files in This Item:
File Description SizeFormat 
NearyWoods-Small-UTM-survey-2011.pdf261.85 kBAdobe PDFDownload
Title: The complexity of small universal Turing machines : a survey
Authors: Neary, Turlough
Woods, Damien
Permanent link:
Date: 17-Feb-2009
Online since: 2011-11-24T15:24:24Z
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.
Funding Details: Science Foundation Ireland
Type of material: Journal Article
Publisher: Elsevier
Journal: Theoretical Computer Science
Volume: 410
Issue: 4-5
Start page: 443
End page: 450
Copyright (published version): 2008 Elsevier B.V.
Keywords: Universal Turing machineSmall universal Turing machineSimple universal Turing machinesComputational complexityPolynomial timeTag systemsCellular automata
Subject LCSH: Turing machines
Computational complexity
Cellular automata
DOI: 10.1016/j.tcs.2008.09.051
Other versions:
Language: en
Status of Item: Peer reviewed
Appears in Collections:Computer Science Research Collection

Show full item record

Citations 10

Last Week
Last month
checked on Feb 18, 2019

Page view(s) 20

checked on May 25, 2018

Download(s) 50

checked on May 25, 2018

Google ScholarTM



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.