The complexity of small universal Turing machines

Damien Woods: We present some work concerned with small universal Turing machines, tag systems, and cellular automata. In particular we focus on program size and time complexity results.

For example, it has been an open question for some time as to whether the smallest known universal Turing machines of Minsky, Rogozhin, Baiocchi and Kudlek are efficient (polynomial time) simulators of Turing machines. Previously, the best known simulations were exponentially slow. We discuss recent work that shows that these machines are indeed efficient simulators. As a related result we also find thatRule 110, a well-known cellular automaton, is also efficiently universal. From the point of view of universal program-size we present new results on three variants of the the one tape Turing machine model: standard, semi-weak and weak. These machines are some of the most intuitively simple general purpose computational devices.

This is joint work with Turlough Neary.