3
$\begingroup$

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

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks, I do not get your 3rd paragraph. What is the space of pf decidable languages, what you mean by decidable equality?? Could you please expand on that... $\endgroup$
    – StefanH
    Feb 28, 2019 at 13:47
  • 4
    $\begingroup$ @StefanH The point is: when we deal with sets of natural numbers (or words), we can use the standard computability notions of (semi) decidability. When instead we deal with sets of sets of natural numbers, we need to be careful with the coding. The space of decidable language is the set of all decidable languages, so it is a set-of-sets (of words). Here we need to represent each language with a TM, a "code" for that -- however there might be many codes for the same language! This makes the problem "given two languages (their codes) are those the same?" non trivial. $\endgroup$
    – chi
    Feb 28, 2019 at 14:12
  • 4
    $\begingroup$ @StefanH Decidable equality would mean that, given two codes we can decide whether they represent the same thing. If codes are for languages, that would mean that given $i,j$ we can decide whether $L(M_i)=L(M_j)$ -- which is unfeasible. So: natural numbers, strings, rational numbers, (finite) trees / graphs, ... have decidable equality. Computable real numbers, decidable sets, ... have undecidable equality. $\endgroup$
    – chi
    Feb 28, 2019 at 14:15
1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ What is $n$ in $T(n)$ here? Anyway, the set $\mathcal A$ looks decidable to me, since a TM in $T(n)$ steps can only read $T(n)$ symbols from the tape, so there's only a finite number of inputs to try, for a given number of steps. $\endgroup$
    – chi
    Feb 28, 2019 at 17:30
  • $\begingroup$ @chi Thanks for your feedback, $T : \mathbb N \to \mathbb N$ is a function and $n$ its argument... is your objection still valid then? As $T(n)$ varies with the input (of size $n$). $\endgroup$
    – StefanH
    Mar 1, 2019 at 13:17
  • $\begingroup$ So $\mathcal A$ actually depends on $T$ and $n$, and $n$ which are completely independent from $M$? I think my objection still stands, then. $\endgroup$
    – chi
    Mar 1, 2019 at 13:19
  • 1
    $\begingroup$ @chi I mean $M$ has to halt in $T(|w|)$ steps for each input $w$, so $n$ is not fixed in advance but depends on the input size $M$ receives. Okay? $\endgroup$
    – StefanH
    Mar 1, 2019 at 13:30
  • $\begingroup$ Ah, right, I see now. I now agree: $\mathcal A$ looks coRE only. $\endgroup$
    – chi
    Mar 1, 2019 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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