Fault Tolerant Turing Machine

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.

Little is known about the behavior and the power of Turing machines when their operation is subject to random noise that can change the state of a machine to an arbitrary one and the content of the cell where the head is positioned.
The main open question is if a machine that operates under some noise can perform any computation reliably.
 

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 'bursts' paper
  • The simulator (Windows version)
  • The Ph.D. thesis
  •  

     

       
     

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

     
         

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