Pokazivačka mašina

U teorijskom računarstvu, pokazivačka mašina predstavlja "atomistički" apstraktni mašinski model računanja nalik na mašinu sa slučajnim pristupom.

U zavisnosti od vrste, pokazivačka mašina se može nazvati i povezujućim automatom, KU-mašinom, SMM, atomističkom LISP masinom, drvo-pokazivačkom mašinom itd. Najmanje tri glavne vrste postoje u literaturi - Kolmogorov-Uspenski model(KUM, KU-mašina), Knut povezivajući automat, i Šonhagov model mašine za modifikaciju skladišta (SMM). SMM je najčešći. Mašina prima ulazne podatke sa trake "samo za čitanje", sekvence simbola napravljene od bar dva simbola, npr. 0 i 1, i piše izlazne podatke na traku "samo za pisanje". Da bi transformisala sekvencu simbola, tj. ulazne podatke u sekvencu simbola kao izlazne podatke, mašina poseduje "program" - mašinu konačnog stanja, koju čini memorija i lista instrukcija. Preko svog stanja mašina program čita ulazne simbole, operiše na svojoj strukturi za skladištenje - kolekciji čvorova(registara) međusobno povezanih "granama" (pokazivačima označenim simbolima npr. 0,1) i piše simbole na izlaznoj traci.

Pokazivačka mašina ne može da vrši aritmetičke operacije. Računanje se svodi na čitanje ulaznih simbola, njihovu izmenu, obavljanje raznih testova na strukturi skladišta - šablone čvorova i pokazivača, i izlaz simbola na osnovu testova. "Informacija" se nalazi u skladišnoj strukturi.

Tipovi pokazivačke mašine

I Gurevic i Ben-Amram su napravili listu veoma sličnih atomskih modela apstraktnih mašina. Ben-Amram veruje da postoje atomski modeli (kojih ima šest) i modeli višeg nivoa. Tri glavna atomska modela su:

• Šonhagov model mašine sa modifikacijom skladišta
• Kolmogorov-Uspenski mašine
• Knutov povezivajući automat

Ali Ben-Amram dodaje i:

• Atomističku "isključivo-LISP" mašinu
• Atomističku "potpuno-LISP" mašinu
• Generalnu atomističku pokazivačku mašinu
• Jone's I jezik - dva tipa

Problemi modela pokazivačke mašine

Upotreba modela u teoriji kompleksnosti: van Emde Boas (1990) izražava zabrinutost da ovaj oblik apstraktnog modela: "da je interesantni teorijski model, ali njegova privlačnost kao fundamentalnog modela za teoriju kompleksnosti je pod znakom pitanja. Njegova mera vremena se bazira na uniformnom vremenu u kontekstu da ova mera potcenjuje pravu vremensku kompleksnost"

Gurevic 1988. godine takođe izražava zabrinutost:

"...pragmatično gledano, Schonage model daje dobru meru složenosti vremena što se tiče trenutnog napretka...iako bih voleo nešto slično računarima sa slučajnim pristupom Angluina i Valijanta", čime misli na Angluin D. i Valiant L.G., "Brzi probabilistički algoritmi za hamiltonske krugove i poklapanja". Činjenica je da Schoinageg sam demonstrira ekvivalencije u realnom vremenu svoje dve mašine sa slučajnim pristupom, modele "RAM0" i "RAM1", što vodi do pitanja neophodnosti SMM za studije kompleksnosti.

Moguća korišćenja modela

Ipak, Schonage opisuje množenje celih brojeva u linearnom vremenuu, a Gurevic se pita da li paralelna KU masina podseća na ljudski mozak.

Šonhagova mašina modifikacije skladišta - model SMM

Čini se da je Šonhagov SMM model najčešći i najviše prihvaćen. Sasvim je različit od modela registarske mašine i drugih uobičajenih računskih modela, kao što su Turingova mašina na bazi trake ili označene rupe na brojačkoj mašini.

Računar se sastoji od fiksnog alfabeta ulaznih simbola, i promenljivog usmerenog grafa, tj. dijagrama stanja, sa strelicama označenim simbolima alfabeta. Svaki čvor grafa ima tačno jednu izlaznu strelicu označenu svakim simbolom, iako se neke od njih vraćaju u originalni čvor. Jedan fiksirani čvor grafa je označen kao početni čvor.

Svaka reč simbola u alfabetu se može prevesti kao put kroz mašinu. npr. 10011 se može prevesti kao put 1 od početnog čvora zatim put 0 od kranjnjeg čvora, zatim put 1, pa put 1, pa put 1. Put se može identifikovati kao rezultujući čvor, ali identifikacija će se menjati kako se graf menja u toku računanja.

