A variation of the halting problem

Question

Given an infinite set $S \subseteq \mathbb{N}$, define the language:

$L_S = \{ \langle M \rangle : M $ is a deterministic TM that does not halt on $\epsilon$, or, $T_M \in S\}$

where $T_M$ is the number of steps that $M$ takes until it halts with the empty word $\epsilon$ as input (or $\infty$ if it doesn't halt).

What are the sets $S$ such that $L_S$ is decidable?

There are some more trivial cases, if $S = \{k,k+1,k+2, \dots \}$ for some $k \in \mathbb{N}$ then $L_S$ is clearly decidable, as we can simulate $M$ on $\epsilon$ for $k-1$ steps and accept if and only if $M$ didn't halt. though, if we take $S= \{k,k+2,k+4,\dots \}$ for some $k \in \mathbb{N}$, or even simply taking $S=\mathbb{N}_{even}$ or $S=\mathbb{N}_{odd}$ this becomes more of a problem, because there is no prevention from it being impossible to have a finite calculation for whether the number of steps until halting will be even in the cases where it halts. Although this seems undecidable I'm not sure how to prove this.

I generally suspect that $L_S$ is decidable if and only if $\mathbb{N} \setminus S$ is finite and $S$ is decidable

Answer 1

$L_S$ is undecidable if $S = \mathbb{N}_{odd}$:

The problem of whether a given TM accepts $\epsilon$ is undecidable. There is a simple reduction from this problem to the problem of membership in $L_S$ when $S = \mathbb{N}_{odd}$. Given a TM $M$, we create a new TM $M'$ which on any input simulates $M$ on the same input, but for each step of $M$, it takes one (or any finite odd number of) extra redundant step(s). This basically makes sure that the number of steps taken by $M'$ on any input is always even.
Now, since $T_{M'} \notin S$, hence, $M'$ is in $L_S$ if and only if $M'$ doesn't halts on $\epsilon$, which in turn implies that $M$ doesn't halt on $\epsilon$. Hence, this language is undecidable.

A similar proof can be also given for $\mathbb{N}_{even}$.

[Undecidable $S$ with Oracle Machines] $L_S$ is decidable for a set $S$ for which $\mathbb{N} \setminus S$ is not finite.

Assuming that the set $S$ need not be decidable itself, and we are going to use it as an oracle and check for decidability using oracle machines.

We construct the set $S$ as follows: for each Turing Machine $M$, let it's binary encoding be $\langle M \rangle$, and let the length of the string $\langle M \rangle$ be $n$. If $M$ doesn't halt on $\epsilon$, then we add the number $10^{n}\langle M \rangle$ to our set $S$. By construction, this set doesn't contain infinite numbers.

Now, the decider will work as follows: On an input $M$, it will check whether the number $10^{n}\langle M \rangle$ is in $S$. It will accept $M$ if the number if found, else we can be sure that the machine $M$ will halt, and hence we simulate $M$ on $\epsilon$ until it halts while keeping the count of the number of steps taken by $M$. We finally accept or reject $M$ on the basis of whether this count is in $S$ or not.

Hence, this language is decidable for a set $S$ for which $\mathbb{N} \setminus S$ is not finite.

[Decidable S]

When the set $S$ is decidable, it will be interesting to know whether the hypothesis that "$\mathbb{N} \setminus S$ is finite" holds. I suspect that the answer would be affirmative.

Let $S' = \mathbb{N} \setminus S$ be infinite set. If $S'$ has "simple" subsequence in it (say, an Arithmetic Progression), then we can prove that $L_S$ would be undecidable by a proof similar to the one in the case of $S = \mathbb{N}_{odd}$. The idea is simply to run a construct a TM $M'$ which simulates $M$, and if $M$ halts, then jump to the next hole in $S$. $M'$ will be in $L_S$ iff $M$ halts.

This idea doesn't seem to work when $S'$ is a difficult set; by which I mean that checking the membership is hard in terms of time complexity.