Maszyna Blum – Shub – Smale

W teorii obliczeń maszyna Blum – Shub – Smale lub maszyna BSS to model obliczeń wprowadzony przez Lenore Blum , Michaela Shuba i Stephena Smale , mający na celu opisanie obliczeń na liczbach rzeczywistych . Zasadniczo maszyna BSS to maszyna o swobodnym dostępie z rejestrami, które mogą przechowywać dowolne liczby rzeczywiste i które mogą obliczać funkcje wymierne na liczbach rzeczywistych w jednym kroku czasowym. Jest często określany jako Real RAM . Maszyny BSS są potężniejsze niż maszyny Turinga , ponieważ te ostatnie są z definicji ograniczone do skończonego alfabetu. Maszynę Turinga można upoważnić do przechowywania dowolnych liczb wymiernych w pojedynczym symbolu taśmy, czyniąc ten skończony alfabet dowolnie dużym (w kategoriach fizycznej maszyny korzystającej z pamięci opartej na tranzystorach , budującej swoje lokalizacje pamięci z wystarczającej liczby tranzystorów do przechowywania żądanej liczby) , ale nie dotyczy to niezliczonych liczb rzeczywistych (na przykład żadna liczba tranzystorów nie może dokładnie reprezentować Pi ).

Definicja

$instrukcji$ przez listę (do opisania poniżej), indeksowanych $,$ $kropki ,N}$ . Konfiguracja M to krotka ${\ Displaystyle (k, r, w, x)}$ , gdzie k jest indeksem instrukcji do wykonania w następnej kolejności, r i w to rejestry kopii przechowujące nieujemne liczby całkowite i $liczby$ rzeczywistych, . Uważa się, że lista przechowuje zawartość wszystkich rejestrów M. $Obliczenia$ rozpoczynają ${\ displaystyle k = N}$ $gdy$ kończą ; mówi się, że końcowa zawartość x jest wyjściem maszyny.

Instrukcje M mogą być następujących typów:

Obliczenie ${\ Displaystyle (x_ {0})}$ ${\ Displaystyle x_ {0}: = g_ {k}$ podstawienie jest wykonywane, gdzie $} styl wyświetlania g_{k}}$ jest dowolną funkcją wymierną (ilorazem dwóch funkcji wielomianowych o dowolnych współczynnikach rzeczywistych); kopiowanie rejestrów r i w można zmienić albo przez ${\ displaystyle r: = 0}$ albo ${\ displaystyle r: = r + 1}$ i podobnie dla w. Następna instrukcja to k +1.
Gałąź ${\ Displaystyle (x_ {0}, l)}$ : jeśli ${\ Displaystyle x_ {0} \ geq 0}$ to goto ${\ Displaystyle l}$ ; inaczej got k +1.
Kopiuj ( $\ displaystyle x_ {r}, x_ {w}}$ ${\ displaystyle x_ {w}}$ ): zawartość rejestru „odczyt” ${\ displaystyle x_ {r}}$ kopiowana do rejestru „zapisu” ; następna instrukcja to k +1

Zobacz też

Dalsza lektura

Bürgisser, Peter (2000). Kompletność i redukcja w teorii złożoności algebraicznej . Algorytmy i obliczenia w matematyce . Tom. 7. Berlin: Springer-Verlag . ISBN 3-540-66752-0 . Zbl 0948.68082 .
Gradel, E. (2007). „Teoria modeli skończonych i złożoność opisowa”. Teoria modeli skończonych i jej zastosowania (PDF) . Springer-Verlag. s. 125–230. Zbl 1133.03001 .
Blum, Lenore ; Shub, Mike ; Mały, Steve (1989). „O teorii obliczeń i złożoności liczb rzeczywistych: NP-zupełność, funkcje rekurencyjne i maszyny uniwersalne” (PDF) . Biuletyn Amerykańskiego Towarzystwa Matematycznego . 21 (1): 1–46. doi : 10.1090/S0273-0979-1989-15750-9 . Zbl 0681.03020 .
Blum, Lenore ; Cucker, Felipe ; Shub, Mike ; Mały, Steve (1998). Złożoność i obliczenia rzeczywiste . Springera w Nowym Jorku. doi : 10.1007/978-1-4612-0701-6 . ISBN 978-0-387-98281-6 . S2CID 12510680 . Źródło 23 marca 2022 r .