Inclusion of complexity classes (Deterministic Turing Machine)

Question

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?

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