Reducing a Decidability Problem to the Halting Problem

Question

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?

Answer 1

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\}$.

Answer 2

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.

Answer 3

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.