Blum–Shub–Smale machine

Short description: Model of computation over real numbers

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 closely related to the Real RAM model.

BSS machines are more powerful than Turing machines, because the latter are by definition restricted to a finite set of symbols. A Turing machine can represent a countable set (such as the rational numbers) by strings of symbols, but this does not extend to the uncountable real numbers.

Definition

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

Theory

Blum, Shub and Smale defined the complexity classes P (polynomial time) and NP (nondeterministic polynomial time) in the BSS model. Here NP is defined by adding an existentially-quantified input to a problem. They give a problem which is NP-complete for the class NP so defined: existence of roots of quartic polynomials. This is an analogue of the Cook-Levin Theorem for real numbers.

See also

• Complexity and Real Computation
• General purpose analog computer
• Hypercomputation
• Real computer

Further reading

• Blum, Lenore; Cucker, Felipe; Shub, Mike; Smale, Steve (1998) (in en). Complexity and Real Computation. Springer New York. doi:10.1007/978-1-4612-0701-6. ISBN 978-0-387-98281-6. https://link.springer.com/book/10.1007/978-1-4612-0701-6. Retrieved 23 March 2022. 
• 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. 
• Grädel, E. (2007). "Finite Model Theory and Descriptive Complexity". Finite Model Theory and Its Applications. Springer-Verlag. pp. 125–230. http://www.logic.rwth-aachen.de/pub/graedel/FMTbook-Chapter3.pdf.