CJTCS Volume 2013 Article 3

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 epok.edu.al

and

Peter Gács
Computer Science Department
Boston University
gacs AT bu.edu

March 27, 2013

Abstract

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) \).

The article: PDF (506 KB)
Source material: ZIP (834 KB)
BibTeX entry for this article (276 bytes)

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

DOI: 10.4086/cjtcs.2013.003

Licensed under a Creative Commons Attribution License

Article 2

Article 4

Volume 2013 [back]

Published articles