Cellular automata with assumption-commitment schemes

Taivo Lints

Dept. of Computer Control
Tallinn University of Technology

Thursday, 23 October 2014, 14:00
Cybernetica Bldg (Akadeemia tee 21), room B101


Abstract: We explore the potential of using assumption-commitment schemes in a network of automata for preserving the behavior of the network as a whole, even if parts of the network fail.

For that, we propose a computational model that is based on elementary cellular automata. Any finite and closed deterministic cellular automaton is guaranteed to behave periodically after some potentially nonperiodic initial iterations, because sooner or later it finds itself in a state that has already occurred before and from that on it has to repeat the earlier behavior due to being deterministic. Now, if we give each cell sufficient memory and an ability to learn, they can notice that they periodically repeat a cycle of states, and they can then become autonomous and stop looking at their neighbors and just repeat their own memorized cycle. An external observer would not be able to notice any difference in the behavior of the CA after the cells became autonomous.

But if, then, there will be some disturbance (external interference or internal failure) in some cells, the difference becomes evident -- the CA with memorized behavior basically ignores the disturbance and continues as before. This can be interpreted either positively as resistance to failures, or negatively as failure to react to new information. We can associate a cost with each such local violation of the original ECA rules, and give each cell a limited resource ("energy", "health", etc.) for covering that cost, so that when the cell depletes its resource, it will, for example, stop functioning. We can also, optionally, add some mechanisms for restoring the resources ("energy", "health", etc.) in certain conditions. In such systems, interesting dynamics emerge.

Joint work with Eric Rothstein, Silvio Capobianco, Eduardo Garcia, Cristina Gomez, Nura Mukhtar, and Jose Ortega.


Tarmo Uustalu
Last update 21 October 2014