# Inclusion of complexity classes (Deterministic Turing Machine)

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?

• 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)$. Apr 28, 2014 at 15:59
• 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. Apr 28, 2014 at 16:00
• @DavidRicherby, yet I don't understand why the $log$; and the summation is the "number of configurations"? Apr 28, 2014 at 16:15
• @Louis, I don't get what you're trying to tell me :( Apr 28, 2014 at 17:06

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