patternMinor
Is the set of language decidable by some Turing machine computing in some given computable time bound decidable
Viewed 0 times
thecomputableboundtimelanguagedecidablesomemachineturinggiven
Problem
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 s
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 s
Solution
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.
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.
Context
StackExchange Computer Science Q#104955, answer score: 3
Revisions (0)
No revisions yet.