Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

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

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer
    
You, sir, made my day. Thank you :) –  elmazzun Apr 28 at 18:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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