Seminar of the laboratory "Eroders". Speaker: Peter Gacs
On April 19, 2019 Peter Gacs will give a lecture "Eroders".
Address: Faculty of computer science HSE, Kochnovsky proezd, 3.
If you need a pass to the building, please contact the manager of the laboratory Dina Chernyshova: email@example.com.
This talk is about cellular automata on a finite-dimensional lattice---a certain kind that has special interest for error correction. A state 0 is distinguished, and a cellular automaton is called an ''eroder'' if it eliminates any finite island of non-0s. We restrict attention to cellular automata whose state set is ordered with 0 being minimal, and whose transition rule is monotonic. (For example majority vote over some neighbors.) A classical result of Toom characterizes all 2-state eroders (in any dimension). It also shows that such eroders erode in linear time, and resist (low random) noise. (The latter was key to building the simplest known construction of a reliable computation model.)Here I will report on work (some of it old by Galperin and Toom, some of it new, joint with Ilkka Törmä and Mathieu Hilaire) trying to extend these results to more than 2 states. In one dimension, all eroders erode in linear time, but not all resist noise. In 2 dimensions and 3 states, some eroders need more than linear time, and we don't even know whether the eroder property is decidable.
Characterizing eroders that resist noise (in any dimension) seems easier than to characterize just eroders (they all erode in linear time).