In computation theory, the Blum–Shub–Smale machine, or BSS machine, is a model of computation introduced by Lenore Blum

Lenore Blum

Lenore Blum is a distinguished professor of Computer Science at Carnegie Mellon. She received her Ph.D. in mathematics from the Massachusetts Institute of Technology in 1968. Her dissertation was on Generalized Algebraic Structures and her advisor was Gerald Sacks...

, Michael Shub and Stephen Smale

Stephen Smale

Steven Smale a.k.a. Steve Smale, Stephen Smale is an American mathematician from Flint, Michigan. He was awarded the Fields Medal in 1966, and spent more than three decades on the mathematics faculty of the University of California, Berkeley .-Education and career:He entered the University of...

, intended to describe computations over the real numbers. Essentially, a BSS machine is a Random Access Machine

Random access machine

In computer science, random access machine is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers...

with registers that can store arbitrary real numbers and that can compute rational functions over reals at unit cost.

Definition

A BSS machine M is given by the set of instructions, indexed . A configuration of M is a tuple , 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 and ends whenever – the 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 is performed, where is an arbitrary rational function; copy registers r and w may be changed, either by or and similarly for w.
• Branch: if then goto l else goto k+1.
• Copy(): the content of the "read" register is copied into the "write" register ; the next instruction is k+1