University College Cork, Ireland
4pm Tuesday 23rd October 2007
Room 2511, JCMB, King's Buildings
We survey some work concerned with small universal Turing machines, tag systems, and cellular automata. In particular we focus on time complexity and program-size 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 find that Rule 110, a well-known cellular automaton, is also efficiently universal. From the point of view of universal program-size we present a number of new small machines for the Turing machine model, and for the weak and semi-weak variants of the model. These machines are some of the most intuitively simple, yet general purpose, computational devices.
This is joint work with Turlough Neary.