125 citations · 284 across the 20 of their papers we have counts for
21 papers
Probabilistic cellular automata with Andrei Toom
Peter Gacs
Andrei Toom, who died in September 2022, contributed some of the most fundamental results on probabilistic cellular automata. We want to acquaint the reader with these and will als…
A reliable Turing machine
Ilir Çapuni, Peter Gács
We consider computations of a Turing machine subjected to noise. In every step, the action (the new state and the new content of the observed cell, the direction of the head moveme…
A new version of Toom's proof
Peter Gacs
There are several proofs now for the stability of Toom's example of a two-dimensional stable cellular automaton and its application to fault-tolerant computation. Simon and Berman…
Lecture notes on descriptional complexity and randomness
Peter Gacs
A didactical survey of the foundations of Algorithmic Information Theory. These notes are short on motivation, history and background but introduce some of the main techniques and…
Inequalities for space-bounded Kolmogorov complexity
Bruno Bauwens, Peter Gács, Andrei Romashchenko +1
There is a parallelism between Shannon information theory and algorithmic information theory. In particular, the same linear inequalities are true for Shannon entropies of tuples o…
Stable Multi-Level Monotonic Eroders
Péter Gács, Ilkka Törmä
Eroders are monotonic cellular automata with a linearly ordered state set that eventually wipe out any finite island of nonzero states. One-dimensional eroders were studied by Gal'…