2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What would be the language whose decidability you want to determine? $\endgroup$
    – Steven
    Commented Apr 2, 2020 at 1:09
  • $\begingroup$ The first sentence seems false -- it is not undecidable when we fix the Turing machine $M$. In fact, for many specific Turing machines, it is decidable. For example for any decider, the problem is trivially decidable as you can just output "true". $\endgroup$
    – Caleb Stanford
    Commented Apr 2, 2020 at 2:36

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Thank you for your answer! It seems like I was indeed somewhat confused about the definitions but I think it is more clear to me now. $\endgroup$
    – Heisenberg
    Commented Apr 2, 2020 at 22:01
  • $\begingroup$ I've also realized that I didn't ask the question that I really wanted to. My question would be the following: is it true that for every fixed $M_0$ Turing machine and every fixed $w_0$ input, an $M_{M_0, w_0}$ Turing machine can be constructed where the possible inputs are ($M, w$) machine-input pairs, and for the ($M_0, w_0$) pair, the output is "1" if $M_0$ will halt on $w_0$ and "0" if $M$ will not halt on $w_0$? ($M_{M_0, w_0}$ can give false answers for other pairs, it is not demanded that it has to run correctly for every pair.) $\endgroup$
    – Heisenberg
    Commented Apr 2, 2020 at 22:19
  • $\begingroup$ I made a typo in my previous comment: the ending of the penultimate sentence would be "... and "0" if $M_0$ will not halt on $w_0$?" of course. $\endgroup$
    – Heisenberg
    Commented Apr 2, 2020 at 22:50
  • $\begingroup$ @T.Christopher For your new problem, there is still effectively only one input :) Your $M_{M_0, w_0}$ only has to be correct on one input, so it is easy to solve the problem just by always accepting or always rejecting (whichever is correct). $\endgroup$
    – Caleb Stanford
    Commented Apr 2, 2020 at 23:01
  • $\begingroup$ In order to have an interesting problem, there need to be infinitely many inputs that matter (you should need to give a different answer depending on the input). $\endgroup$
    – Caleb Stanford
    Commented Apr 2, 2020 at 23:02

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.