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, ...