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 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 $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 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: a substitution $x_ := g_(x)$ is performed, where $g_$ is an arbitrary rational function (a quotient of two polynomial functions with arbitrary real coefficients); 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($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 "written" register $x_w$; 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
*Quantum finite automaton

References

Further reading

*
*
*

{{DEFAULTSORT:Blum-Shub-Smale machine
Models of computation