For a specific unbounded Turing machine, is its Halting problem undecidable?

Question

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.

Answer 1

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.

Answer 2

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.