Blum–Shub–Smale machine

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In computation theory, the Blum–Shub–Smale machine, or BSS machine, is a model of computation introduced by Lenore Blum, Michael Shub and Stephen Smale, intended to describe computations over the real numbers. Essentially, a BSS machine is a Random Access Machine with registers that can store arbitrary real numbers and that can compute rational functions over reals in a single time step. It is often referred to as Real RAM model. BSS machines are more powerful than Turing machines (which in a sense are restricted to storing rational numbers only).

Definition[edit]

A BSS machine M is given by a list of instructions (to be described below), indexed . A configuration of M is a tuple , where k is the index of the instruction to be executed next, r and w are copy registers holding non-negative integers, and is a list of real numbers, with all but finitely many being zero. The list is thought of as holding the contents of all registers of M. The computation begins with configuration and ends whenever ; the final content of x is said to be the output of the machine.

The instructions of M can be of the following types:

  • Computation: a substitution is performed, where is an arbitrary rational function (a quotient of two polynomial functions with arbitrary real coefficients); copy registers r and w may be changed, either by or and similarly for w. The next instruction is k+1.
  • Branch: if then goto l else goto k+1.
  • Copy(): the content of the "read" register is copied into the "write" register ; the next instruction is k+1

See also[edit]

Further reading[edit]

  • Bürgisser, Peter (2000). Completeness and reduction in algebraic complexity theory. Algorithms and Computation in Mathematics. 7. Berlin: Springer-Verlag. ISBN 3-540-66752-0. Zbl 0948.68082.
  • Grädel, E. (2007). "Finite Model Theory and Descriptive Complexity". Finite Model Theory and Its Applications (PDF). Springer-Verlag. pp. 125–230. Zbl 1133.03001.
  • Blum, Lenore; Shub, Mike; Smale, Steve (1989). "On a Theory of Computation and Complexity over the Real Numbers: NP-completeness, Recursive Functions and Universal Machines" (PDF). Bulletin of the American Mathematical Society. 21 (1): 1–46. doi:10.1090/S0273-0979-1989-15750-9. Zbl 0681.03020.