Search⌘ K
Home
Courses
Theory of Computation

Church-Turing Thesis

Learn about the Church-Turing Thesis, which states that any mechanical computation can be performed by a Turing machine. Understand key concepts like halting, total and partial functions, recursive and recursively enumerable languages. Explore how Turing machines model computation and their significance in computer science.

We'll cover the following...

Halting

Whether a TM\text{TM} halts or not is a feature of the machine itself and its input. We emphasize the notion of halting because some TM\text{TM}s do not halt on some inputs. This is not a matter of “bad programming,” but rather of the nature of certain computations.

To illustrate, consider an arbitrary function, f:Z×Z→Zf: Z\times Z\to Z, that takes two integer parameters and returns an integer. Suppose that we are interested in the smallest nonnegative integer, pp, for which f ...