The measure DSPACE is used to define complexity classes, sets of all of the decision problems that can be solved using a certain amount of memory space. For each function f, there is a complexity class SPACE, the set of decision problems that can be solved by a deterministic Turing machine using space O. There is no restriction on the amount of computation time that can be used, though there may be restrictions on some other complexity measures. Several important complexity classes are defined in terms of DSPACE. These include:
REG = DSPACE, where REG is the class of regular languages. In fact, REG = DSPACE.
Proof: Suppose that there exists a non-regular language L ∈ DSPACE, for s = o. Let M be a Turing machine deciding L in space s. By our assumption L ∉ DSPACE; thus, for any arbitrary, there exists an input of M requiring more space than k. Let x be an input of smallest size, denoted by n, that requires more space than k, and be the set of all configurations of M on input x. Because M ∈ DSPACE, then, where c is a constant depending on M. Let S denote the set of all possible crossing sequences of M on x. Note that the length of a crossing sequence of M on x is at most : if it is longer than that, then some configuration will repeat, and M will go into an infinite loop. There are also at most possibilities for every element of a crossing sequence, so the number of different crossing sequences of M on x is According to pigeonhole principle, there exist indexes i < jsuch that, where and are the crossing sequences at boundary i and j, respectively. Let be the string obtained from by removing all cells from i + 1 to j. The machine still behaves exactly the same way on input as on input, so it needs the same space to compute as to compute. However, |x' | < |x|, contradicting the definition of. Hence, there does not exist such a language as assumed. □ The above theorem implies the necessity of the space-constructible function assumption in the space hierarchy theorem.
DSPACE is traditionally measured on a deterministic Turing machine. Several important space complexity classes are sublinear, that is, smaller than the size of the input. Thus, "charging" the algorithm for the size of the input, or for the size of the output, would not truly capture the memory space used. This is solved by defining the multi-tape Turing machine with input and output, which is a standard multi-tape Turing machine, except that the input tape may never be written-to, and the output tape may never be read from. This allows smaller space classes, such as L, to be defined in terms of the amount of space used by all of the work tapes. Since many symbols might be packed into one by taking a suitable power of the alphabet, for all c ≥ 1 and f such that f ≥ 1, the class of languages recognizable in c f space is the same as the class of languages recognizable in f space. This justifies usage of big O notation in the definition.
