Church-Turing Thesis

Halting

Whether a $\text{TM}$ halts or not is a feature of the machine itself and its input. We emphasize the notion of halting because some $\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\times Z\to Z$, that takes two integer parameters and returns an integer. Suppose that we are interested in the smallest nonnegative integer, $p$, for which $f(x,p)=1$ for some given $x$. Since $f$ is arbitrary, we have no choice but to attempt to “solve” this problem by creating a brute-force function, like the function $g$ in the following Python code: