#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!!!

Leave a Reply

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