Википедија

Univerzalna Tjuringova mašina

U informatici, univerzalna Tjuringova mašina (UTM) je Tjuringova mašina koja može da simulira proizvoljnu Tjuringovu mašinu proizvoljnog ulaza. Univerzalna mašina u suštini to postiže čitanjem kako opisa mašine da će biti simulirana kao i ulaz istih iz svojih traka. Alan Tjuring je uveo tu mašinu 1936-1937. Ovaj model neki smatraju (na primer, Martin Dejvis (2000)) da su poreklo kompjutera skladištenog programa iskoristio Džon fon Nojman (1946), za "Electronic Computing Instrument" koja sada nosi Fon Nojmanovo ime: Fon Nojmanova arhitektura. Takođe je poznat kao univerzalna računarska mašina, univerzalna mašina (UM), mašina U, U.

U pogledu računarske kompleksnosti, univerzalna Tjuringova mašina sa mnogo traka mora biti samo sporija od logaritamskog faktora u odnosu na mašine koje simulira.

Uvod uredi

 

Svaka Tjuringova mašina izračunava određenu fiksnu parcijalnu izračunljivu funkciju od ulaznih stringova preko svog pisma. U tom smislu se ponaša kao računar sa fiksnim programom. Međutim, možemo da kodiramo akcioni sto bilo koje Tjuringove mašine u string. Tako možemo konstruisati Tjuringovu mašinu da očekuje na njenom snimku string opisuje akcioni sto praćen opisivanjem stringova ulazne trake i izračunava traku da bi kodirana Tjuringova mašina obračunala. Tjuring je opisao takvu konstrukciju u potpunosti detaljno u svojim novinama 1936.:

"Moguće je izmisliti jednu mašinu koja može da se koristi za računanje bilo kojih izračunljivih stringova. Ako je ova mašina U isporučuje sa trakom na početku koja je napisana S. D [" Standardni opis "akcionog stola] neke računarske mašine M, tada U može izračunati istu sekvencu kao M. "

Skladišteni programski računar uredi

Dejvis daje ubedljiv argument da je Tjuringova koncepcija o tome šta je sada poznato kao "skladišteni programski računar", od postavljanja "akcionog stola" -instrukcije za mašinu, u istoj "memoriji" kao i ulazni podaci, snažno uticala Džon fon Nojmanova koncepcija prvog američkog diskretnog-simbola (za razliku od analognog) računara-i EDVAC. Dejvis citira magazin Tajm u tom smislu, da "svako ko kuca na tastaturi ... radi na inkarnaciji Tjuringove mašine" i da je "Džon fon Nojman [napravio] na radu Alana Tjuring" (Dejvis, 2000: 193 citirajući magazin Tajm od 29. marta 1999).

Dejvis pravi slučaj da je Tjuringov automatski računski sistem (ARS) računar "očekivao" pojmove mikroprogramiranja (Mikroprogram) i RISC procesorima (Dejvis 2000: 188). Knut navodi Tjuringov rad na ACE računaru kao dizajniranje "hardvera da bi se olakšala potprogram povezivanja" (Knut 1973: 225); Dejvis je takođe referencirao ovaj posao kao Tjuringovo korišćenje hardverskog "steka" (Dejvis, 2000: 237 fusnota 18).

Kako je Tjuringova mašina podsticala izgradnju računara, UTM je podsticala razvoj u povoju informatike. Rani, ako ne i prvi, monter je predložen "od mladog paklenog programera" za EDVAC (Dejvis 2000: 192). Fon Nojmanov "Prvi ozbiljan program ... [bio je] da je jednostavno sortiranje podataka efikasno" (Dejvis 2000: 184). Knut primećuje da se potprogram koji se vraća ugrađen u samom programu, a ne u posebnim registrima se pripisuje fon Nojmanu i Goldštajneru. Knut dalje navodi da

"Prva rutina tumačenja može se reći da je" Univerzalna Tjuringova mašina "... Rutine tumačenja u konvencionalnom smislu je pomenuo Džon Močli u svojim predavanjima u školi Mur 1946. ... Tjuring je učestvovao u tom razvoju takođe; sistemi tumačenja za Pilot ACE računara su napisani pod njegovom upravom "(Knut 1973: 226).

Dejvis kratko pominje operativne sisteme i prevodioce, kao rezultata pojma programskih-kao-podaci (Dejvis 2000: 185).

