Friday, 5 June 2009, 14:00 (note the unusual weekday)
Cybernetica Bldg (Akadeemia tee 21), room B101
Slides from the talk [pdf]
Abstract: Given a cellular automaton (CA) it is conceptually straightforward to realize a physical implementation of it. What is to be done, is to place on the nodes of a space-time grid several identical many-inputs, one-output devices. Each output shall be then replicated, and one copy sent to each element the node is a neighbor of.
However, the signal cancellation and replication occurring in CA must take, with respect to the balance of the CA itself, a toll in terms of loss of free energy. A real system constructed according to a CA recipe will require a power supply for performing the signal replications and cancellations; and consequently, a heat sink to dissipate the excess heat.
It is thus of interest to be able to construct other kinds of systems which can reproduce the same global dynamics of a given CA, yet follow a construction rule which does not require the signal replication phase. Block automata, where the space is divided into blocks evolving independently, are such a kind of system.
The subject of this talk will be the state of the art of re-writing one-dimensional CA as compositions of block automata. For reversible CA, a theorem by J. Kari is stated and discussed. For non-surjective ones, a technique by T. Toffoli with the speaker and P. Mentrasti is described in detail. Finally, suggestions and hypotheses for extending these results to arbitrary dimension will be presented.