Halting problem for fixed Turing machine and fixed input

Question

It is known that the halting problem is undecidable even when we fix either the Turing machine $M$ or the input $w$.

What if we fixed both the machine and the input? I.e., is it decidable for every fixed Turing machine $M_0$ and every fixed input $w_0$ that $M_0$ will halt on $w_0$ as input?

Answer 1

It is known that the halting problem is undecidable even when we fix either the Turing machine $M$ or the input $w$.

You have to be more careful about this statement. It's not true for any fixed Turing machine $M$ that the halting problem $\text{HALT}_M$ (deciding on input $w$ if $M$ halts on $w$) is undecidable. For example, if $M$ is a machine that always halts, we can easily decide $\text{HALT}_M$ just by outputting "yes".

What you probably meant to say is the following facts, which are true:

1. There exists a Turing machine $M$ such that the problem $\text{HALT}_M$ (deciding on input $w$ if $M$ halts on $w$) is undecidable.

2. For all words $w$, the problem $\text{HALT}_w$ (deciding on input $M$ if $M$ halts on $w$) is undecidable.

In particular for fact 1, we can take $M$ to be the universal Turing machine.

What if we fixed both the machine and the input? I.e., is it decidable for every fixed Turing machine $M_0$ and every fixed input $w_0$ that $M_0$ will halt on $w_0$ as input?

Yes, the problem becomes trivially decidable. Define the language $\text{HALT}_{M_0, w_0}$ to be the problem of deciding whether $M_0$ halts on $w_0$. But notice that this problem no longer has any input that the answer depends on, as both things that the answer might depend on ($M_0$ and $w_0$) are now fixed, i.e. part of the language definition, not part of the input. That means the answer is just "yes" or "no". So we can trivially decide this problem either by using a program which always says "yes", or a program which always says "no".

This is a common pitfall about decidability: it is only useful to ask whether a problem is decidable or not when the number of possible inputs is infinite. If there are only finitely many possible inputs, then all problems become decidable. You have asked whether a problem with only 1 possible input (the empty input) is decidable, and the answer to that is always yes.