# Do the Turing machines involved in Chruch-Turing thesis have to halt on all the inputs?

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?

Thanks.

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.

• "The halting problem also falls in that category" Well, you have to be careful what you mean by "the halting problem." The partial function $\theta$ which takes in $e$ and (i) halts and outputs $0$ if $\Phi_e(e)$ halts and (ii) never halts if $\Phi_e(e)$ never halts is computable, but "the halting problem" usually refers to the set of indices of halting computations and the function corresponding to this is its characteristic function $\chi$ which is total and not computable. (cont'd) Oct 9 '18 at 13:15
• The first interpretation of CT would say that $\theta$, not $\chi$, is "informally computable" and in my opinion this is clearly true. Basically, the shift is in viewing CT as a characterization of informally algorithmic processes, and things like $\theta$ are in fact described perfectly well by such. Oct 9 '18 at 13:18