# A variation of the halting problem

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