Computers without batteries?
Rewriting cellular automata into block automata

Silvio Capobianco

Institute of Cybernetics

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.

Tarmo Uustalu
Last update 6.6.2009