A Fault-Tolerant Turing Machine: Ilir Capuni, PhD Defense

Starts:
1:00 pm on Tuesday, November 20, 2012
Ends:
3:00 pm on Tuesday, November 20, 2012
Location:
MCS 148
Abstract: 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 the 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 overhead - can 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. First Reader: Peter Gacs, Professor Second Reader: Steven Homer, Professor Third Reader: Mattthew Cook Chair of Examining Committee: Leonid Levin, Professor Additional Committee Member(s): Leonid Reyzin, Associate Professor