Numerous results for simple computationally universal systems are presented, with a particular focus on small universal Turing machines. These results are aimed at finding the simplest universal systems. We add a new aspect to this area by examining trade-offs between the simplicity of universal systems and their time/space computational complexity.
Improving on the earliest results, we give the smallest known universal Turing machines that simulate Turing machines in 𝒪(t2) time. They are also the smallest known machines where direct simulation of Turing machines is the technique used to establish their universality. This result gives a new algorithm for small universal Turing machines.
We show that the problem of predicting t steps of the 1D cellular automaton Rule 110 is P-complete. As a corollary, we find that the small weakly universal Turing machines of Cook and others run in polynomial time, an exponential improvement on their previously known simulation time overhead. These results are achieved by improving the cyclic tag system simulation time of Turing machines from exponential to polynomial.
A new form of tag system, which we call a bi-tag system, is introduced. We prove that bi-tag systems are universal by showing they efficiently simulate Turing machines. We also show that 2-tag systems efficiently simulate Turing machines in polynomial time. As a corollary, we find that the small universal Turing machines of Rogozhin, Minsky, and others simulate Turing machines in polynomial time. This is an exponential improvement on the previously known simulation time overhead and improves on a 40-year-old result.
We present new small polynomial time universal Turing machines with state-symbol pairs of (5, 5), (6, 4), (9, 3), and (15, 2). These machines simulate bi-tag systems and are the smallest known universal Turing machines with 5, 4, 3, and 2 symbols, respectively. The 5-symbol machine uses the same number of instructions (22) as the current smallest known universal Turing machine (Rogozhin’s 6-symbol machine).
We give the smallest known weakly universal Turing machines. These machines have state-symbol pairs of (6, 2), (3, 3), and (2, 4). The 3-state and 2-state machines are very close to the minimum possible size for weakly universal machines with 3 and 2 states, respectively.
