3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – John L. Jun 25 '20 at 23:56
0
+50
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – John L. Jun 26 '20 at 0:02
  • $\begingroup$ 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. $\endgroup$ – prime_hit Jun 26 '20 at 5:45
  • $\begingroup$ 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) $\endgroup$ – Oren Jun 26 '20 at 11:52
  • 2
    $\begingroup$ 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. $\endgroup$ – prime_hit Jun 26 '20 at 12:10
  • 1
    $\begingroup$ 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$? $\endgroup$ – prime_hit Jun 27 '20 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.