<p>It depends in which sense you mean "undecidable".</p>

<p>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.</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Universal_Turing_machine" rel="noreferrer">universal Turing machine</a> $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.</p>

<p>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.</p>

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

<p>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.</p>

CC BY-SA 4.0
2018-05-23T04:35:58.730Z
For the smallest Turing Machine known to be independent of ZFC see https://arxiv.org/abs/1605.04343 (and the corresponding post https://www.scottaaronson.com/blog/?p=2725)
didest
CC BY-SA 4.0
2018-05-22T11:26:16.993Z
2018-05-22T11:32:41.857Z
2018-05-22T11:32:41.857Z
Denis
<p>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.</p>

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

CC BY-SA 4.0
2018-05-22T11:24:12.900Z
Can you elaborate more? Given an input x, how can one decide M halts on x or not?
Vincent J. Ruan
CC BY-SA 4.0
2018-05-22T09:23:44.953Z
2018-05-22T09:23:44.953Z
Gamow
<p>The question is on the title.</p>

<p>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).</p>

<p>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.</p>

CC BY-SA 4.0
2021-12-25T16:33:37.213Z
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.
Neal Young
CC BY-SA 4.0
2023-02-25T22:11:43.333Z
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.
polcott
<turing-machines><halting-problem><universal-turing-machines>
For a specific unbounded Turing machine, is its Halting problem undecidable?
Vincent J. Ruan
# For a specific unbounded Turing machine, is its Halting problem undecidable?

(Asked by: username_0 on 2018-05-22)

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.

**Tags:** turing-machines, halting-problem, universal-turing-machines

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_3 on 2018-05-22. Score: 9 | Accepted answer

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 username_5, 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](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_4**: For the smallest Turing Machine known to be independent of ZFC see https://arxiv.org/abs/1605.04343 (and the corresponding post https://www.scottaaronson.com/blog/?p=2725)  

---

### Answer by username_5 on 2018-05-22. Score: 6

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.

> **Comments:**
> **username_0**: Can you elaborate more? Given an input x, how can one decide M halts on x or not?  

---

