I can't understand what my professor wrote about these inclusions concerning deterministic classes:

$$ DTIME(f) \subseteq DSPACE(f) \subseteq \sum_{c\in\Bbb N}DTIME(2^{c(log+f)}) $$

I understood the first inclusion:

The Turing Machine needs to do at least one step in order to check the next cell on tape

I didn't get the second one:

The number of configurations of the Turing Machine with fixed space is finite, and the computation must stop within a maximum number of steps equal to these settings, otherwise wewould have a cycle.

I don't understand the argument of the summation: why that $2$ and that $c(log+f)$? Why is it written like that?

  • 2
    $\begingroup$ That's very strange notation. Complexity classes can't be added (they're sets, not numbers) so surely the summation should be a union. Presumably, "$\log{} + f$" means $\log n + f(n)$. $\endgroup$ Apr 28, 2014 at 15:59
  • 1
    $\begingroup$ If a deterministic TM reaches the same configuration twice, then it will definitely not halt. Now try to work out the number of possible states of a TM that uses $s$ tape cells in terms of $s$, the number of states, and the size of the alphabet. $\endgroup$
    – Louis
    Apr 28, 2014 at 16:00
  • $\begingroup$ @DavidRicherby, yet I don't understand why the $log$; and the summation is the "number of configurations"? $\endgroup$
    – elmazzun
    Apr 28, 2014 at 16:15
  • $\begingroup$ @Louis, I don't get what you're trying to tell me :( $\endgroup$
    – elmazzun
    Apr 28, 2014 at 17:06

1 Answer 1


Expanding on the comments, the idea is that if a Turing machine has $M$ possible configurations then if it halts, it must do so within $M$ steps. The reason is that once the machine has stepped through $M+1$ different configurations, it must have stepped on the same configuration $C$ twice. Since the machine is deterministic, each time it reaches configuration $C$, it will work its way in the same manner and reach $C$ again, and again, and again, indefinitely.

How many different configurations are there? Suppose the tape alphabet is $\Sigma$ (include the blank symbol), the space is $S$ (assume for simplicity that the tape is one-way infinite so there is a unique chunk of space $S$), and there are $N$ states. Then the number of configurations is $NS|\Sigma|^S$, since a configuration is given by the state, the position of the head, and the contents of the tape. We can write this bound as $$ NS|\Sigma|^S = 2^{\log N + \log S + (\log |\Sigma|) S} \leq 2^{c(1+\log S + S)} $$ for $c = \max(\log N, \log |\Sigma|)$. Assuming $S \geq 2$, we can further simplify this to $2^{c(1+\log S+S)} \leq 2^{c'(\log S+S)}$ for $c' = 2c$.


Your Answer

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

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