Back to search

Boston University

A fault-tolerant Turing machine

Abstract

dc:description.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 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

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Capuni, Ilir. A fault-tolerant Turing machine. doctoral thesis, Boston University, 2013. https://hdl.handle.net/2144/13608