Apstraktni stroj
Apstraktni stroj, još zvan i apstraktno računalo, je teoretski model računalnog sklopovlja ili programske podrške korištene u teoriji automata. Apstrakcija računarskih procesa se koristi i u računarstvu i u računalnom inženjerstvu, i obično pretpostavlja paradigmu diskretnog vremena.
U teoriji računanja, apstraktni su strojevi često korišteni kao misaoni eksperimenti u vezi izračunljivosti ili analize složenosti algoritama (vidi računska teorija složenosti). Tipičan se apstraktni stroj sastoji od definicije u terminima ulaza, izlaza te skupa dozvoljenih operacija korištenih za pretvorbu prvog u drugo. Najpoznatiji je primjer Turingov stroj.
Složenije definicije kreiraju apstraktne strojeve sa potpunim instrukcijskim skupovima, procesorskim registrima i modelima memorije. Jedan popularni model sličan stvarnim suvremenim strojevima je RAM model, koji dozvoljava slučajan pristup lokacijama u indeksiranoj memoriji. Kako raste razlika u performansama između različitih razina u priručnoj memoriji, postaju sve važniji i modeli osjetljivi na priručnu memoriju, poput modela osetljivog na priručnu memoriju te modela zaboravljive priručne memorije.
Apstraktni se stroj također može odnositi na dizajn mikroprocesora koji tek treba (ili kojeg se ne namjerava) biti sklopovski ostvaren. Apstraktni stroj ostvaren kao programska simulacija, ili za koji postoji interpreter, se zove virtualni stroj.
Uporabom je apstraktnih strojeva moguće izračunati kolika je količina resursa (vremena, memorije itd.) potrebna za obavljanje pojedine operacije bez konstrukcije konkretne implementacije za nju.
Članci koji se bave Turing-ekvivalentnim slijednim modelima apstraktnog stroja
Pristup se sastoji u uzimanju ponešto formalnog taksonomskog pristupa razredbi Turing-ekvivalentnih apstraktnih strojeva. Ova taksonomija ne uključuje konačne automate:
Porodica: Turing-akvivalentan (TE) apstraktni stroj:
Potporodice:
- Potporodica (1) Slijedni TE apstraktni stroj
- Potporodica (2) Paralelni TE apstraktni stroj
Potporodica (1)-- Slijedni TE model apstraktnog stroja: Postoje dva razreda (roda) slijednih TE modela apstraktnog stroja u uporabi (usp. van Emde Boas, npr.):
- Rod (1.1) Tračno zasnovan model Turingovog stroja
- Rod (1.2) Registarski zasnovan registarski stroj
Rod (1.1) -- Tračno zasnovan model Turingovog stroja: Ovo uključuje sljedeće "vrste":
- { jednotračni Turingov stroj, višetračni Turingov stroj, deterministički Turingov stroj, nedeterministički Turingov stroj, Wangov B-stroj, Post-Turingov stroj, stroj proročište, univerzalni Turingov stroj }
Rod (1.2) -- Model registarskog stroja: Ovo uključuje (barem) sljedeće četiri "vrste" (ostale spominje van Emde Boas):
- { (1.2.1) Stroj brojilo, (1.2.2) Stroj sa slučajnim pristupom RAM, (1.2.3) Stroj pohranjenog programa sa slučajnim pristupom RASP, (1.2.4) Pokazivački stroj }
- Vrsta (1.2.1) -- Model stroja brojila:
- { stroj abakusa, Lambekov stroj, Melzakov stroj, Minskyjev stroj, Shepherdson-Sturgisov stroj, programski stroj itd. }
- Vrsta (1.2.2) -- Model stroja sa slučajnim pristupom (RAM):
- { bilo koji model stroja brojila sa dodatnim neposrednim adresiranjem, ali sa instrukcijama u stroju stanja u harvardskoj arhitekturi - bilo koji model sa "akumulatorom" sa dodatnim neposrednim adresiranjem ali sa instrukcijama u stroju stanja u harvardskoj arhitekturi }
- Vrsta (1.2.3) -- Model stroja pohranjenog programa sa slučajnim pristupom (RASP) uključuje
- { bilo koji RAM za programom pohranjenim u registrima slično univerzalnom Turingovom stroju, tj. u von Neumannovoj arhitekturi }
- Vrsta (1.2.4)-- Model pokazivačkog stroja uključuje sljedeće:
- = { Schönhageov stroj za modifikaciju pohrane SMM, Kolmogorov-Uspenskyjev KU-stroj, Knuthov povezujući automat }
Drugi apstraktni strojevi
- ABC programski jezik
- Apstraktna strojna notacija
- ALF programski jezik
- Caml
- Kontekstno neovisna gramatika
- Konačni automat
- SDL
- Apstraktni strojevi za Prolog:
- MMIX
- TDF