Chicago Journal of Theoretical Computer Science

Volume 2013

Article 3

Published by the Department of Computer Science, The University of Chicago.

A Turing Machine Resisting Isolated Bursts Of Faults

Ilir Çapuni
Computer Engineering Department, Epoka University
Tirana, ALbania
icapuni AT


Peter Gács
Computer Science Department
Boston University
gacs AT

March 27, 2013


We consider computations of a Turing machine under noise that causes violations of the transition function. Given an upper bound \( \beta \) on the size of bursts of faults, we construct a Turing machine \( M(\beta) \) subject to faults that can simulate any fault-free machine under the condition that the time between bursts is lowerbounded by \( O(\beta^2) \).

Submitted April 7, 2012, revised March 2, 2013, published March 27, 2013.

DOI: 10.4086/cjtcs.2013.003

[] Article 2 [] Article 4
[back] Volume 2013 [back] Published articles
[CJCTS home]