Blum–Shub–Smale maskin

I beräkningsteorin är Blum -Shub-Smale-maskinen , eller BSS-maskinen , en beräkningsmodell introducerad av Lenore Blum , Michael Shub och Stephen Smale , avsedd att beskriva beräkningar över de reella talen . I huvudsak är en BSS-maskin en Random Access Machine med register som kan lagra godtyckliga reella tal och som kan beräkna rationella funktioner över reella i ett enda tidssteg. Den kallas ofta för Real RAM- modell. BSS-maskiner är mer kraftfulla än Turing-maskiner , eftersom de senare per definition är begränsade till ett ändligt alfabet. En Turing-maskin kan bemyndigas att lagra godtyckliga rationella tal i en enda bandsymbol genom att göra det ändliga alfabetet godtyckligt stort (i termer av en fysisk maskin som använder transistorbaserat minne, bygger dess minnesplatser av tillräckligt många transistorer för att lagra önskat antal) , men detta sträcker sig inte till de oräkneliga reella talen (till exempel kan inget antal transistorer representera Pi exakt ).

Definition

En BSS-maskin M ges av en lista $I$ med $N+1$ instruktioner (som beskrivs nedan), indexerade $0,1,\dots ,N$ . En konfiguration av M är en tuppel $(k,r,w,x)$ , där k är indexet för instruktionen som ska köras härnäst, r och w är kopiaregister som innehåller icke-negativa heltal, och $x=(x_{0},x_{1},\ldots )$ är en lista med reella tal, där alla utom ändligt många är noll . Listan $x$ är tänkt att innehålla innehållet i alla register i M. Beräkningen börjar med konfiguration $(0,0,0,x)$ och slutar när $k=N$ ; det slutliga innehållet av x sägs vara maskinens utdata.

Instruktionerna för M kan vara av följande typer:

Beräkning $(x_{0})$ : en substitution $x_{0}:=g_{k}(x)$ utförs, där ${\ displaystyle g_{k}}$ är en godtycklig rationell funktion (en kvot av två polynomfunktioner med godtyckliga reella koefficienter); kopieringsregistren r och w kan ändras, antingen med $r:=0$ eller $r:=r+1$ och på liknande sätt för w. Nästa instruktion är k +1.
Branch $(x_{0},l)$ : om $x_{0}\geq 0$ , gå till ${\displaystyle l$ ; annars fick k +1.
Copy( $x_{r},x_{w}$ ): innehållet i "read"-registret $x_{r}$ kopieras till "write"-registret $x_{w}$ ; nästa instruktion är k +1

Se även

Vidare läsning

Bürgisser, Peter (2000). Fullständighet och minskning av algebraisk komplexitetsteori . Algoritmer och beräkningar i matematik. Vol. 7. Berlin: Springer-Verlag . ISBN 3-540-66752-0 . Zbl 0948.68082 .
Grädel, E. (2007). "Finite Model Theory and Descriptive Complexity". Finita modellteori och dess tillämpningar (PDF) . Springer-Verlag. s. 125–230. Zbl 1133.03001 .
Blum, Lenore ; Shub, Mike ; Smale, Steve (1989). "Om en teori om beräkning och komplexitet över de reella talen: NP-fullständighet, rekursiva funktioner och universella maskiner" ( PDF) . Bulletin från American Mathematical Society . 21 (1): 1–46. doi : 10.1090/S0273-0979-1989-15750-9 . Zbl 0681.03020 .
Blum, Lenore ; Cucker, Felipe ; Shub, Mike ; Smale, Steve (1998). Komplexitet och verklig beräkning . Springer New York. doi : 10.1007/978-1-4612-0701-6 . ISBN 978-0-387-98281-6 . S2CID 12510680 . Hämtad 23 mars 2022 .