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.