Im looking for examples of algorithms $A,B,C,D$ such that :

$A$ halts If $B$ does not halt.

$C$ does not halt If $D$ halts.

$A,B,C,D$ are not algorithms that halt on all input. Also they are not algorithms that loop forever on all input.

I am aware that the general halting problem is undecidable (in case you wonder).


closed as unclear what you're asking by user21820, Hans Lundmark, Ove Ahlman, Guy Fsone, Peter Smith Dec 6 '17 at 19:47

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ $A,B,C,D$ are what, Turing machines? Also what have you done, and where do you get stuck? $\endgroup$ – Ove Ahlman Dec 6 '17 at 12:39
  • $\begingroup$ I edited. Reopen If all is clear ?? $\endgroup$ – mick Dec 6 '17 at 21:21
  • 1
    $\begingroup$ I have edited my answer so that it fits your new condition, though I suspect that the answer is still not what you are looking for. I suggest that you add more context. Perhaps tell us kinda what the solution should look like, and why you find it hard to come up with a solution on your own? $\endgroup$ – Ove Ahlman Dec 7 '17 at 6:19

(Edited solution slightly after OP edited the question) There are (still) some trivial answers.

Let $A$ be any TM which accepts the empty string and let $B$ be the TM, which instantly halts, except in the case of the empty string, in which case it goes into an infinite loop. Now for each non-empty string $IF$ B does not halt, then $A $ will certainly halt. Since $B$ will halt, this is clearly true. For the non-empty string we know that $A$ halts and $B$ does not halt, thus the implication clearly hold for any input.

In the same spirit let $C$ be any TM which does not accept the empty string, and let $D$ be the TM which just loops and do not halt for any string, except for the empty string which it accepts imediately.


Not the answer you're looking for? Browse other questions tagged or ask your own question.