Recent News
Making waves: Undergraduate combines computer science skills, love of water for summer internship
April 9, 2024
Inaugural School of Engineering Teaching Innovation Fellows selected
February 2, 2024
UNM computer scientist wins NSF CAREER Award to optimize supercomputer performance
February 1, 2024
Hand and Machine Lab’s Experimental Clay Exhibition closing celebration Nov. 17
November 15, 2023
News Archives
[Colloquium] Simple universal devices and computational complexity
October 27, 2006
- 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