Peer-Reviewed Journal Details
Mandatory Fields
Neary, T;Woods, D
2006
October
Theoretical Computer Science
Small fast universal Turing machines
Published
21 ()
Optional Fields
362
171
195
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. (C) 2006 Elsevier B.V. All rights reserved.
AMSTERDAM
0304-3975
10.1016/j.tcs.2006.06.002
Grant Details