Neki, međutim, mogu podići pitanja sa ovim procenama. U to vreme (sredinom 1940-ih do sredine 1950-ih) relativno mali kadar istraživača je blisko povezan sa arhitekturom novih "digitalnih računara". Hao Vang (1954), mladi istraživač u ovom trenutku, je izrazio sledeće zapažanje:

Tjuringova teorija izračunljivih funkcija je zastareo, ali nije mnogo uticao na veliku stvarnu izgradnju digitalnih računara. Ova dva aspekta teorije i prakse razvijene su skoro u potpunosti nezavisno jedan od drugog. Glavni razlog je nesumnjivo da se  logičari koji su zainteresovani za pitanja radikalno razlikuju od onih čime se primenjeni matematičari i elekto inženjeri prvenstveno bave. Ne mogu, međutim, neuspešno da pogode jedan kao prilično čudan da su često isti koncepti izrazili veoma različite uslove u dva razvoja "(Vang 1954, 1957: 63).

Vang se nadao da će njegov rad "povezati dva pristupa." Zaista, Minski to potvrđuje: "da je prva formulacija teorije Tjuringove mašine u kompjuterima poput modela pojavljuje kod Vanga (1957)" (Minski 1967: 200). Minski nastavlja da pokazuje Tjuringovu ekvivalentnost kanter mašine.

Što se tiče smanjenja računara na jednostavne Tjuringove ekvivalentne modele (i obrnuto), Minskijeva oznaka Vanga kao što je "prva formulacija" je otvorena za raspravu. Iako obe knjige. Minskijeva iz 1961. godine i Vangova iz 1957. citiraju Šeperdsona i Sturdžisa (1963), one takođe navode i sumiraju u nekim detaljima rad evropskih matematičara Kapenst (1959), Ersov (1959), i Piter (1958). Imena matematičara Hermes (1954, 1955, 1961) i Kapenst (1959) pojavljuju se u bibliografiji oba, i Šeperdson-Sturdžisa (1963) i Elgot-Robinsona (1961). Dva druga značajna imena su kanadski istraživači Melzak (1961) i Lambek (1961). Za mnogo više pogledajte Ekvivalencije Tjuringove mašine; reference se mogu naći na Registrujućoj mašini.

 Matematička teorija uredi

Sa ovim kodiranjem akcionih tabela i nizova postaje moguće, u principu, za Tjuring mašine da odgovori na pitanja o ponašanju drugih Tjuring mašina. Većina ovih pitanja, međutim, su nerešiva, što znači da je u pitanju funkcija koja se ne može mehanički izračunati. Na primer, problem utvrđivanja da li će proizvoljna Tjuringova mašina zaustaviti na određenom ulazu, ili na svim ulazima, poznato kao Halting problem, je pokazao da, generalno, nerešivo u Tjuringovom originalnom radu. Rajsova teorema pokazuje da bilo koje ne-trivijalno pitanje o izlazu na Tjuringovoj mašini je nerešiv.

Univerzalna Tjuringova mašina može da izračuna bilo koju rekurzivnu funkciju, odlučuje o bilo kojem rekurzivnom jeziku, i prihvatiti svaki rekurzivno prebrojiv jezik. Prema Čurč-Tjuringovoj tezi, problemi rešivi Univerzalnom Tjuringovom mašinom su upravo ti problemi rešivi algoritmima ili efikasnom metodom obračuna, za bilo kakve razumne definicije tih pojmova. Iz tih razloga, Univerzalna Tjuringova mašina služi kao standard prema kome se upoređuju računarski sistemi, kao i sistem koji može da simulira Univerzalnu Tjuringovu Mašinu i ona se zove Tjuring potpuna.

Apstraktna verzija Univerzalne Tjuringove mašine je univerzalna teorema, računarska funkcija koja se može koristiti za izračunavanje neke druge računarske funkcije. Univerzalna teorema dokazuje postojanje takve funkcije.

Efikasnost uredi

