Blum-Shub-Smale machine

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.

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$(x\_\{0\})$: a substitution $x\_\{0\}\; :=\; g\_\{k\}(x)$ is performed, where $g\_\{k\}$ 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$(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

ee also

*hypercomputation
*real computer

External links

* [http://www.logic.rwth-aachen.de/pub/graedel/FMTbook-Chapter3.pdf] E. Grädel. Finite Model Theory and Descriptive Complexity. In Finite Model Theory and Its Applications, pp. 125–230. Springer-Verlag, (2007).

* [http://www.ams.org/bull/1989-21-01/S0273-0979-1989-15750-9/S0273-0979-1989-15750-9.pdf] 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).