# Constructing a Turing machine which decides whether a fixed TM will halt on a fixed input or not

It is known that the halting problem is decidable for every fixed $$M_0$$ Turing machine and every fixed $$w_0$$ input.

My related 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 for which 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_0$$ 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 $$(M, w)$$ pair.)

• What do you mean by "can be constructed"? Do you want an algorithm that constructs $M_{M_0, w_0}$ or do you want to know whether $M_{M_0, w_0}$ exists? Commented Apr 2, 2020 at 23:15
• @Steven An algorithm would be preferred, but knowing if it exists or not would be also really helpful. Edit: I see from the conversation with 6005 on my previous question that either or machine that always accepts or another one which always rejects will be good. I don't know though that can we decide for every fixed $(M_0, w_0)$ pairs which is going to be the right choice? Commented Apr 2, 2020 at 23:22

Since $$M_0$$ and $$w_0$$ are fixed parameters of the problem, the answer is yes: for every fixed $$M_0$$ and $$w_0$$, there exists a Turing machine $$M_{M_0, w_0}$$ (depending on $$M_0$$ and $$w_0$$) such that, for the input $$(M_0, w_0)$$, $$M_{M_0, w_0}$$ returns $$1$$ if $$M_0(w_0)$$ halts and 0 otherwise.

In particular one such Turing machine $$M_{M_0, w_0}$$ must be one of the following two machines:

• $$M'_1$$: Write $$1$$. Halt.
• $$M'_0$$: Write $$0$$. Halt.

If, instead, you are looking for an algorithm that takes $$M_0$$ and $$w_0$$ as input and outputs a machine $$M_{M_0, w_0}$$ with the above property, then you are out of luck: there is not such algorithm in general (it might exist if you restrict the set of input machines $$M_0$$). Suppose that such an algorithm (i.e., Turing machine) $$A$$ existed, then it would allow to solve the halting problem:

• Given $$M_0$$ and $$w_0$$, compute $$M_{M_0, w_0}$$ by simulating $$A$$ on input $$(M_0, w_0)$$.
• Simulate $$M_{M_0, w_0}$$ on input $$(M_0, w_0)$$. By definition of $$M_{M_0, w_0}$$ this step requires finite time.
• Return "yes" if the output of $$M_{M_0, w_0}( (M_0, w_0) )$$ was $$1$$, otherwise return "no".
• I'm a little confused: does this mean that if we have a fixed Turing machine $M_0$ and a fixed $w_0$ input, we cannot predict how $M_0$ will work on $w_0$, i.e. it will halt or not? Commented Apr 2, 2020 at 23:45
• It depends on $M_0$ and $w_0$. For some of them you might be able to predict whether $M_0(w_0)$ halts or not (think for example, of the trivial machine that always halts on the first step). But you have no general method that, given $M_0$ and $w_0$, is able to predict whether $M_0(w_0)$ halts. Commented Apr 2, 2020 at 23:49
• You say I "might be able to predict whether $M_0(w_0)$ halts or not". Does this mean that there exists a $(M_0, w_0)$ pair for which it is known that it is impossible to predict whether $M_0(w_0)$ halts or not? If yes, could you give me please an example? Commented Apr 2, 2020 at 23:55
• The proposition: $P_T$="This Turing machine $T$ halts on the empty string $\epsilon$" cannot be proven true or false for all $T$ (as otherwise you'd be able to solve the halting problem by generating, in parallel, all tentative proofs for $T$'s termination and non-termination until, eventually, a correct proof is found). Let $T$ be a Turing machine for which $P_T$ can't be proven true of false. Pick $M_0 = T$ and $w_0 = \epsilon$. I don't know what $T$ is explicitly. Commented Apr 3, 2020 at 0:51
• @T.Christopher Perhaps what you ask in your 2nd comment deserves a new question/post. It's not easy to answer it in comments. Commented Apr 3, 2020 at 7:48