- Blum-Shub-Smale machine
In
computation theory , the Blum-Shub-Smale machine, or BSS machine, is a model of computation introduced byLenore Blum ,Michael Shub andStephen Smale , intended to describe computations over the real numbers. Essentially, a BSS machine is aRandom 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:
*Computationx_{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.
*Branchx_{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+1ee 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).
Wikimedia Foundation. 2010.