To gain a better understanding of space-bounded computation, let's look at the relationship between time classes and space classes.
Definition. TIME(f(n)) is the class of all decision (yes/no) problems that can be solved (deterministically) in time O(f(n)).
Definition. SPACE(f(n)) is the class of all decision (yes/no) problems that can be solved (deterministically) in space O(f(n)).
By definition, a program that loops forever uses infinitely much space.
Notice that we an define P and PSPACE in terms of TIME and SPACE classes.
Definition. P = ∪k > 0TIME(nk).
Definition. PSPACE = ∪k > 0SPACE(nk).
You cannot use more space than time.
Recall that our official model is a Turing machine. A Turing machine can only move its head to the right one cell per step.
So an algorithm that uses time O(f(n)) must also use space O(f(n)). As a consequence,
Theorem. For every function f(n), TIME(f(n)) ⊆ SPACE(f(n)).
The reverse of the observation above does not work. You can use a lot of time using a small amount of space.
Think of a computation that counts up to 2n. It only needs n bits to write down the current value of the counter.
But there are limits.
Theorem. For every function f(n), SPACE(f(n)) ⊆ ∪c > 1 TIME(cf(n)).
Proof. Recall that a program that loops forever uses infinite space. If a program uses space O(f(n)), then it cannot loop forever.
How long can it run without looping forever if it has c⋅f(n) space?
A Turing machine has a tape alphabet; suppose that alphabet contains a symbols. With c⋅f(n) symbols, there are ac⋅f(n) configurations that can be written on the tape.
A Turing machine also has a finite collection of states. Suppose that there are s states. That increases the number of configurations by a factor of s.
Finally, the tape head can be in c⋅f(n) positions.
So the total number of different configurations is s⋅c⋅f(n)⋅ac⋅f(n).
The dominant part is ac⋅f(n) = (ac)f(n).
Choosing d = ac, we see that there are only about d f(n) configurations.
The program cannot run more than that many steps without repeating a configuration. If it repeats a configuration, it is in an infinite loop. ◊