Informatisches Kolloquium Wintersemester 2007/2008

Montag, 10. Dezember 2007

Turlough Neary PhD
National University of Ireland, Maynooth

Small Universal Turing Machines and Computational Complexity

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. The Turing machines we present are smallest universal Turing machines for there respective state-symbol products. The 4-symbol machine is the first reduction in the number of states on the 4-symbol machine of Minsky 40 years. We also give a new machine the equals Rogozhin's record of 22 transition rules. These machines are some of the most intuitively simple, yet general purpose, computational devices.

Kontakt

Prof. M. Kudlek
Telefon 2410