Blum Shub Smale machine

From Wikipedia, the free encyclopedia

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 which registers can store arbitrary real numbers and which can compute rational functions over reals at unit cost.

[edit] Definition

A BSS machine M is given by the set I of N + 1 instructions, indexed 0, 1, \dots, N. A configuration of M is a tuple (k,r,w,x), where k is the number of the instruction currently executed, r and w are copy registers and x stores the content of all registers of M. The computation begins with configuration (0,0,0,x) and ends whenever k = N - the content of x is said to be the output of the machine.

The instructions of M can be of the following types:

  • Computation(x0): a substitution x0: = gk(x) is performed, where gk is an arbitrary rational function; copy registers r and w may be changed, either by r: = 0 or r: = r + 1 and similarly for w.
  • Branch(x0,l): if x_{0} \geq 0 then goto l else goto k+1.
  • Copy(xr,xw): the content of the "read" register xr is copied into the "write" register xw; the next instruction is k+1


[edit] See also

[edit] External links

  • [1] E. Grädel. Finite Model Theory and Descriptive Complexity. In Finite Model Theory and Its Applications, pp. 125–230. Springer-Verlag, (2007).
  • [2] L. Blum, M. Shub, and S. Smale, ON A THEORY OF COMPUTATION AND COMPLEXITY OVER THE REAL NUMBERS: NP-COMPLETENESS, RECURSIVE FUNCTIONS AND UNIVERSAL MACHINES, Bull. Am. Math. Soc., 21, 1 (1989).