It is well known that if some computing apparatus is Turing-complete, then the halting problem is undecidable for that computing apparatus. However, is it true that if the halting problem is undecidable for some computing apparatus, then it is Turing-complete?


Here's an artificial counterexample:

Define an apparatus "aTM" like a TM, except that any input word which does not start with the symbol $a$ is immediately rejected. For words which do start with $a$, the TM is run as usual (and can accept/reject as usual).

This is clearly not Turing complete since it can't recognize the language $\{b\}$, which is decidable by a TM. Still, the halting problem on aTMs is as hard as the halting problem for TMs.

  • $\begingroup$ In general, to define Turing-completeness you need to make use of an input-coding anyway, and the input coding here is obviously "preface with "a"". Thus, the model is Turing-complete. $\endgroup$ – Arno Nov 11 '18 at 16:47
  • $\begingroup$ @Arno The whole point of this model is to not do such coding, but to use the simplest coding "leave the input string" as it is. In this way it is not Turing complete (for a trivial reason) as the OP required. $\endgroup$ – chi Nov 11 '18 at 17:03
  • 1
    $\begingroup$ Alternatively, on input x the apparatus simulates the Turing machine encoded by x and, upon halting, outputs the xor of the bits of x. Clearly not a Turing complete apparatus (since it only computes one function), but its halting problem is trivially just as hard as that for Turing machines. $\endgroup$ – Yonatan N Dec 11 '18 at 18:39

You can think of weaker model for example finite-state automaton, or a turing machine with space bound of $O(n)$. this models are not turing-complete and can't decide halting problem.

  • 2
    $\begingroup$ I think you've misunderstood the question. Each model of computation has its own halting problem and the question is (I'm fairly sure) asking whether you can have a model $M$ of computation that is not complete but for which the halting problem for $M$ is undecidable (presumably, undecidable by Turing machines). For example, the halting problem for DFAs is decidable: they always halt. Your answer addresses models $M$ of computation that can't decide the Turing machine halting problem. But even Turing machines can't do that, so weaker models obviously can't. $\endgroup$ – David Richerby Dec 11 '18 at 16:08
  • $\begingroup$ yes it is so correct and I was mistaken. $\endgroup$ – Mohsen Ghorbani Dec 11 '18 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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