Mašina može da primi instrukcije koje menjaju izgled grafa. Osnovne instrukcije su nove w instrukcije, koje kreiraju novi čvor koji je rezultat niza w, a skup w do v instrukcija koji ponovo usmerava granu do drugog čvora. Ovde w i v predstavljaju reči, v je prethodna reč npr. prethodno napravljeni niz simbola, tako da ponovo usmerena grana pokazuje unazad ka starom čvoru koji je rezultat tog niza.

Koraci u kreiranju novog čvora u mašini sa dva simbola {0,1}

Kada se susretnemo sa novom reči, što je u ovom slučaju 11, mašina je odgovorna za kreiranje novog čvora 3 i pokazuje odgovarajuću granu ka njemu, zatim kreira dva nova pokazivača, oba pokazuju nazad ka starom čvoru, što je u ovom primeru 2.

(1) novi w: pravi novi čvor. W predstavlja novu reč koja pravi novi čvor. Mašina čita reč w, zatim put predstavljen simbolima w dok mašina ne dođe do poslednjeg, "dodatnog" simbola u reči. Dodatni simbol primorava poslednje stanje da napravi novi čvor, i obrće odgovarajuću strelicu (označenu tim simbolom) sa stare pozicije da pokazuje na novi čvor. Novi čvor obrće sve grane nazad na poslednje stanje, kada su bile neusmerene, smislu da novi čvorovi "spavaju", čekajući na dodelu. U slučaju početnog čvora takođe ćemo početi sa obe grane koje pokazuju nazad ka sebi.

Npr. neka je "w" 10110[1], gde je finalni karakter u zagradi kako bi označio svoj posebni status. Uzimamo granu 1 čvora da pokazuje na novi, 7. čvor. Dve grane ovog čvora zatim pokazuju nazad na 6. čvor.

(2) skup w do v: pomeriti granu(strelicu) od puta predstavljenog rečju w do prethodnog čvora predstavljenog rečju v. Opet je poslednja strelica u putu ta koja će biti preusmerena.

Primer: skup 1011011 na 1011, nakon instrukcije iznad, promeniće 1 strelicu novog čvora na 101101 da pokaže na peti čvor na putu, dostignut 1011. Onda bi put 1011011 imao isti rezultat kao 1011.

(3) ako je v=w, onda instrukcija z: Uslovna instrukcija koja upoređuje dva puta predstavljena rečima w i v da vidi da li se završavaju u istom čvoru. Ako je to tačno, pređi na instrukciju z; ako nije tačno, nastavi. Ova instrukcija ima istu svrhu kao i njen pandan u registarskoj ili Wang-b mašini, što odgovara sposobnosti Turingove mašine da pređe na sledeće stanje.

Knutov model povezivajućeg automata

Prema Šonhageu, Knut je naveo da se SMM model poklapa sa specijalnim tipom povezivajućeg automata ukratko objašnjenog u knjizi "The art of computer programming".

Kolmogorov - Uspenski model mašine - KU mašina

KUM se razlikuje od SMM u tome što dozvoljava samo invertibilne pokazivače: za svaki pokazivač od čvora x do čvora y, inverzibilni pokazivač od y do x mora biti prisutan. S obzirom da izlazni pokazivači moraju biti obeleženi različitim simbolima abecede, oba KUM i SMM grafa imaju O(1) izlazni stepen. Međutim, inverzibilnost pokazivača KUM ograničava ulazni stepen na O(1), takođe. Dodatna razlika je u tome što je KUM zamišljena kao generalizacija Turingove mašine, tako da omogućava trenutno "aktivnim" čvorovima da se pomeraju u okviru grafa. Shodno tome, čvorovi se mogu odrediti pojedinim karakterima umesto rečima, a akcije koje treba preduzeti mogu se odrediti tabelom stanja umesto fiksiranom listom instrukcija.

Vidi još

• Registarska mašina
• Mašina sa slučajnim pristupom
• Mašina sa slučajnim pristupom uskladištenog programa
• Turingova mašina
• Post turingova mašina

Literatura

• "On Kolmogorov Machines And Related Issues", Yuri Gurevich
• Andrey Kolmogorov and V. Uspenskii, On the definition of an algorithm,Uspehi Mat. Nauk. 13 (1958), 3-28. English translation in American Mathematical Society Translations, Series II, Volume 29 . (1963). стр. 217–245.
• J. E. Savage (1998), Models of Computation: Exploring the Power of Computing. Addison Wesley Longman.
• A. Schōnhage (1970), Universelle Turing Speicherung, Automatentheorie und Formale Sprachen, Dōrr, Hotz, eds. Bibliogr. Institut, Mannheim, (1970). стр. 69–383.