Bez gubitka opštosti, ulaz Tjuringove mašine može se pretpostaviti da je u alfabetu {0, 1}; bilo koji drugi konačni alfabet može biti kodiran preko {0, 1}. Ponašanje Tjuringove mašine M utvrđeno je njegovom tranzicijskom funkcijom. Ova funkcija se takođe može lako kodirati kao string nad alfabetom {0, 1}, . Veličina alfabeta M, broj traka koje ima, i veličina prostora stanja se može zaključiti iz stola tranzicijske funkcije. Istaknute države i simboli mogu biti identifikovani po svom položaju, na primer prve dva stanja mogu da po običaju budu kreni i zaustavi stanje. Prema tome, svaka Tjuringova mašina može da se kodira kao string nad alfabetom {0, 1}. Osim toga, mi sazivamo da svako nevažeće kodiranje mape na trivijalnoj Tjuringovoj mašini odmah prestane, i da svaka Tjuringova mašina može imati neograničen broj kodiranja postavljanjem kodiranja sa proizvoljnim brojem (recimo) 1 na kraju, baš kao i komentare rade u programskom jeziku. To ne bi trebalo da bude nikakvo iznenađenje da možemo postići to kodiranje s obzirom na postojanje Gudelovog broja i računarske ekvivalencije između Tjuringove mašine i μ-rekurzivne funkcije. Slično tome, naša konstrukcija asocira na svaki binarni string α, Tjuringove mašine Mα.

Polazeći od navedenog kodiranja, 1966 F. K. Hejni i R. E. Sterns pokazalu su da data Tjuringova mašina Mα koja se zaustavlja na ulazu h u N koraka, onda postoji multi-traka univerzalne Tjuringove mašine koja zaustavlja na ulazu α,  x (s obzirom na različite trake) u CN log N, gde je C specifičn konstanta mašine koja ne zavisi od dužine ulaza x, ali ne zavise od M azbučne veličine, broja traka, i broja stanja. Efektivno, ovo je O (N log N) simulacija.

Najmanje mašine uredi

Kada je Alan Tjuring došao na ideju univerzalne mašine imao je u vidu najjednostavniji model računara dovoljno snažan da se izračunaju sve moguće funkcije koje se mogu izračunati. Klod Šenon je prvo eksplicitno postavio pitanje pronalaženja najmanje moguće univerzalne Tjuringove mašina u 1956. On je pokazao da su dva simbola bila dovoljna sve dok se koristi stanje (ili obrnuto), i da je uvek bilo moguće razmeniti stanja simbola.

Marvin Minski je otkrio 7-stanjsku 4-simbolsku univerzalnu Tjuringovu Mašinu 1962. koristeći 2-označavajuća sistema. Druge male univerzalne Tjuringove mašine su u međuvremenu pronađene od strane Jurija Rogožina i drugi su proširivali ovaj pristup simulacije oznaka sistema. Ukoliko označimo od (m, n) klasa UTMS slovom m stanja i n simbole sledeću torku su pronašli: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9), i (2, 18). Rogožinova (4, 6) mašina koristi samo 22 instrukcije, i nestandardna UTM manje opisne složenosti je poznata.

Međutim, generalizujući standardni model Tjuringove mašine on priznaje čak i manje UTM-e. Jedna takva generalizacija je da omogući kontinualno ponavljane reči o jednoj ili obe strane ulaza Tjuringove mašine, čime produžava definiciju univerzalnosti i poznato kao "polu-slaba" ili "slaba" univerzalnost, respektivno. Polu-slabe univerzalne Tjringove mašine koje simuliraju Pravilo 110 ćelijskog automata su date za (6, 2), (3, 3) i (2, 4) stanje-simbol parova. Dokaz o univerzalnosti za Volframovu 2-stanja3-simbola Tjuringovu mašinu dodatno proširuje pojam slabe univerzalnosti, dozvoljavajući određene neperiodične početne konfiguracije. Druge varijante na standardnim modelom Tjuringove mašine koje daju male UTM-e uključuju mašine sa više traka ili traka višestrukih dimenzija, i mašina zajedno sa konačnim automatom.

Mašine bez unutrašnjih stanja uredi

Ako dozvolite više glava na Tjuringovoj mašini onda možete imati Tjuring Mašine bez ikakvih unutrašnjih stanja uopšte.  "Stanja" su kodirana kao deo trake. Na primer, razmotrimo traku sa 6 boja: 0, 1, 2, 0A, 1A, 2A. Razmislite o traci kao što je 0,0,1,2,2A, 0,2,1 gde se troglava Tjuringova mašina nalazi preko trostrukog (2,2A, 0). Pravila onda pretvaraju bilo koju trostruku u drugu trostruku i pomera 3-glave ulevo ili udesno. Na primer, pravila mogu pretvoriti (2,2A, 0) do (2,1,0) i pomerati glavu levo. Tako se u ovom primeru mašina ponaša kao trobojna Tjuringova mašina sa unutrašnjim stanjima A i B (zastupa bez slova). Slučaj za dvoglavu Tjuringovu mašinu je vrlo slična. Tako dvoglava Tjuringova mašina može biti univerzalna sa 6 boja. Nije poznato koji je najmanji broj boja potreban za višeglavu Tjuringovu mašinu ili ako je dvobojna Univerzalna Tjuringova mašina moguća sa više glava. To takođe znači da se preprave pravila Tjuuringove potpunosti jer su trostruka pravila ekvivalentna da preprave pravila. Proširivanjem trake na dve dimenzije sa glavom uzorkovanja slova i to su 8 komšija, samo 2 boje su potrebne, kao na primer, boja može da se kodira u vertikalnom trostrukom obrascu kao što je 110.

