There is no total Turing computable function f (n) such that every recursive
language can be decided in time f(n), where n is the length of the input string.
Proof: Consider the alphabet Σ = {0,1}, with all strings in Σ + arranged in proper
order w 1 , w 2 ,…. Also, assume that we have a proper ordering for the Turing
machines in M 1 ,M 2 ,….
Assume now that the function f (n) in the statement of the theorem exists. We
can then define the language
We claim that L is recursive. To see this, consider any w ∈ L and compute first
f(|w|). By assuming that f is a total Turing computable function, this is possible.
We next find the position i of w in the sequence w 1 ,w 2 ,…. This is also possible
because the sequence is in proper order. When we have i, we find M i and let it
operate on w for f(|w|) steps. This will tell us whether or not w is in L, so is
recursive.
But we can now show that L is not decidable in time f(n). Suppose it were.
Since L is recursive, there is some M k , such that L = L (M k ). Is w k in L? If we
claim that if w k is in L, then M k decides w k in f(|w k |) steps. But this contradicts
(14.4). Conversely, we get a contradiction if we assume that w k ∉ L. The
inability to resolve this issue is a typical diagonalization result and leads us to
conclude that the original assumption, namely the existence of a computable f
(n), must be false.
Theorem 14.3 allows us to make some claims, for example, that there is a
language in DTIME (n 4 ) that is not in DTIME (n 3 ). Although this may be of
theoretical interest, it is not clear that such a result has any practical significance.
At this point, we have no clue what the characteristics of a language in DTIME
(n 4 ) might be. We can get a little more insight into the matter if we relate the
complexity classification to the languages in the Chomsky hierarchy. We will
look at some simple examples that give some of the more obvious results.
Example 14.3
Every regular language can be recognized by a deterministic finite automaton in
language can be decided in time f(n), where n is the length of the input string.
Proof: Consider the alphabet Σ = {0,1}, with all strings in Σ + arranged in proper
order w 1 , w 2 ,…. Also, assume that we have a proper ordering for the Turing
machines in M 1 ,M 2 ,….
Assume now that the function f (n) in the statement of the theorem exists. We
can then define the language
We claim that L is recursive. To see this, consider any w ∈ L and compute first
f(|w|). By assuming that f is a total Turing computable function, this is possible.
We next find the position i of w in the sequence w 1 ,w 2 ,…. This is also possible
because the sequence is in proper order. When we have i, we find M i and let it
operate on w for f(|w|) steps. This will tell us whether or not w is in L, so is
recursive.
But we can now show that L is not decidable in time f(n). Suppose it were.
Since L is recursive, there is some M k , such that L = L (M k ). Is w k in L? If we
claim that if w k is in L, then M k decides w k in f(|w k |) steps. But this contradicts
(14.4). Conversely, we get a contradiction if we assume that w k ∉ L. The
inability to resolve this issue is a typical diagonalization result and leads us to
conclude that the original assumption, namely the existence of a computable f
(n), must be false.
Theorem 14.3 allows us to make some claims, for example, that there is a
language in DTIME (n 4 ) that is not in DTIME (n 3 ). Although this may be of
theoretical interest, it is not clear that such a result has any practical significance.
At this point, we have no clue what the characteristics of a language in DTIME
(n 4 ) might be. We can get a little more insight into the matter if we relate the
complexity classification to the languages in the Chomsky hierarchy. We will
look at some simple examples that give some of the more obvious results.
Example 14.3
Every regular language can be recognized by a deterministic finite automaton in