A Turing machine resisting isolated bursts of faults
OA Version
Citation
Çapuni I., Gács P. (2012) A Turing Machine Resisting Isolated Bursts of Faults. In: Bieliková M., Friedrich G., Gottlob G., Katzenbeisser S., Turán G. (eds) SOFSEM 2012: Theory and Practice of Computer Science. SOFSEM 2012. Lecture Notes in Computer Science, vol 7147. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-27660-6_14
Abstract
We consider computations of a Turing machine under noise that causes consecutive violations of the machine’s transition function. Given a constant upper bound β on the size of bursts of faults, we construct a Turing machine M(β) subject to faults that can simulate any fault-free machine under the condition that bursts not closer to each other than V for an appropriate V = O(β).