Is the set of language decidable by some Turing machine computing in some given computable time bound decidable

Question

Let $T : \mathbb N \to \mathbb N$ be some computable function. Then by $\mathcal C_T$ we denote the class of languages decidable by a deterministic Turing machine in at most $T(|w|)$ steps for an input $w$. In On the Computational Complexity of Algorithms by J.Hartmanis and R.E. Stearns it is stated that $\mathcal C_T$ is recursively enumerable (they consider a notion of computable sequences, but this is the same as a $\{0,1,\}$-sequence could be considered a subset of $\mathbb N$, and going from to $\mathbb N$ to $\Sigma^*$ does not change anything) and their proof goes by enumerating all machines, and modifying them in order to stop after $T(|w|)$ moves and print zero (this used the computability of $T$). By this procedure for each element in $\mathcal C_T$ some machine is enumerated for it.

But I noticed that also the complement of $C_T$ is recursively enumerable. A machine to accept this set (and do not halt for elements not in the set) could operate according to the following scheme:

Given a Turing machine $M$ as input, we want to know if it halts in at most $T(n)$ steps on each input. Let $\Sigma^{\ast} = \{w_1, w_2, w_3, \ldots \}$ and $c : \mathbb N \to \mathbb N \times \mathbb N$ be some computable pairing function. Then set up a counter $i = 1, 2, 3, \ldots$ and for each $i$ write $(j,k) = c(i)$. Then simulate the machine $M$ on input $w_j$ for $k$ steps, if $k > T(|w_i|)$ and the $M$ has not halted before $k$ steps (i.e. is still in a non-halting state) then accept it.

A turing machine could operate according to the above algorithm and this would give us a machine that takes another machine and accepts presicely those that run on some input of length $n$ more than $T(n)$ steps (and runs forever for all the others).

Hence it accepts the complement of $\mathcal C_T$. So both sets are recursively enumerable, hence the set $C_T$ is recursive/decidable.

Is this reasoning right? I am just wondering why J.Hartmanis and R.E. Stearns have not included this stronger statement in their paper back then...

Answer 1

This is a situation where coding is non-trivial. $\mathcal{C}_T$ is a class of decidable languages. To make sense of $\mathcal{C}_T$ having any effective properties, we need to choose a coding. Naturally, we would code some decidable language $L$ by the index of some TM that decides it.

So what does it mean for $\mathcal{C}_T$ to be recursively enumerable? It means that we can effectively produce a list $(M_i)$ of TMs such that $\{L(M_i) \mid i \in \mathbb{N}\} = \mathcal{C}_T$. Note that this does not give us that $\mathcal{C}_T$ is semi-decidable -- that would mean that given some TM $M$ deciding a language, we can recognize that codes a language belonging to $\mathcal{C}_T$.

The familiar "semi-decidable = computable enumerable" holds only for spaces with decidable equality -- and the space pf decidable languages does not have decidable equality.

Furthermore, the complement of $\mathcal{C}_T$ is not semi-decidable, either: While we can recognize that a given TM takes too much time, we cannot rule out that there is another TM deciding the same language, but respecting our time-bounds.

Answer 2

Just let me add some additional insights after thinking about it. Let $T(n)$ be some computable function.

Define $$ \mathcal A = \{ M \mid \mbox{ $M$ is a TM which halts in $T(n)$ steps for each input of size $n$}\}. $$ Then $\mathcal C_T = \{ L(M) : M \in \mathcal A \}$. As shown in my post the complement of the set $\mathcal A$ is recursively enumerable (and by the way we are working with strings, hence have decidable equality between elements). But here we do not have recursive enumerability of the set $\mathcal A$ itself (where for $\mathcal C_L$ we have). This follows from Rice's Theorem as here the non-trivial property mentioned in the article is $\mathcal C_L$ (strictly we have to show that $\mathcal C_L$ is non-trivial first, but this I take for granted now).

Note by the way that the complement of $\mathcal C_T$ is not even enumerable. But what we mean when we say $\mathcal C_T$ is recursively enumerable is that we can enumerate some representation in terms of machines for it. Then Rice's Theorem talks about the complement in terms of these codes, i.e. the relative complement with respect to the set $\{ L(M) \mid M \mbox{ is some TM } \}$.