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 with registers that can store arbitrary real numbers and that can compute rational functions over reals at unit cost. It is often referred to as Real RAM model.
Definition
A BSS machine M is given by the set 
of 
instructions, indexed 
. A configuration of M is a tuple 
, 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 
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; copy registers r and w may be changed, either by 
or 
and similarly for w. - 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
- Hypercomputation
- Real computer
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. 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". Bulletin of the American Mathematical Society 21 (1): 1–46. doi:10.1090/S0273-0979-1989-15750-9. Zbl 0681.03020.