Jump to content

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

## References

1. ^ 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" (PDF). Bulletin of the American Mathematical Society. 21 (1): 1–46. doi:10.1090/S0273-0979-1989-15750-9. Zbl 0681.03020.
2. ^ Minsky, Marvin (1967). Computation: Finite and Infinite Machines. New Jersey: Prentice–Hall, Inc.