Week 2, 7 October 2014 (16:00-18:00 Arts LR2)

Richard Kaye (Birmingham)

Title: Toggle machines

Abstract: I discuss finite state machines (toggle machines) made from networks of `toggles'---simple two state machines with one possible input and two possible output values. These are arguably the simplest building blocks one could use to make a `computer'. A toggle machine is a network of finitely many such toggles linked together in some fixed way. (`Feedback' is allowed.) The halting problem for toggle machines is defined. The natural algorithm to solve this problem is in polynomial space, but we show that in fact this halting problem is in N intersect coNP . I do not know if it is in P. A slightly more difficult decision problem for toggle machines will be shown to be NP-complete.

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.

About the seminar

The Midlands Logic Seminar was founded in 2011 and aims to cover all areas of mathematical logic, as well as related areas of theoretical computer science and philosophy of mathematics.

Study group

Our topic for Term 1 of 2014-2015 is the use of induction and heuristics in mathematical problem solving. We will be working through George Polya's book Induction and Analogy in Mathematics .


All meetings for Term 1 2014-15 will be Tuesday from 16:00-18:00 (study group 16:00-17:00, research talks 17:00-18:00) in room 310 of Watson Building (TBC) on the campus of the University of Birmingham.
  • campus map
  • google maps
    To get to campus, take the train from Birmingham New Street to the University stop (7 minutes).


    Dr Richard Kaye
    School of Mathematics
    University of Birmingham


    Dr Walter Dean
    Department of Philosophy
    University of Warwick