Church-Turing Thesis

Learn about the Church-Turing thesis and its background.


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×ZZf: 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(x,p)=1f(x,p)=1 for some given xx. Since ff is arbitrary, we have no choice but to attempt to “solve” this problem by creating a brute-force function, like the function gg in the following Python code:

Get hands-on with 1200+ tech skills courses.