Primer kodiranja univerzalne mašine uredi

Za one koji bi preduzeli izazov dizajniranja UTM tačno onako kako je naveo Tjuring - videli članak  Dejvis u Kouplendu (2004: 103ff). Dejvis ispravlja greške u originalu i pokazuje kako bi niz uzoraka izgledao. On tvrdi da je uspešno pokrenuta (donekle pojednostavljen) simulacija.

Sledeći primer je uzet od Tjuringa (1936). Više o ovom primeru vidi stranu Primeri Tjuringove Mašine.

Tjuring je koristio sedam simbola {A, C, D, R, L, N, ;} da kodira svaki 5-torku; kako je opisano u članku Tjuringova mašina, njegove 5-torke su samo vrsta  N1, N2, i N3. Broj svake "m-konfiguracije" (uputstva, stanja) je predstavljen sa "D" praćeno unarnim nizom petice, npr "q3" = DAAA. Na sličan način kodira simbole prazne kao "D", simbol "0" kao "DC", simbol "1" kao DCC, itd. Simboli "R", "L" i "N" ostaje kao što je.

Nakon kodiranja svake 5-torke zatim "montira" u string kao što je prikazano u sledećoj tabeli:

Trenutna

m-konfiguracija

Simbol

na

traci

Štampa-

operacija

Traka-pomeranje Konačna

m-konfiguracija

Trenutna

m-konfiguracija-kod

Simbol trake Kod operacije štampanja Kod pomeranja trake Kod konačne m-konfiguracije Kod 5-torke
q1 prazno P0 R q2 DA D DC R DAA DADDCRDAA
q2 prazno E R q3 DAA D D R DAAA DAADDRDAAA
q3 prazno P1 R q4 DAAA D DCC R DAAAA DAAADDCCRDAAAA
q4 prazno E R q1 DAAAA D D R DA DAAAADDRDA

Konačno, kodovi za sve četiri 5-torke su nanizani zajedno u kodu početo kao ";" i odvojeno sa ";" tj .:

;DADDCRDAA;DAADDRDAAA;DAAADDCCRDAAAA;DAAAADDRDA

Ovaj kod je stavljen na alternativnim trgovima-u "F-trgovima" - ostavljajući "E-ogradu" (oni su odgovorni za brisanje) praznu. Konačna skupina koda na traci za U-mašinu se sastoji od postavljanja dva specijalna simbola ("e") jedan za drugim, zatim kod izdvojili na alternativnim trgovima, i na kraju dva simbola dvotačke"::" (prazno je prikazano ovde sa "." radi jasnoće):

ee.;.D.A.D.D.C.R.D.A.A.;.D.A.A.D.D.R.D.A.A.A.;.D.A.A.A.D.D.C.C.R.D.A.A.A.A.;.D.A.A.A.A.D.D.R.D.A.::......

U-smašinski akcijski sto (sto tranzicije stanja) je odgovoran za dekodiranje simbola. Tjuringov akcijski sto vodi evidenciju o njegovom mestu sa markerima ""u", "v", "x", "y", "z" postavljajući ih u "E-ogradu" na desnoj strani "označene simbolom" - na primer, , da označi instrukciju z se nalazi na desnoj strani ";" h drži mesto u odnosu na trenutnu "m-konfiguraciju" DAA. Akcijski sto U-mašine će gurati ove simbole oko (briše ih i stavlja ih u različitim lokacijama) i računanje napreduje:

ee.; .D.A.D.D.C.R.D.A.A. ; zD.A.AxD.D.R.D.A.A.A.;.D.A.A.A.D.D.C.C.R.D.A.A.A.A.;.D.A.A.A.A.D.D.R.D.A.::......

Tjuringov akcijski sto za njegovu U-mašinu je veoma umešan.

