125 citations · 284 across the 20 of their papers we have counts for
Showing 2021Show all
3 papers · 1 filter
cs.CC2021★ 1 cited
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…
cs.FL2021★ 4 cited
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…
cs.IT2021★ 43 cited
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…