BCRI































International Workshop on
The Complexity of Simple Programs


University College Cork, Ireland
December 6th and 7th, 2008


Scope

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.

Invited speakers
Olivier Bournez
Cristian S. Calude
Matteo Cavaliere
Matthew Cook
Liesbeth De Mol
Jèrôme Durand-Lose
Manfred Kudlek
Martin Kutrib
Grégory Lafitte
Leonid Levin
Jack Lutz
Fred Lunnon
Maurice Margenstern
Philippe Moser
Niall Murphy
Nicolas Ollinger
Alexander Okhotin
Matt Patitz
Ivan Rapaport
Gaétan Richard
Yurii Rogozhin
Scott Summers
Klaus Sutner
Sergey Verlan