Abstract
dc:description.abstractThe 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 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.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy
- Level thesis:degree_level
- doctoral
- Discipline thesis:degree_discipline
- Computer Science
- Grantor dc:publisher
- Boston University
- Year dc:date.issued
- 2013
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Capuni, Ilir
Rights
dc:rights- Statement dc:rights
-
- PLEASE NOTE: Boston University Libraries did not receive an Authorization To Manage form for this thesis or dissertation. It is therefore not openly accessible, though it may be available by request. If you are the author or principal advisor of this work and would like to request open access for it, please contact us at open-help@bu.edu. Thank you.
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Dc Identifier Other
- (ALMA)contemp