Neary, Turlough and Woods, Damien (2006) Small fast universal Turing machines. Theoretical Computer Science, 362. pp. 171-195. ISSN 0304-3975
|
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: | https://doi.org/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 |
| URI: | |
| 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
Altmetric
Altmetric