Share and Export
Share and Export
Neary, Turlough and Woods, Damien (2006) Small fast universal Turing machines. Theoretical Computer Science, 362. pp. 171-195. ISSN 0304-3975
Preview
Woods_SmallFast_2006.pdf
Download (379kB) | Preview
Abstract
We present deterministic polynomial time universal Turing machines (UTMs) with state-symbol pairs of (3,11), (5,7), (6,6), (7,5) and (8,4). These are the smallest known UTMs that simulate Turing machines in polynomial time.
| Item Type: | Article |
|---|---|
| Keywords: | Universality; Small universal Turing machine; Computational complexity; Polynomial time; |
| Academic Unit: | Faculty of Science and Engineering > Computer Science Faculty of Science and Engineering > Research Institutes > Hamilton Institute |
| Item ID: | 12421 |
| Identification Number: | 10.1016/j.tcs.2006.06.002 |
| Depositing User: | Damien Woods |
| Date Deposited: | 17 Feb 2020 14:42 |
| Journal or Publication Title: | Theoretical Computer Science |
| Publisher: | Elsevier |
| Refereed: | Yes |
| Related URLs: | |
| URI: | https://mu.eprints-hosting.org/id/eprint/12421 |
| 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
