News Archives

[Colloquium] Simple universal devices and computational complexity

October 27, 2006

Watch Colloquium: 

Quicktime (126 Meg) 
AVI (311 Meg)


  • Date: Friday, October 27, 2006 
  • Time: 1 pm — 2:15 pm 
  • Place: ME 218

Damien Woods
Boole Centre for Research in Informatics, School of Mathematics
University College Cork, Ireland

Abstract It has been an open question for forty years as to whether the smallest known universal Turing machines of Minsky, Rogozhin and others are efficient (polynomial time) simulators of Turing machines. These are some of the most intuitively simple computational devices and previously the best known simulations were exponentially slow. We show that these machines are indeed efficient simulators. As a related result we also show that Rule 110, a famous elementary cellular automaton, is efficiently universal.

This is joint work with Turlough Neary from NUI Maynooth, Ireland.

Bio Damien Woods works on algorithms and computational complexity theory for optical computers, biomolecular computers, cellular automata, small universal Turing machines, and other computational devices