Loading AI tools
Model of computation over real numbers From Wikipedia, the free encyclopedia
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.
A BSS machine M is given by a list of instructions (to be described below), indexed . A configuration of M is a tuple , where is the index of the instruction to be executed next, and are 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 is said to be the output of the machine.
The instructions of M can be of the following types:
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.