2
$\begingroup$

As is well known, there is no single procedure for deciding whether any given Turing machine halts on an empty input tape. This is easily shown, e. g., by applying Rice's theorem.

But what if, instead of considering the entire set of Turing machines, we only focus on a subset thereof? Clearly, if the subset is finite, the problem is decidable. But if the subset is infinite, is there an easy way to prove its undecidability?

Take, e.g., the following decision problem (let's call it EVEN):

EVEN = determine whether any given Turing machine with an even index halts on an empty input tape.

(Just to be clear about quantifiers, I mean: does there exist a procedure that is able, for any given Turing machine with an even index, to decide whether that machine halts on an empty input tape?)

In this case, the considered set of Turing machines is infinite, but Rice's theorem is no longer applicable (a.f.a.i.k.) and even a diagonalization argument does not seem to be conclusive, since you may end up with a function with an odd index, so self-reference is lost.

So my questions are:

  1. is EVEN undecidable? How can you prove its undecidability?
  2. what about other infinite subsets of TMs (for which we ask whether they halt on an empty input tape)? would this problem still be undecidable or does that depend on the subset?

Regarding question 2, one could take the set of TMs that compute, say, f(x) = x, which certainly always halt; however, the set of indices of those TMs is not a recursive set, so the question seems ill-formulated.

$\endgroup$
2
  • $\begingroup$ Why is the problem easy if the subset is finite? What if the subset consists of a halting problem? $\endgroup$ – Pål GD Jan 6 at 13:53
  • $\begingroup$ @PålGD Say you have a set of 100 (indices of) TMs, for each of which you want to know whether it halts or not. Overall, you have 2^100 ways (=functions, all of which are trivially computable) to address the problem, and one of these is the right one (although you may not know which one), so the problem is decidable. Maybe my question was unclear or maybe I do not understand your point. $\endgroup$ – Maiaux Jan 6 at 15:26
1
$\begingroup$

is EVEN undecidable? How can you prove its undecidability?

It depends entirely on the enumeration that you use. E.g. one could make an enumeration that maps all Turing machines that halt with 1000 steps to an even index and all others to odd indices. Then EVEN is still an infinite set but decidable.

However a simple way to prove EVEN undecidable (assuming your enumeration is anything sane) is to show that for every Turing machine T there exists a machine T' that has an even index but identical behavior. You can do this by adding unreachable states, or useless extra transitions, etc, as long as it switches the parity of the enumeration.

What about other infinite subsets of TMs (for which we ask whether they halt on an empty input tape)? Would this problem still be undecidable or does that depend on the subset?

Entirely depends on the subset. See the example above, "the set of all Turing machines that halt within 1000 steps" is infinite, and trivially decidable. Other examples could include any mapping from infinite families of functions that you know that halt to Turing machines. All you need is an injective mapping - you don't need to decide behavioral equivalence.

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