# Undecidability of the exactly-1-in-k halting problem

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?

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.
• 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. Commented Feb 15 at 18:06
• Yes, sorry, this is not exactly $\textsf{ALL}$ (however that still works). Commented Feb 15 at 18:18
• 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.