0
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The Church-Turing thesis is an informal notion so it is not strange to see different authors taking slightly different positions.

To me, the second definition makes a bit more sense: CT tries to characterize "functions that are calculable in all cases", and for instance, we don't consider lets say, second order unification computable. The halting problem also falls in that category so I really wonder what do the authors mean.

Some interesting recent discussion about CT can be found in this thread: http://www.cs.nyu.edu/pipermail/fom/2016-August/020027.html

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks. I think the statements of Church-Turing thesis in all the references should be the same or equivalent. So I am confused whether the Turing machines are required to halt at all the inputs in the statement in the first book. $\endgroup$
    – Tim
    Commented Oct 3, 2016 at 2:03
  • $\begingroup$ After reading a bit of my copy of Ullman's, IMVHO they pose the CTT as the link between Turing machines and "algorithm", in the sense that if there is not algorithm showing something then there is not TM neither. IMO asserting equivalence of undecidability is equivalent to the first formulation of asserting equivalence in the decidable cases, as long as we reason classically of course. $\endgroup$
    – ejgallego
    Commented Oct 3, 2016 at 11:33
  • $\begingroup$ "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) $\endgroup$
    – Noah Schweber
    Commented Oct 9, 2018 at 13:15
  • $\begingroup$ 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. $\endgroup$
    – Noah Schweber
    Commented Oct 9, 2018 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.