1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user137481 Apr 11 '14 at 18:45
  • $\begingroup$ $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. $\endgroup$ – Robert Israel Apr 11 '14 at 19:48
  • $\begingroup$ ... 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. $\endgroup$ – Robert Israel Apr 11 '14 at 19:50
  • $\begingroup$ 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? $\endgroup$ – user137481 Apr 11 '14 at 22:23
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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