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:
- is EVEN undecidable? How can you prove its undecidability?
- 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.