# Halting (on empty input tape) for an infinite subset of all Turing machines

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.

• Why is the problem easy if the subset is finite? What if the subset consists of a halting problem? Commented Jan 6, 2021 at 13:53
• @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. Commented Jan 6, 2021 at 15:26