# #StackBounty: #turing-machines #undecidability #decision-problem A variation of the halting problem

### Bounty: 50

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

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.