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

• For $S\subseteq\mathbb N$, let $H_S=\{ \langle M \rangle : M$ is a deterministic TM that halts on $\epsilon$ in exactly $s$ steps for some $s\in S\}$. An equivalent but slightly easier way to state the problem is when $H_S$ is decidable. You suspect that $H_S$ is decidable $\iff$ $S$ is finite. – John L. Jun 25 '20 at 23:56

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

• Nice explanation. However, the really interesting question is, is there an example where 𝐿𝑆 is decidable for a set 𝑆 for which ℕ∖𝑆 is not finite? The additional assumption of a specially designed oracle machine, although enlightening, render the question much easier and less interesting. – John L. Jun 26 '20 at 0:02
• Yes, indeed that question is interesting. If the set S has infinite holes, but has a “easy pattern” in its holes, then the same proof as given in 1 can be applied to prove its undecidability. For any decidable set in general, I think it is not trivial to prove/disprove the OP’s hypothesis. – prime_hit Jun 26 '20 at 5:45
• Is the use of oracles is for the second case where we check if $T_M$ is in $S$? so yes. $S$ can be undecidable, but the proof should deal with it without oracles (or to say it's impossible) – Oren Jun 26 '20 at 11:52
• If $S$ is undecidable, then $L_S$ will be undecidable. We can easily prove this by contradiction. If $L_S$ is decidable, then you can easily construct a decider for $S$. It’s quite elementary and I’ll leave it to you to think about this. – prime_hit Jun 26 '20 at 12:10
• For each natural $n$, we can construct a Turing Machine $T_n$ which halts exactly in $n$ steps. What do you think will happen in you pass $T_n$ to the decider for $L_S$? – prime_hit Jun 27 '20 at 13:19