# Reducing a Decidability Problem to the Halting Problem

Let $L = \{(M, n): M$ halts on less than $n$ elements from a set S $\}$
I'm trying to come up with a generalization on how to solve these types of problems so I have not defined what S is.

Since the halting problem is undecidable, it means we won't be able to determine if M would halt on an input i from S. It follows then that we won't be able to decide if M would halt on less than (or more than) n elements from S.

1) Is my generalization valid?
2) Does it matter what S is?

If your goal is to prove that $L$ is undecidable, you want to reduce from the halting problem, not to the halting problem.

This reduction is easy enough if $S$ is not empty. Suppose we're given $(M,a)$ and want to decide whether $M$ halts on input $a$. Construct machine $M'$ to do the following:

1. Ignore its input.
2. Write $a$ to the tape.
3. Simulate $M$.

Then run your supposed decider for $L$ with input $(M',1)$ it will answer "yes" iff $M$ doesn't halt on $a$. So if $L$ is decidable then HALT is decidable too. And we know that HALT is not decidable, so $L$ cannot be decidable either.

(Note that this is a Turing reduction rather than a many-one reduction because we need to invert the answer from the $L$-solver).

If $S$ is empty then $L$ is of course trivially decidable: $L_{S=\varnothing}=\{(M,n)\mid n> 0\}$.

You haven't defined S, but it has to be defined in order for the problem to be specified.

If S is a finite set, in order to solve your problem it would suffice to be able to solve, for each $i$ in S, the problem of whether $M$ halts on input $i$. But if S is infinite, that may not be enough.

• so does that mean that the "type" of the elements in S don't have to be specified? That we just have to specify whether S is finite or infinite? But if the halting problem does not specify whether the input is from a finite or infinite set, why do we need to in this case? – user137481 Apr 11 '14 at 18:45
• $S$ is part of the specification of the problem. That is, in a particular instance, you are given a specific machine $M$ and a specific set $S$ (presumably its members are of whatever type is acceptable as inputs to $M$), and you ask whether there are fewer than $n$ members of $S$ on which $M$ halts. Note that if the answer is No (i.e. there are at least $n$ such members), you can prove that by running $M$ on $n$ different inputs and seeing that it does indeed halt in each of those cases. A Yes answer, on the other hand, might not be provable. – Robert Israel Apr 11 '14 at 19:48
• ... and my point was simply that (in the infinite case) it might still not be provable even using an oracle that could tell whether or not $M$ would halt on any specific input. – Robert Israel Apr 11 '14 at 19:50
• I see your point. If S was finite, it would be possible to enumerate all of the elements to find the n or more members on which M would halt. But, my understanding was that you need to prove that an algorithm A exists that takes M and the n inputs and decides that M halts on them. For L to be decidable, A also had to be able to tell if M would not halt on an input. So, if S had only one such element, based on the Halting problem, no such A could possibly exist. In that case, wouldn't your example just show recognizability as opposed to decidability? – user137481 Apr 11 '14 at 22:23

Your proof idea is just fine. If you want to make the proof even clearer, all you have to do is set $S = \{w\}$ for an arbitrary string $w$ and set $n=1$, and now you have the halting problem. So if you could decide your problem for arbitrary $S,n$, then you could decide the halting problem, which is impossible. If you want to rigorously show the problem is undecidable for $n > 1$, just create a new Turing machine that accepts $n-1$ strings in $S$ different than $w \in S$ in finite time, and runs forever on $|S| - n$ strings in $S$ different from $w$, and simulates an arbitrary Turing machine on string $w$. Then the answer for $S,n$ is equivalent to whether the simulated Turing machine halts on string $w$, which is the standard halting problem.