Wed Aug 1 10:32:57 EDT 2007

Small Turing Machine paper on Arxiv

--

File this under "to-read":

Small weakly universal Turing machines

Turlough Neary, Damien Woods

(Submitted on 30 Jul 2007)

Abstract: We give small universal Turing machines with state-sym-
bol 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  simu-
late Rule 110 and are currently the smallest known weakly univer-
sal Turing machines.


--
Powered by vee
Copyright © 2006-2010