Turing
machines are considered the most
general models of computation. Essentially, they can do whatever a computer
can do. They consist of a control unit, which at any step is in one of
finitely many different states, together with a tape divided into cells,
which is infinite in both directions. They have read and write capabilities
on the tape as the control unit moves left and right on the tape, changing
states depending on the tape symbol read. We first construct a Turing machine \(M_1\) that can simulate any other Turing machine even when it is subjected to some separated intervals of noise of bounded size that change its state and the cell where the head is positioned. Then, we build a hierarchy of simulations where machine \( M_1 \) simulates machine \(M_2\) which has the same program as \(M_1\). Machine \(M_2\) simulates machine \(M_3\) and so on. We don't lose universality in this way since each of these machines performs oblivious simulation of any 'given' machine \(G\)


Downloads


(The logo of the Fault Tolerant Virtual Turing Machine by I. Capuni) 

Copyright I. Capuni. Email for any questions.
Boston 2010