0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Steven
    Commented Apr 2, 2020 at 23:15
  • $\begingroup$ @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? $\endgroup$
    – Heisenberg
    Commented Apr 2, 2020 at 23:22

1 Answer 1

1
$\begingroup$

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".
$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Heisenberg
    Commented Apr 2, 2020 at 23:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steven
    Commented Apr 2, 2020 at 23:49
  • $\begingroup$ 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? $\endgroup$
    – Heisenberg
    Commented Apr 2, 2020 at 23:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steven
    Commented Apr 3, 2020 at 0:51
  • $\begingroup$ @T.Christopher Perhaps what you ask in your 2nd comment deserves a new question/post. It's not easy to answer it in comments. $\endgroup$
    – frabala
    Commented Apr 3, 2020 at 7:48

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.