The halting problem is undecidable, i.e. $\not \exists$ $M$ Turing machine s.t. for every $(M_0,w_0)$ input where $M$ is the description of a Turing machine and $w_0$ is an input word, the output of $M$ is "$1$" if $M_0$ will halt on $w_0$ and "$0$" if it will not.

From this statement only, it does not follow that there must be an ($M_0,w_0$) pair for which it is impossible to predict if $M_0(w_0)$ halts or not. It only means there is no general way to decide this question for all ($M_0,w_0$) pairs.

So my question is the following: Does there exist 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, is there a known example or construction for an ($M_0,w_0$) pair such that?

  • 1
    $\begingroup$ What do you mean by "impossible to predict"? $\endgroup$ – Yuval Filmus Apr 3 '20 at 22:22
  • 1
    $\begingroup$ This doesn’t help at all. It only pushes the problem to a different phrase: what do you mean by “can we always decide”? Who should decide, and how? $\endgroup$ – Yuval Filmus Apr 3 '20 at 22:41
  • 1
    $\begingroup$ Here is one suggestion: you want an example of a Turing machine for which it cannot be proved (in some fixed proof system) that the machine halts, and also it cannot be proved that the machine doesn’t halt. $\endgroup$ – Yuval Filmus Apr 3 '20 at 22:50
  • 1
    $\begingroup$ I don’t think we’re making any progress here. $\endgroup$ – Yuval Filmus Apr 3 '20 at 22:55
  • 1
    $\begingroup$ The halting problem says no one machine can decide weather every given input pair halts or not. It seem's you're asking is there one input for which no machine, when run on that input, halts and accepts IFF the input pair halts. There is no such input for a trivial reason. A given input pair either halts or loops. If it halts the machine that accepts all inputs "makes the correct prediction" (if you can call it that). If it loops the machine that always rejects suffices.. $\endgroup$ – Jake Apr 3 '20 at 23:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.