Abstract:
The most natural question of reliable computation, in every computation model and noise model,is whether given a certain level of noise, a machine of that model exists that canperform arbitrarily complex computations under noise of that level. This question has positive answers for circuits, cellular automata, and recently for Turing machines.
Here, we raise the question of the existence of a random access machine that---with some moderate slowdown --- can simulate any other random access machine even if the simulator is subjected to constant size bursts of faults separated by a certain minimum number of steps from each other.
We will analyze and spell out the problems and difficulties that need to be addressed in such construction.
