3
$\begingroup$

The question is on the title.

To make it clearer, I state some facts. We all know that the Halting problem with input is undecidable. It leads to, given a specific input (e.g. empty string), the corresponding Halting problem with input is also undecidable. Moreover, given a time or space bounded Turing machine M, the Halting problem of that specific M is decidable (on input x, save all of the configurations of M on x to check if M loops on x).

From there, I naturally have this question. I believe the problem is undecidable (because, otherwise, there seems to be no way to compute if M loops or not). But I haven't proved it yet.

$\endgroup$
2
  • $\begingroup$ What do you mean exactly by "the halting problem for a specific machine $M$"? Do you mean the problem of deciding the language $L = \{x : M \text{ halts on input } x\}$? Yes, that's undecidable for some $M$ (e.g. for a universal TM). If you mean the problem "Does $M$ halt when run on blank tape", note that undecidable by definition (in TCS) at least is a property of languages. It doesn't make sense to ask whether a given question (one that does not implicitly define a decision problem) is undecidable. $\endgroup$
    – Neal Young
    Dec 25, 2021 at 16:33
  • $\begingroup$ I have shown that the previously "impossible" input is correctly determined to be non-halting in the Peter Linz proof below. This same reasoning applies to every instance of the halting theorem. $\endgroup$
    – polcott
    Feb 25, 2023 at 22:11

2 Answers 2

9
$\begingroup$

It depends in which sense you mean "undecidable".

If you evaluate $M$ on the empty input, and want only to find a yes/no answer, then the algorithmic problem is trivially decidable, as answered by Gamow, since either the algorithm outputting "Yes", or the one outputting "No" is correct. you don't have to know which one is correct to prove decidability: there exists an algorithm solving the problem.

If your Halting problem on a specific $M$ still accepts the input $x$ of the machine as input of the problem, then it is in general undecidable. This is because it is equivalent to the general Halting problem by using a universal Turing machine $M_{univ}$, and giving as input the encoding of the Turing machine you want to test. For simpler machines, of course, this problem can become decidable.

But coming back to the first version with no input, interestingly, there are Turing Machines for which the answer is actually mathematically undecidable. This means that the machine does not halt, but you cannot prove it using your usual mathematical theory (say ZFC for instance). To see this, consider a machine looking for a proof of contradiction in ZFC, and halting when it finds one. If ZFC is not contradicatory, the machine won't halt. But by Gödel's second incompleteness theorem, you cannot prove that this machine won't halt, since this would amount to prove there is no proof of contradiction in ZFC.

Remark that if the machine halts, then it is always possible to prove it, by exhibiting the full run of the machine.

So in my opinion, the answer to your question is: "the Halting problem can be undecidable for a specific Turing machine, even with no input", but we have to be precise about the meaning of "undecidable" here: it is in the sense of mathematical undecidability, i.e. independent of the axioms.

$\endgroup$
1
6
$\begingroup$

For every concrete Turing machine $M$, the halting problem (Problem $P_M$ without input: "Does the Turing machine $M$ halt on the empty input $\varepsilon$?") is decidable.

The corresponding decision algorithm is either the algorithm that outputs "Yes" and halts, or the algorithm that outputs "No" and halts.

$\endgroup$
1
  • $\begingroup$ Can you elaborate more? Given an input x, how can one decide M halts on x or not? $\endgroup$ May 22, 2018 at 11:24

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.