On the time complexity of 2-tag systems and small universal Turing machines

Abstract

We show that 2-tag systems efficiently simulate Turing machines. 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 a forty year old result in the area of small universal Turing machines.

Slightly expanded and updated from conference version

Cited by in corpus (8)

• A Concrete View of Rule 110 Computation
• Accepting Hybrid Networks of Evolutionary Processors with Special Topologies and Small Communication
• Small weakly universal Turing machines
• Program-Size Versus Time Complexity, Speed-Up and Slowdown Phenomena in Small Turing Machines
• Undecidability in binary tag systems and the Post correspondence problem for four pairs of words
• The complexity of small universal Turing machines: a survey
• Small Turing universal signal machines
• On the computational complexity of spiking neural P systems