Time and Space

In many models of computation it is possible to imagine communication between different stages of the computation. This communication is usually realized by one part of the computation leaving the computing device in a certain state and other part of the computation starting from this state. The amount of information “communicated” this way can often be quantified as the “space” of this model; and the number of times such a communication takes place relates to the “time” of the model. We then usually get time–space tradeoffs by utilizing communication complexity lower bounds. In this chapter we discuss several lower bounds concerning time and space in several models of computations. Particularly, certain types of Turning machines , finite automata , and branching programs . Time–Space Tradeoffs for Turing Machines In this section we discuss the standard model of multi-tape Turing machines; these are finite automata with an arbitrary but fixed number k of read/write tapes. The input for the machine is provided on another read-only tape, called the input tape . The cells of the read/write tapes are initiated with a special blank symbol, b . At each step the finite control reads the symbols appearing in the k + 1 cells (on the k + 1 tapes) to which its heads are pointing. Based on these k + 1 symbols and the state of the finite control, it decides what symbols (out of a finite set of symbols) to write in the k read/write tapes (in the same locations where it reads the symbols from), where to move the k + 1 heads (one cell to the left, one cell to the right, or stay on the same cell), and what is the new state of the finite control (out of a finite set of states).