next up previous contents
Next: Running Time and Complexity Up: The Classical Computer Previous: Turing Machines   Contents

Church-Turing Thesis

This bold claim, that any computer is essentially equivalent to a Turing machine grew out of contemporaneous work by Alonzo Church and Alan Turing, and is variously referred to as Church's Thesis, the Church-Turing Thesis, the Turing-Church thesis, the Church-Turing conjecture, and Turing's thesis. There are several equivalent formulations of the thesis stated at different times and to different degrees of rigor, but the central idea is that:

Every effectively calculable function can be produced by a Turing machine.

The claim here is that anything which one would like to compute, which one reasonably could compute (for instance given pen and paper, and enough time), are precisely those things which a Turing machine can compute.

The Church Turing thesis is perhaps best understood as a definition of the types of functions that are calculable in the real world - not as a theorem to be proven. As evidence for the suitability of this as a definition, multiple (indeed every one considered to far) distinct models of computation have been shown to be equivalent to the Turing model with regard to what functions they can compute.

Beyond the mere ability of a computing device to calculate a function is the consideration of how long it would take to do so. This notion is generalized by the time complexity of a given algorithm, which considers the number of steps or operations an algorithm would have to perform relative to the length of the input in order to compute the function.

There are various extensions of the Church-Turing thesis that address the relative efficiency of different models of computation, such as the Complexity-Theoretic Church-Turing Thesis states that:

A Turing machine can efficiently simulate any realistic model of computation.

Here efficiently means a Turing machine can simulate any realistic model of computation with at most polynomial time expansion of the computation time or other resources (such as memory). This hypothesis may be viewed either as a definition of what a realistic model of computation is, or as a statement of fact (which may turn out to be false) about realistic models of computation. There are no known models of computation which are thought to be realizable that violate this thesis. The discovery of a model which did violate this thesis would likely be an astonishing breakthrough in the fields of computational complexity, computer science, and/or physics.

These theses gives us insight into the power of computing machines. If a computer theoretically can compute all the functions a Turing machine can compute (given enough memory and time) then it is as powerful as a Turing machine.

next up previous contents
Next: Running Time and Complexity Up: The Classical Computer Previous: Turing Machines   Contents
Matthew Hayward - Quantum Computing and Shor's Algorithm GitHub Repository