## A Constant-Space Model of Computation for First-Order Queries

- DIMACS Center - Room 431
- Busch Campus
- Piscataway, New Jersey
- November 8, 1995 at **1:00** PM

### Abstract:

We present a natural model of computation for constant-space serial
algorithms. It differs from the classical finite-state machine in
subtle but important ways. Instead of a single head and finite
control, the input is accessed using multiple heads with an oblivious
control. The actual boolean data calculations are performed
separately, and have a read-once restriction imposed upon them. We
argue that this approach of measuring read/write work space is more
intuitively accurate, and describe it in ordinary terms by a simple
deterministic machine with a sequential programming language.
Our model captures first-order logical expressibility, which in the
presence of arithmetic is known to coincide with constant-time
parallel computability (uniform AC^0). This
parallel-time/serial-space duality will be illustrated most
beautifully by the example of binary addition, for which our main
theorem constructively yields the carry look-ahead algorithm from the
bit-serial (elementary school) algorithm. There also appear to be
connections between space measurement in this model and quanta of
information. This reinforces the notion that first-order logic is a
machine-independent query language, and may also give possible
insights into space-bounded quantum computation. Extensions to
constant-depth threshold circuits (uniform TC^0) and ALOGTIME (uniform
NC^1) will also be discussed.