Published: 25th June 2009
DOI: 10.4204/EPTCS.1
ISSN: 2075-2180

EPTCS 1

Proceedings International Workshop on
The Complexity of Simple Programs
Cork, Ireland, 6-7th December 2008

Edited by: Turlough Neary, Damien Woods, Tony Seda and Niall Murphy

Preface
Turlough Neary, Damien Woods and Anthony K. Seda
1
Playing With Population Protocols
Olivier Bournez, Jérémie Chalopin, Johanne Cohen and Xavier Koegler
3
Simplicity via Provability for Universal Prefix-free Turing Machines
Cristian S. Calude
16
Complexity through the Observation of Simple Systems
Matteo Cavaliere and Peter Leupold
22
A Concrete View of Rule 110 Computation
Matthew Cook
31
On the boundaries of solvability and unsolvability in tag systems. Theoretical and Experimental Results.
Liesbeth De Mol
56
Limitations of Self-Assembly at Temperature One (extended abstract)
David Doty, Matthew J. Patitz and Scott M. Summers
67
Small Turing universal signal machines
Jérôme Durand-Lose
70
Communications in cellular automata
Eric Goles, Pierre-Etienne Meunier, Ivan Rapaport and Guillaume Theyssier
81
Multi-Head Finite Automata: Characterizations, Concepts and Open Problems
Markus Holzer, Martin Kutrib and Andreas Malcher
93
Computational Power of P Systems with Small Size Insertion and Deletion Rules
Alexander Krassovitskiy, Yurii Rogozhin and Sergey Verlan
108
Some Considerations on Universality
Manfred Kudlek
118
Busy beavers gone wild
Grégory Lafitte
123
The Pagoda Sequence: a Ramble through Linear Complexity, Number Walls, D0L Sequences, Finite State Automata, and Aperiodic Tilings
Fred Lunnon
130
A Divergence Formula for Randomness and Dimension (Short Version)
Jack H. Lutz
149
On the injectivity of the global function of a cellular automaton in the hyperbolic plane (extended abstract)
Maurice Margenstern
153
A General Notion of Useful Information
Philippe Moser
164
On acceptance conditions for membrane systems: characterisations of L and NL
Niall Murphy and Damien Woods
172
Representing a P-complete problem by small trellis automata
Alexander Okhotin
185
Intrinsically Universal Cellular Automata
Nicolas Ollinger
199
A Particular Universal Cellular Automaton
Nicolas Ollinger and Gaétan Richard
205
Self-Assembly of Infinite Structures
Matthew J. Patitz and Scott M. Summers
215
Computational Processes and Incompleteness
Klaus Sutner
226
New Choice for Small Universal Devices: Symport/Antiport P Systems
Sergey Verlan and Yurii Rogozhin
235

Preface

The International Workshop on The Complexity of Simple Programs was hosted at University College Cork on the 6th and 7th of December, 2008. All speakers were invited. We were delighted by the positive response to the workshop and we would like to thank the speakers and their co-authors for submitting such an interesting selection of topics and results. All of the papers went through a thorough peer-review process and we thank the anonymous reviewers for their outstanding efforts. We would also like to acknowledge the valuable contribution of Leonid A. Levin who attended the workshop and presented joint work with Gene Itkis on simple self-organizing networks. This work is from their paper "Flat Holonomies on Automata Networks" which is not in this volume but may be found here.

As can be seen from this volume, the topics and results presented at the meeting have a common thread that weaves through a large number of computational paradigms and ideas. However at the core, many of the same concerns are being addressed. One of the motivations for the meeting was to give an opportunity for the cross-fertilisation and communication of ideas and techniques, and to provide a starting-point for future collaborations.

Given the subject matter of the meeting, it is indeed fitting that it was generously sponsored by the Boole Centre for Research in Informatics (BCRI) here at University College Cork. BCRI is an ambitious project bringing together the expertise of the School of Mathematics, Applied Mathematics and Statistics and the Department of Computer Science to carry out interdisciplinary research under the banner of Informatics. The Boole Centre represents the interface between the two disciplines and provides the motivation for the link with the name of George Boole, who was the first Professor of Mathematics at the former Queen's College, Cork. We are deeply indebted to BCRI, and in particular to its co-directors John Morrison and Pat Fitzpatrick, for providing generous financial support for the meeting. Without this support the meeting could not have happened, and we hope this volume represents a fitting token to the generosity of BCRI.

We would like to give a very special mention to Maureen Dwane. Maureen did splendid work in the organisation of the workshop. Her efforts were well above the call of duty and we thank her for a job well-done. A sincere thanks goes to Niall Murphy for doing a great job on compiling the papers for this volume, and to Martin Flemming for valuable technical assistance during the workshop. Finally, we would like to thank EPTCS, in particular Rob van Glabbeek and Lane A. Hemaspaandra, for their help and for enabling us to bring this proceedings volume to a wide audience.

Turlough Neary
Damien Woods
Anthony K. Seda

Co-chairs
Cork, May 2009