International Workshop on
The Complexity of Simple Programs
University College Cork, Ireland
December 6th and 7th, 2008
The focus of the workshop is on models of computation, computational complexity, and decidability.
The following areas are of particular interest.
Universality in simple models of computation and the computational complexity of problems associated with such models.
Reductions between properties of simple models and well-known unsolved problems (3n+1, etc.).
Decidability results that provide lower bounds for the simplest possible computationally universal models.
Results on these topics have already been found for a number of models such as Turing machines, Post systems, Tag systems, cellular automata, neural networks, grammars and dynamical systems.
The workshop will continue the work in this area.
Cristian S. Calude
Liesbeth De Mol