Izvestan broj drugih komentatora (naročito Penrouz 1989) pružaju primere načina da kodiraju uputstva za Univerzalne mašine. Kako radi Penrose, većina komentatora koristiti samo binarni simbole, odnosno samo simbole {0, 1}, ili {prazno, oznaka | }. Penrouz ide dalje i piše da celim svojim kodom U-mašine (Penrouz 1989: 71-73). On tvrdi da je zaista kod U-mašine, ogroman broj koji obuhvata skoro 2 cele stranice 0 i 1. Za čitaoce zainteresovane za jednostavnije kodiranje za Post-Tjuringove mašine rasprava  Dejvisa u Stinu (Stin 1980: 251ff) može biti korisno.

Asperti i Rićioti opisali su multi-trake UTM definisane komponovanjem osnovne mašine sa veoma jednostavnom semantikom, pre nego što je eksplicitno davanje akcionog stola. Ovaj pristup je bio dovoljno modularan da im omoguće da formalno dokažu ispravnost mašine u Matitinom dokazu asistenta.

Vidi još uredi

Literatura uredi

Opšte reference

  • Arora, Sanjeev; Barak, Boaz . "Complexity Theory: A Modern Approach". Cambridge University Press. Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.  section 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9"

Originalni radovi

Seminalni radovi

Implementacije

Formalne potvrde

Ostale reference

  • Copeland, Jack, ur. (2004). The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma. Oxford UK: Oxford University Press. ISBN 978-0-19-825079-1. 
  • Davis, Martin (1980). „What is Computation”. Ur.: Steen, Lynn Arthur. Mathematics Today: Twelve Informal Essays. New York NY: Vintage Books (Random House). ISBN 978-0-394-74503-9. 
  • Goldstine, Herman H.; von Neumann, John. Planning and Coding of the Problems for an Electronic Computing Instrument. Institute for Advanced Study (Rep. 1947 ed.) (Princeton).
  • Bell, C. Gordon; Newell, Allen (1971). Computer Structures: Readings and Examples. New York: McGraw-Hill Book Company. str. 92–119. ISBN 978-0-07-004357-2. 
  • Herken, Rolf (1995). The Universal Turing Machine – A Half-Century Survey. Springer Verlag. ISBN 978-3-211-82637-9. 
  • Knuth, Donald E.. (1968), The Art of Computer Programming Second Edition, Volume 1/Fundamental Algorithms (First ed.), Addison-Wesley Publishing Company The first of Knuth's series of three texts.
  • Kudlek, Manfred; Rogozhin, Yurii (2002), "A universal Turing machine with 3 states and 9 symbols", LNCS (Springer) 2295: 311–318, . doi:10.1007/3-540-46011-x 27 (neaktivno 2023-09-04) Proverite vrednost parametra |doi= (pomoć).  Nedostaje ili je prazan parametar |title= (pomoć)
  • Minsky, Marvin , "Size and Structure of Universal Turing Machines using Tag Systems, Recursive Function Theory", Proc. Symp. Pure Mathematics . . Providence RI: American Mathematical Society. 1962.  Nedostaje ili je prazan parametar |title= (pomoć) 5: 229–238
  • Neary, Turlough; Woods, Damien (2009), "Four Small Universal Turing Machines", Fundamenta Informaticae 91 (1)
  • Neary, Turlough; Woods, Damien (2009b), Small Weakly Universal Turing Machines, 17th International Symposium on Fundamentals of Computation Theory, Springer LNCS (5699). str. 262–273
  • Penrose, Roger (1989). The Emperor's New Mind. Oxford UK: Oxford University Press. ISBN 978-0-19-851973-7. 
  • Rogozhin, Yurii (1996). „Small universal Turing machines”. Theoretical Computer Science. 168 (2): 215—240. doi:10.1016/S0304-3975(96)00077-1. 
  • Shannon, Claude . "A Universal Turing Machine with Two Internal States", Automata Studies, Princeton, NJ: Princeton University Press. (1956). str. 157–165
  • Turing, A.M. (1936), "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 2 42: 230–65.
  • Turing, A. M. (1938). „On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction”. Proceedings of the London Mathematical Society: 544—546. doi:10.1112/plms/s2-43.6.544. 
  • Davis ed, Martin (1965). The Undecidable (Reprint ed.). Hewlett, NY: Raven Press. (1938). str. 115–154. with corrections to Turing's UTM by Emil Post cf footnote 11 pg:299
Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Универзална_Тјурингова_машина&oldid=27672966”