Some results that show that basic toggle networks cannot simulate all
finite state automata will be presented and discussed. An enhanced
version of the machine model is given (in three equivalent
formulations) and shown to have **PSPACE**-complete halting problem and
to be powerful enough to simulate arbitrary finite state automata.

To get to campus, take the train from Birmingham New Street to the University stop (7 minutes).

School of Mathematics

University of Birmingham

http://web.mat.bham.ac.uk/R.W.Kaye/

Dr Walter Dean

Department of Philosophy

University of Warwick

http://go.warwick.ac.uk/whdean