Blum–Shub–Smale machine
In
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 of instructions (to be described below), indexed . A configuration of M is a tuple , where k is the index of the instruction to be executed next, r and w 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 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 (a quotient of two polynomial functions with arbitrary real coefficients); registers r and w may be changed, either by or and similarly for w. The next instruction is k+1.
- Branch: if then goto ; else goto k+1.
- Copy(): the content of the "read" register is copied into the "written" register ; the next instruction is k+1
Theory
Blum, Shub and Smale defined the
See also
- Complexity and Real Computation
- General purpose analog computer
- Hypercomputation
- Real computer
- Quantum finite automaton
References
- Zbl 0681.03020.
- ^ Minsky, Marvin (1967). Computation: Finite and Infinite Machines. New Jersey: Prentice–Hall, Inc.
Further reading
- S2CID 12510680. Retrieved 23 March 2022.
- Bürgisser, Peter (2000). Completeness and reduction in algebraic complexity theory. Algorithms and Computation in Mathematics. Vol. 7. Berlin: Zbl 0948.68082.
- Grädel, E. (2007). "Finite Model Theory and Descriptive Complexity". Finite Model Theory and Its Applications (PDF). Springer-Verlag. pp. 125–230. Zbl 1133.03001.