Blum–Shub–Smale machine

From Wikipedia, the free encyclopedia

(Redirected from Blum Shub Smale machine)

Jump to: navigation, search

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.

[edit] 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:

Computation $(x_{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.
Branch $(x_{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+1