Blum -Shub -SMALE -Maschine

Im Berechnungstheorie, das Blum -Shub -SMALE -Maschine, oder BSS -Maschine, ist ein Berechnungsmodell Vorgestellt von Lenore Blum, Michael Shub und Stephen Smale, beabsichtigt, Berechnungen über die zu beschreiben reale Nummern. Im Wesentlichen ist eine BSS -Maschine a Zufallszugriffsmaschine mit Registern, die willkürliche reale Zahlen speichern und berechnen können rationale Funktionen über Real in einem einzigen Zeitschritt. Es wird oft als als bezeichnet Echter Ram Modell. BSS -Maschinen sind leistungsfähiger als Turing -Maschinen, weil letztere per Definition auf ein endliches Alphabet beschränkt sind. Eine Turing -Maschine kann befugt sein, willkürlich zu speichern Rationale Zahlen in einem einzigen Bandsymbol, indem Sie dieses endliche Alphabet willkürlich groß machen (in Bezug auf eine physische Maschine verwendet Transistor-basierten Speicher, erstellen Sie seine Speicherorte von genügend Transistoren, um die gewünschte Zahl zu speichern), dies erstreckt sich jedoch nicht auf die unzähliger reelle Zahlen (z. B. kann keine Anzahl von Transistoren genau darstellen Pi).

Definition

Eine BSS -Maschine M wird durch eine Liste angegeben ${\ displayStyle i}$ von ${\ displayStyle n+1}$ Anweisungen (nachstehend beschrieben werden), indiziert ${\ displayStyle 0,1, \ dots, n}$ . Eine Konfiguration von M ist ein Tupel ${\ displayStyle (k, r, w, x)}$ , wo k ist der Index der Anweisung, die als nächstes ausgeführt wird, r und w sind Kopieregister, die nicht negative Ganzzahlen halten, und ${\ displayStyle x = (x_ {0}, x_ {1}, \ ldots)}$ ist eine Liste realer Zahlen, wobei alle ab aber endlich viele Null sind. Die Liste ${\ displayStyle x}$ wird als Halten des Inhalts aller Register von M angesehen. Die Berechnung beginnt mit der Konfiguration ${\ displayStyle (0,0,0, x)}$ und endet wann immer ${\ displayStyle k = n}$ ; der letzte Inhalt von x soll die Ausgabe der Maschine sein.

Die Anweisungen von m können die folgenden Typen haben:

Berechnung ${\ displayStyle (x_ {0})}$ : eine Substitution ${\ displayStyle x_ {0}: = g_ {k} (x)}$ wird durchgeführt, wo ${\ displayStyle g_ {k}}$ ist eine willkürliche rationale Funktion (ein Quotient von zwei Polynomfunktionen mit willkürlichen realen Koeffizienten); Register kopieren r und w kann entweder durch geändert werden durch ${\ displayStyle r: = 0}$ oder ${\ displayStyle r: = r+1}$ und ähnlich für w. Die nächste Anweisung ist k+1.
Zweig ${\ displayStyle (x_ {0}, l)}$ : wenn ${\ displayStyle x_ {0} \ geq 0}$ dann geh zu ${\ displayStyle l}$ ; sonst goto k+1.
Kopieren( ${\ displaystyle x_ {r}, x_ {w}}$ ): Der Inhalt des "Lesens" -Registers ${\ displayStyle x_ {r}}$ wird in das Register "Schreiben" kopiert ${\ displayStyle x_ {w}}$ ; Die nächste Anweisung ist k+1