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 often referred to as Real RAM model. BSS machines are more powerful than Turing machines, because the latter are by definition restricted to a finite alphabet. A Turing machine can be empowered to store arbitrary rational numbers in a single tape symbol by making that finite alphabet arbitrarily large, but this does not extend to the uncountable real numbers.

Definition

A BSS machine M is given by a list of instructions, indexed. A configuration of M is a tuple, where k is the index of the instruction to be executed next, r and w are copy registers holding non-negative integers, and is a list of real numbers, with all but finitely many being zero. The list is thought of as holding the contents of all registers of M. The computation begins with configuration and ends whenever ; the final content of x is said to be the output of the machine.
The instructions of M can be of the following types: