0
$\begingroup$

The problem:

Given $k>1$ Turing machines decide if for every possible input exactly one of them halts.

Is this variant of halting problem undecidable?

Intuitively, it seems that it must be not only as hard as the standard halting problem, it actually is harder. Because even if you have a refutation input string, you'd still need to run the machines, and if none of them halt, it could take forever to verify that this is a correct refutation.

But is there a proof of its undecidability?

$\endgroup$

1 Answer 1

2
$\begingroup$

Consider a Turing Machine $M_1$. Create $k - 1$ looping machines $M_2, …, M_k$ that never halts.

Then $M_1$ halts on all inputs if and only if for any input, exactly one among $M_1, …, M_k$ halts.

There, you have a many-one reduction from $H_{\textsf{ALL}} = \{\langle M\rangle \mid M \text{ halts on every inputs}\}$ which is known to be neither decidable, nor semi-decidable.

$\endgroup$
4
  • $\begingroup$ Thanks for the idea. Though, I suppose, the reduction is not from $\mathsf{ALL}$ but only from $\Pi_2$ problem - the universal halting problem. I suppose, $\mathsf{ALL}$, as a hierarchy that does not collapse, has no complete problem. $\endgroup$
    – rus9384
    Commented Feb 15 at 18:06
  • $\begingroup$ Yes, sorry, this is not exactly $\textsf{ALL}$ (however that still works). $\endgroup$
    – Nathaniel
    Commented Feb 15 at 18:18
  • $\begingroup$ Hm, I wonder if the reasoning holds, if at least one of the machines is universal. $\endgroup$
    – rus9384
    Commented Feb 15 at 20:09
  • $\begingroup$ The exactly-1-in-k problem is in the difference hierarchy over $\Sigma_1$, and as such much simpler than $\mathrm{H}_{\textrm{ALL}}$, which is $\Pi_2$-complete. $\endgroup$
    – Arno
    Commented Feb 15 at 20:44

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.