-2
$\begingroup$

We proved that, there exist no algorithm so it can tell us if an algorithm halts or not (a.k.a. the halting problem is undecidable). But it surely can handle some of those; can we tell which of those it can handle, and which not? If we can't, can we tell which of those we can tell if it can handle or not? And even if not that, can we tell which of those that we can't tell which of those we can tell if it can handle or not? (do it recursively till a yes comes; do a yes ever come?)

$\endgroup$
5
  • 2
    $\begingroup$ I think the question would be much clearer if you got rid of pronouns ("it", "those") and replace them with notation. If it answers your question, for any fixed algorithm $A$, there exists an algorithm that determines whether $A$ halts (the answer is either "yes" or "no", so just return "yes" or "no"). $\endgroup$
    – Dmitry
    Commented Jun 25, 2023 at 20:15
  • $\begingroup$ There seems to be a from missing from can we tell which of those that we can't tell which of those we can tell if it can handle or not?, or maybe the of should be a from. $\endgroup$
    – greybeard
    Commented Jun 26, 2023 at 4:42
  • 2
    $\begingroup$ You say consecutively "there exist no [decision] algorithm" and "it surely can handle some of those", where "it" represents the decision algorithm. So "it" does not exist !? Please review your text. $\endgroup$
    – user16034
    Commented Jun 26, 2023 at 6:31
  • $\begingroup$ @YvesDaoust "There exist algorithms, but whatever it is, it can't handle all, however can handle some" $\endgroup$
    – sbh
    Commented Jun 26, 2023 at 17:20
  • $\begingroup$ There is an Edit button. $\endgroup$
    – user16034
    Commented Jun 26, 2023 at 18:48

2 Answers 2

1
$\begingroup$

If you set a timeout on the decision algorithm $A$ (let us call this variant $A'$), then by running it on any input you will get either a yes/no answer or a don't know. And this is precisely the question you are asking, "which of those it can handle, and which not", where "it" is $A'$.

$\endgroup$
3
  • $\begingroup$ not quite true, because the decision algorithm may be able to handle more cases by running for longer. $\endgroup$ Commented Jul 27, 2023 at 8:27
  • $\begingroup$ @user253751: you don't understand my answer. $A'$ does answer yes/no/don't know on any input in finite time. That's all we ask it to do. $\endgroup$
    – user16034
    Commented Jul 27, 2023 at 8:37
  • $\begingroup$ yes, that says it's possible to make a partial halting decider which definitely knows or doesn't know, but the question asks about all partial halting deciders in general. $\endgroup$ Commented Jul 27, 2023 at 8:38
1
$\begingroup$

If I understand your question correctly, you are considering an algorithm $A$ that, when run with an input $x$ (which is in turn an algorithm) attempts to predict whether $x$ halts or not. Notice that $A(x)$ could accept, reject, or run forever.

Now you consider the language $H_{A}$ containing all algorithms $x$ such that either i) $x$ halts and $A(x)$ accepts, or $x$ does not halt and $A(x)$ rejects. The question is whether $H_A$ is decidable.

The answer depends on $A$. For example, if $A$ is an algorithm that runs forever. Then $H_A = \emptyset$ and hence it is trivially decidable. If $A$ is the trivial algorithm that always accepts, then $H_A$ is the language of the halting problem and hence it is undecidable.

$\endgroup$

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.