# Blum–Shub–Smale machine

(Redirected from Blum-Shub-Smale)
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

A BSS machine M is given by a list $I$ of $N+1$ instructions (to be described below), indexed $0,1,\dots ,N$ . A configuration of M is a tuple $(k,r,w,x)$ , where k is the index of the instruction to be executed next, r and w are copy registers holding non-negative integers, and $x=(x_{0},x_{1},\ldots )$ is a list of real numbers, with all but finitely many being zero. The list $x$ is thought of as holding the contents of all registers of M. The computation begins with configuration $(0,0,0,x)$ and ends whenever $k=N$ ; 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$(x_{0})$ : a substitution $x_{0}:=g_{k}(x)$ is performed, where $g_{k}$ 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 $r:=0$ or $r:=r+1$ and similarly for w. The next instruction is k+1.
• Branch$(x_{0},l)$ : if $x_{0}\geq 0$ then goto l else goto k+1.
• Copy($x_{r},x_{w}$ ): the content of the "read" register $x_{r}$ is copied into the "write" register $x_{w}$ ; the next instruction is k+1

## Further reading

• 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.