Share and Export
Share and Export
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
DW_small weakly.pdf
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 |
| Related URLs: | |
| URI: | https://mural.maynoothuniversity.ie/id/eprint/15730 |
| 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
Downloads per month over past year
