The following is Church-Turing Thesis from two books.
Is it correct that
- The first book seems to say that the Turing machines involved in the thesis may or may not halt on a given input,
- the second book says that the Turing machines involved in the thesis must halt on all the inputs?
Do the two books contradict each other? Why?
From Ullman and Hopcroft's Introduction to Automata Theory, Language, and Computation 1ed 1979
Note that one TM may compute a function of one argument, a different function of two arguments, and so on. Also note that if TM M computes function f of k arguments, then f need not have a value for all different k-tuples of integers. ...
In a sense,
the partial recursive functions are analogous to the r.e. languages, since they are computed by Turing machines that may or may not halt on a given input.
The total recursive functions correspond to the recursive languages, since they are computed by TM's that always halt.
The assumption that the intuitive notion of "computable function" can be identified with the class of partial recursive functions is known as Church's hypothesis or the Church-Turing thesis.
From Lewis and Paradimitriou's Elements of The Theory of Computation
However, we have also seen in the last chapter that not all Turing ma machines deserve to be called "algorithms:" We argued that Turing machines that semidecide languages, and thus reject by never halting, are not useful computational devices, whereas Turing machines that decide languages and compute functions (and therefore halt at all inputs) are. Our notion of an algorithm must exclude Turing machines that may not halt on some inputs.
We therefore propose to adopt the Turing machine that halts on all inputs as the precise formal notion corresponding to the intuitive notion of an "algorithm". Nothing will be considered an algorithm if it cannot be rendered as a Turing machine that is guaranteed to halt on all inputs, and all such machines will be rightfully called algorithms. This principle is known as the Church-Turing thesis.