Blum-Shub-Smale-Maschine

In der Rechentheorie ist die Blum-Shub-Smale-Maschine oder BSS-Maschine ein Rechenmodell, das von Lenore Blum, Michael Shub und Stephen Smale eingeführt wurde, um Berechnungen über die reellen Zahlen zu beschreiben. Im Wesentlichen handelt es sich bei einer BSS-Maschine um eine Zufallszugriffsmaschine mit Registern, die beliebige reelle Zahlen speichern und in einem einzigen Zeitschritt rationale Funktionen über reelle Zahlen berechnen kann. Sie wird oft auch als Real-RAM-Modell bezeichnet. BSS-Maschinen sind leistungsfähiger als Turingmaschinen, da letztere per Definition auf ein endliches Alphabet beschränkt sind.^[1] Eine Turingmaschine kann in die Lage versetzt werden, beliebige rationale Zahlen in einem einzigen Bandsymbol zu speichern, indem man das endliche Alphabet beliebig groß macht (im Sinne einer physikalischen Maschine, die einen transistorbasierten Speicher verwendet, indem sie ihre Speicherplätze aus genügend Transistoren aufbaut, um die gewünschte Zahl zu speichern), aber dies gilt nicht für die nicht abzählbaren reellen Zahlen (zum Beispiel kann keine Anzahl von Transistoren die Kreiszahl ${\displaystyle \pi }$ (Pi) genau darstellen).^[2][3]

1. ↑ Peter Bürgisser: Completeness and reduction in algebraic complexity theory. Springer, Berlin 2000, ISBN 3-540-66752-0. 
2. ↑ L. Blum, M. Shub, S. Smale: On a theory of computation over the real numbers; NP completeness, recursive functions and universal machines. In: [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science. IEEE, 1988, doi:10.1109/sfcs.1988.21955. 
3. ↑ F. Cucker: The Collected Papers of Stephen Smale (In 3 Volumes) - Volume 3. World Scientific Publishing Company, 2000, ISBN 978-981-279-283-9.