## Computers without batteries?

Rewriting cellular automata into block automata

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