## Ilir Capuni

## Abstract of PhD Thesis (Boston Univ., 2012)

### Title: Fault-tolerant Turing Machine

The Turing machine is the most studied universal model of computation.
This thesis
studies the question if there is a Turing machine that can compute
reliably even when
violations of its transition function occur independently of each other
with some small
probability.

In this thesis, we prove the existence of a Turing machine that with a
polynomial
overheadcan simulate any other Turing machine, even when it is subject to
faults of the
above type, thereby answering the question that was open for 25 years.

*Submitted to the Boston University Graduate School
of Arts and Science, December 2012.*

Back to Ilir Capuni's homepage.