Neary, Turlough and Woods, Damien (2009) Small weakly universal Turing machines. In: Fundamentals of Computation Theory. Springer Verlag, pp. 267-273. ISBN 3-642-03408-X

Preview

Download (429kB) | Preview

Abstract

We give small universal Turing machines with state-symbol pairs of (6,2), (3,3) and (2,4). These machines are weakly universal, which means that they have an infinitely repeated word to the left of their input and another to the right. They simulate Rule 110 and are currently the smallest known weakly universal Turing machines. Despite their small size these machines are efficient polynomial time simulators of Turing machines.

Item Type:	Book Section
Keywords:	Turing Machine; Universal Machine; Universal Turing Machine; Tape Head; Elementary Cellular Automaton;
Academic Unit:	Faculty of Science and Engineering > Computer Science Faculty of Science and Engineering > Research Institutes > Hamilton Institute
Item ID:	15730
Depositing User:	Damien Woods
Date Deposited:	23 Mar 2022 12:47
Publisher:	Springer Verlag
Refereed:	Yes
URI:	Publisher
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads