A Turing machine resisting isolated bursts of faults

Thumbnail
Date Issued
2012
Publisher Version
10.1007/978-3-642-27660-6_14
Author(s)
Capuni, Ilir
Gacs, Peter
Share to FacebookShare to TwitterShare by Email
Export Citation
Metadata
Show full item record
Permanent Link
https://hdl.handle.net/2144/29419
Citation (published version)
Ç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(β).
Collections