# Blum–Shub–Smale machine

(Redirected from 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 ${\displaystyle I}$ of ${\displaystyle N+1}$ instructions, indexed ${\displaystyle 0,1,\dots ,N}$. A configuration of M is a tuple ${\displaystyle (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 ${\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${\displaystyle (x_{0})}$: a substitution ${\displaystyle x_{0}:=g_{k}(x)}$ is performed, where ${\displaystyle g_{k}}$ is an arbitrary rational function; copy registers r and w may be changed, either by ${\displaystyle r:=0}$ or ${\displaystyle r:=r+1}$ and similarly for w.
• Branch${\displaystyle (x_{0},l)}$: if ${\displaystyle x_{0}\geq 0}$ then goto l else goto k+1.
• Copy(${\displaystyle x_{r},x_{w}}$): the content of the "read" register ${\displaystyle x_{r}}$ is copied into the "write" register ${\displaystyle x_{w}}$; the next instruction is k+1