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.[1] 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 closely related to the Real RAM model.

BSS machines are more powerful than Turing machines, because the latter are by definition restricted to a finite set of symbols.[2] A Turing machine can represent a countable set (such as the rational numbers) by strings of symbols, but this does not extend to the uncountable real numbers.

Definition

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 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); registers r and w may be changed, either by or and similarly for w. The next instruction is k+1.
  • Branch: if then goto ; else goto k+1.
  • Copy(): the content of the "read" register is copied into the "written" register ; the next instruction is k+1

Theory

Blum, Shub and Smale defined the complexity classes P (polynomial time) and NP (nondeterministic polynomial time) in the BSS model. Here NP is defined by adding an existentially-quantified input to a problem. They give a problem which is NP-complete for the class NP so defined: existence of roots of quartic polynomials. This is an analogue of the Cook-Levin Theorem for real numbers.

See also

References

  1. 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.
  2. Minsky, Marvin (1967). Computation: Finite and Infinite Machines. New Jersey: Prentice–Hall, Inc.

Further reading

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.