Blum–Shub–Smale machine explained

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

I of N +1 instructions (to be described below), indexed 0 , 1 , ... , N . A configuration of M is a tuple (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 x = (x _{0,x} _{1,\ldots)} is a list of real numbers, with all but finitely many being zero. The list x is thought of as holding the contents of all registers of M. The computation begins with configuration ( 0 , 0 , 0 ,x) and ends whenever 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

x _{0} : = g _{k} (x) is performed, where 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 r : = 0 or r : = r + 1 and similarly for w . The next instruction is k +1 .

• Branch(

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 "written" register 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.

See also

• Complexity and Real Computation
• General purpose analog computer
• Hypercomputation
• Real computer
• Quantum finite automaton

Further reading

• Book: Blum . Lenore . Lenore Blum . Cucker. Felipe. Felipe Cucker . Shub . Mike . Michael Shub . Smale . Steve . Stephen Smale . Complexity and Real Computation. 1998. Springer New York. 10.1007/978-1-4612-0701-6 . 978-0-387-98281-6. 12510680 . 23 March 2022. en.
• Book: Bürgisser, Peter . Completeness and reduction in algebraic complexity theory . 0948.68082 . Algorithms and Computation in Mathematics . 7 . Berlin . . 2000 . 3-540-66752-0 .
• Book: Grädel, E.. Finite Model Theory and Its Applications. Springer-Verlag. 2007. 1133.03001. 125–230. Finite Model Theory and Descriptive Complexity.

Notes and References

1. Blum . Lenore . Lenore Blum . Shub . Mike . Michael Shub . Smale . Steve . Stephen Smale . 0681.03020 . 1–46 . 10.1090/S0273-0979-1989-15750-9 . 1989. On a Theory of Computation and Complexity over the Real Numbers: NP-completeness, Recursive Functions and Universal Machines. Bulletin of the American Mathematical Society. 21. 1. free .
2. Book: Minsky, Marvin . Marvin Minsky . Computation: Finite and Infinite Machines . Prentice–Hall, Inc. . New Jersey . 1967.