Univerzální Turingův stroj - Universal Turing machine

v počítačová věda, a univerzální Turingův stroj (UTM) je Turingův stroj který simuluje libovolný Turingův stroj na libovolném vstupu. Univerzální stroj toho v zásadě dosahuje čtením popisu simulovaného stroje i vstupu do tohoto stroje z vlastní pásky. Alan Turing představil myšlenku takového stroje v letech 1936–1937. Tento princip je považován za původ myšlenky a počítač s uloženým programem používá John von Neumann v roce 1946 pro „Electronic Computing Instrument“, který nyní nese von Neumannovo jméno: the von Neumannova architektura.^[1]

Ve smyslu výpočetní složitost, vícepásmový univerzální Turingův stroj stačí být pomalejší podle logaritmický faktor ve srovnání se stroji, které simuluje.^[2]

Úvod

Každý Turingův stroj počítá určité pevné částečný vypočítatelná funkce ze vstupních řetězců přes jeho abeceda. V tomto smyslu se chová jako počítač s pevným programem. Můžeme však zakódovat akční tabulku libovolného Turingova stroje do řetězce. Můžeme tedy zkonstruovat Turingův stroj, který na své pásce očekává řetězec popisující tabulku akcí následovaný řetězcem popisujícím vstupní pásku, a vypočítá pásku, kterou by zakódoval Turingův stroj. Turing popsal takovou konstrukci úplně podrobně ve své práci z roku 1936:

„Je možné vymyslet jediný stroj, který lze použít k výpočtu jakékoli vypočítatelné sekvence. Pokud tento stroj U je dodáván s páskou, na jejímž začátku je napsán S.D ["standardní popis" tabulky akcí] nějakého výpočetního stroje M, pak U vypočítá stejnou sekvenci jako M."^[3]

Počítač s uloženým programem

Davise přesvědčivě argumentuje, že Turingova koncepce toho, co je nyní známé jako „počítač s uloženým programem“, umístění „akční tabulky“ - instrukce pro stroj - do stejné „paměti“ jako vstupní data, silně ovlivnila John von Neumann pojetí prvního amerického diskrétního symbolu (na rozdíl od analogového) počítače - the EDVAC. Davis cituje Čas časopis v tomto smyslu, že „každý, kdo klepne na klávesnici ... pracuje na inkarnaci Turingova stroje“, a že „John von Neumann [stavěl] na díle Alana Turinga“ (Davis 2000: 193 cituje Čas časopis ze dne 29. března 1999).

Davis dělá případ jako Turing Automatický výpočetní engine (ACE) počítač „očekával“ představy o mikroprogramování (mikrokód ) a RISC procesory (Davis 2000: 188). Knuth uvádí práci Turinga na počítači ACE jako návrh „hardwaru pro usnadnění propojení podprogramů“ (Knuth 1973: 225); Davis také odkazuje na tuto práci jako na Turingovo použití hardwarového „zásobníku“ (Davis 2000: 237 poznámka pod čarou 18).

Když Turingův stroj podporoval stavbu počítače UTM podporovala rozvoj rodícího se dítěte počítačové vědy. Brzy, ne-li úplně první, byl pro EDVAC navržen „mladý programátor hot-shot“ (Davis 2000: 192). Von Neumannov „první seriózní program ... [byl] jednoduše efektivně třídit data“ (Davis 2000: 184). Knuth podotýká, že návratnost podprogramu vloženého do samotného programu spíše než do zvláštních registrů lze přičíst von Neumannovi a Goldstineovi.^[4] Knuth to dále uvádí

„Za první interpretační rutinu lze považovat„ univerzální Turingův stroj “... Interpretační rutiny v konvenčním smyslu zmínil John Mauchly na svých přednáškách na Mooreově škole v roce 1946 ... Turing se podílel také na tomto vývoji; interpretační systémy pro počítač Pilot ACE byly napsány pod jeho vedením “(Knuth 1973: 226).

Davis stručně zmiňuje operační systémy a překladače jako výsledky pojmu program-as-data (Davis 2000: 185).

Někteří však mohou s tímto hodnocením vyvolat problémy. V té době (polovina čtyřicátých let do poloviny padesátých let) byl relativně malý kádr výzkumníků úzce zapojen do architektury nových „digitálních počítačů“. Hao Wang (1954), mladý výzkumník v této době, učinil následující pozorování:

Turingova teorie vypočítatelných funkcí antedatovala, ale příliš neovlivnila rozsáhlou skutečnou konstrukci digitálních počítačů. Tyto dva aspekty teorie a praxe byly vyvinuty téměř zcela nezávisle na sobě. Hlavním důvodem je nepochybně to, že logiky zajímají otázky radikálně odlišné od těch, kterých se primárně týkají aplikovaní matematici a elektrotechnici. Nelze však zapomenout na jednoho člověka, který je docela podivný, že tytéž pojmy jsou v obou vývojových obdobích vyjádřeny velmi odlišnými pojmy. “(Wang 1954, 1957: 63)

Wang doufal, že jeho práce „spojí dva přístupy“. Minsky to skutečně potvrzuje: „že první formulace teorie Turingova stroje v počítačových modelech se objevuje ve Wangovi (1957)“ (Minsky 1967: 200). Minsky pokračuje v demonstraci Turingova ekvivalence a pultový stroj.

Pokud jde o redukci počítačů na jednoduché Turingovy ekvivalentní modely (a naopak), je diskutabilní Minskyho označení Wanga jako „první formulace“. Zatímco jak Minskyho dokument z roku 1961, tak Wangův dokument z roku 1957 citují Shepherdson a Sturgis (1963), citují a podrobně shrnují práci evropských matematiků Kaphensta (1959), Ershova (1959) a Pétera (1958). Jména matematiků Hermes (1954, 1955, 1961) a Kaphenst (1959) se objevují v bibliografiích jak Sheperdson-Sturgis (1963), tak Elgot-Robinson (1961). Další dvě významná jména jsou kanadští vědci Melzak (1961) a Lambek (1961). Pro mnohem více viz Turingovy ekvivalenty; reference najdete na zaregistrovat stroj.

Matematická teorie

S tímto kódováním akčních tabulek jako řetězců je v zásadě možné, aby stroje Turing odpovídaly na otázky týkající se chování jiných strojů Turing. Většina z těchto otázek však je nerozhodnutelný, což znamená, že dotyčnou funkci nelze vypočítat mechanicky. Například problém s určením, zda se libovolný Turingův stroj zastaví na konkrétním vstupu nebo na všech vstupech, známém jako Zastavení problému, se ukázalo, že je obecně nerozhodnutelný v Turingově původním papíru. Riceova věta ukazuje, že jakákoli nepodstatná otázka týkající se výstupu Turingova stroje je nerozhodná.

Univerzální Turingův stroj dokáže vypočítat jakýkoli rekurzivní funkce, rozhodnout se rekurzivní jazyk a přijmout jakékoli rekurzivně vyčíslitelný jazyk. Podle Církev – Turingova teze, problémy řešitelné univerzálním Turingovým strojem jsou přesně ty problémy řešitelné pomocí algoritmus nebo efektivní metoda výpočtu, pro jakoukoli rozumnou definici těchto pojmů. Z těchto důvodů slouží univerzální Turingův stroj jako standard, proti kterému lze porovnávat výpočetní systémy, a systém, který dokáže simulovat univerzální Turingův stroj, se nazývá Turing dokončen.

Abstraktní verzí univerzálního Turingova stroje je univerzální funkce, vypočítatelná funkce, kterou lze použít k výpočtu jakékoli jiné vypočítatelné funkce. The Věta UTM dokazuje existenci takové funkce.

Účinnost

Bez ztráty obecnosti lze předpokládat, že vstup Turingova stroje je v abecedě {0, 1}; jakákoli jiná konečná abeceda může být zakódována přes {0, 1}. Chování Turingova stroje M je dána jeho přechodovou funkcí. Tuto funkci lze také snadno zakódovat jako řetězec přes abecedu {0, 1}. Velikost abecedy M, počet pásek, které má, a velikost stavového prostoru lze odvodit z tabulky přechodové funkce. Rozlišující stavy a symboly lze identifikovat podle jejich polohy, např. první dva státy mohou být podle konvence stavy start a stop. V důsledku toho může být každý Turingův stroj zakódován jako řetězec přes abecedu {0, 1}. Dále svoláváme, že každé neplatné kódování se mapuje na triviální Turingův stroj, který se okamžitě zastaví, a že každý Turingův stroj může mít nekonečný počet kódování tak, že kódování na konci vyplní libovolným počtem (řekněme) 1, stejně jako komentáře pracovat v programovacím jazyce. Nemělo by být žádným překvapením, že tohoto kódování můžeme dosáhnout vzhledem k existenci a Gödelovo číslo a výpočetní ekvivalence mezi Turingovými stroji a μ-rekurzivní funkce. Podobně se naše konstrukce přidruží ke každému binárnímu řetězci α, Turingův stroj M_α.

Počínaje výše uvedeným kódováním, v roce 1966 F. C. Hennie a R. E. Stearns ukázal, že daný Turingův stroj M_α které se zastaví na vstupu X v rámci N kroky, pak existuje vícepásmový univerzální Turingův stroj, který se zastaví na vstupech α, X (uvedené na různých páskách) v CN log N, kde C je strojově specifická konstanta, která nezávisí na délce vstupu X, ale záleží na M 's velikost abecedy, počet pásek a počet stavů. Účinně se jedná o ${ displaystyle { mathcal {O}} vlevo (N log {N} vpravo)}$ simulace pomocí Donald Knuth je Velká O notace.^[5] Odpovídajícím výsledkem pro prostorovou složitost spíše než časovou složitost je, že můžeme simulovat způsobem, který maximálně využívá CN buňky v jakékoli fázi výpočtu, an ${ displaystyle { mathcal {O}} (N)}$ simulace.^[6]

Nejmenší stroje

Když Alan Turing přišel s myšlenkou univerzálního stroje, měl na mysli nejjednodušší výpočetní model dostatečně výkonný na to, aby vypočítal všechny možné funkce, které lze vypočítat. Claude Shannon nejprve výslovně položil otázku nalezení nejmenšího možného univerzálního Turingova stroje v roce 1956. Ukázal, že dva symboly jsou dostačující, pokud je použit dostatek států (nebo naopak), a že je vždy možné vyměnit stavy za symboly. Ukázal také, že žádný univerzální Turingův stroj jednoho státu nemůže existovat.

Marvin Minsky objevil v roce 1962 7-stavový univerzální Turingův stroj se 4 symboly 2-tag systémy. Další malé univerzální Turingovy stroje od té doby našel Yurii Rogozhin a další rozšířením tohoto přístupu k simulaci systému značek. Pokud označíme (m, n) třída UTM s m státy a n symboly byly nalezeny následující n-tice: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9) a (2, 18) .^[7][8][9] Rogozhinův (4, 6) stroj používá pouze 22 instrukcí a není znám žádný standardní UTM menší popisné složitosti.

Zobecnění standardního modelu stroje Turing však připouští ještě menší UTM. Jedním z takových zobecnění je umožnit nekonečně opakované slovo na jedné nebo obou stranách vstupu Turingova stroje, čímž se rozšíří definice univerzality a je známá jako „poloslabá“ nebo „slabá“ univerzálnost. Malé slabě univerzální Turingovy stroje, které simulují Pravidlo 110 buněčný automat byl dán pro páry (6, 2), (3, 3) a (2, 4) stavových symbolů.^[10] Důkaz univerzálnosti pro Wolframův 2-stavový 3-symbolový Turingův stroj dále rozšiřuje představu o slabé univerzálnosti tím, že umožňuje určité neperiodické počáteční konfigurace. Mezi další varianty standardního modelu stroje Turing, které poskytují malé UTM, patří stroje s více páskami nebo pásky s více dimenzemi a stroje spojené s konečný automat.

Stroje bez vnitřních stavů

Pokud na Turingově stroji povolíte více hlav, můžete mít Turingův stroj bez vůbec žádných vnitřních stavů. „Stavy“ jsou zakódovány jako součást pásky. Zvažte například pásku se 6 barvami: 0, 1, 2, 0A, 1A, 2A. Vezměme si pásku, jako je 0,0,1,2,2A, 0,2,1, kde je nad trojitým (2,2A, 0) umístěn tříhlavý Turingův stroj. Pravidla poté převádějí jakoukoli trojku na jinou trojku a přesouvají 3 hlavy doleva nebo doprava. Pravidla by například mohla převést (2,2A, 0) na (2,1,0) a posunout hlavu doleva. V tomto příkladu tedy stroj funguje jako tříbarevný Turingův stroj s vnitřními stavy A a B (představovaný bez písmene). Případ dvouhlavého Turingova stroje je velmi podobný. Dvouhlavý Turingův stroj tak může být univerzální se 6 barvami. Není známo, jaký je nejmenší počet barev potřebných pro vícehlavý Turingův stroj, nebo zda je možný dvoubarevný univerzální Turingův stroj s více hlavami. To také znamená přepsat pravidla jsou Turing kompletní, protože trojitá pravidla jsou ekvivalentní pravidlům přepisování. Rozšíření pásky na dva rozměry s hlavou vzorkující písmeno a jeho 8 sousedů, jsou zapotřebí pouze 2 barvy, například barvu lze zakódovat do svislého trojitého vzoru, například 110.

Příklad kódování na univerzálním stroji

Pro ty, kteří by přijali výzvu navrhnout UTM přesně tak, jak specifikoval Turing, viz článek Daviese v Copelandu (2004: 103ff). Davies opravuje chyby v originálu a ukazuje, jak by vypadal ukázkový běh. Tvrdí, že úspěšně spustil (poněkud zjednodušenou) simulaci.

Následující příklad je převzat z Turinga (1936). Další informace o tomto příkladu naleznete na stránce Příklady Turingova stroje.

Turing použil sedm symbolů {A, C, D, R, L, N,; } pro zakódování každé 5-tice; jak je popsáno v článku Turingův stroj, jeho 5 n-tic je pouze typů N1, N2 a N3. Počet každé „m-konfigurace“ (instrukce, stav) je reprezentován „D“ následovaným unárním řetězcem A, např. "q3" = DAAA. Podobným způsobem kóduje symboly prázdné jako „D“, symbol „0“ jako „DC“, symbol „1“ jako DCC atd. Symboly „R“, „L“ a „N“ zůstávají jako je.

Po kódování je každá pětina n-tic „sestavena“ do řetězce v pořadí, jak je znázorněno v následující tabulce:

Nakonec jsou kódy všech čtyř n-tic spojeny dohromady do kódu zahájeného znakem „;“ a oddělené znakem „;“ tj.:

;DADDCRDAA;DAADDRDAAA;DAAADDCCRDAAAA;DAAAADDRDA

Tento kód umístil na alternativní čtverce - „F-čtverce“ - ponechávající „E-čtverce“ (ty, které mohou vymazat) prázdné. Konečné sestavení kódu na pásku pro U-stroj se skládá z umístění dvou speciálních symbolů („e“) jeden po druhém, poté se kód oddělil na alternativní čtverce a nakonec symbol dvojtečka “::„(pro lepší přehlednost jsou zde zobrazeny mezery s„. “):

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.::......

Za dekódování symbolů je zodpovědná tabulka akcí U-stroje (tabulka přechodu stavu). Turingova akční tabulka sleduje své místo pomocí značek „u“, „v“, „x“, „y“, „z“ tak, že je umístí do „E-čtverců“ napravo od „označeného symbolu“ - například , k označení aktuální instrukce z je umístěn napravo od „;“ X udržuje místo s ohledem na aktuální DAA „m-konfigurace“. Akční tabulka U-stroje bude tyto symboly kolem dokola (mazat je a umisťovat na různá místa), jak výpočet postupuje:

ee.; .D.A.D.D.C.R.D.A.A. ; zD.A.A.XD.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.::......

Turingův akční stůl pro jeho U-stroj je velmi zapojený.

Řada dalších komentátorů (zejména Penrose 1989 ) poskytují příklady způsobů kódování pokynů pro univerzální stroj. Stejně jako Penrose používá většina komentátorů pouze binární symboly, tj. Pouze symboly {0, 1} nebo {blank, mark | }. Penrose jde dále a vypíše celý svůj kód U-stroje (Penrose 1989: 71–73). Tvrdí, že se skutečně jedná o kód U-stroje, což je enormní počet, který pokrývá téměř 2 celé stránky 1 a 0. Pro čtenáře, kteří mají zájem o jednodušší kódování pro Post-Turingův stroj diskuse Davise in Steen (Steen 1980: 251ff) může být užitečná.

Asperti a Ricciotti popsali vícepásmový UTM definovaný složením elementárních strojů s velmi jednoduchou sémantikou, místo aby výslovně uváděli celou akční tabulku. Tento přístup byl dostatečně modulární, aby jim umožnil formálně prokázat správnost stroje v Matita důkaz asistent.

Programování Turingových strojů

Různé jazyky vyšší úrovně jsou navrženy pro kompilaci do Turingova stroje. Mezi příklady patří Lakonický a Turingův strojový deskriptor.^[11][12]

Viz také

• Střídavý Turingův stroj
• Von Neumann univerzální konstruktér - pokus postavit samoreplikující se Turingův stroj
• Kleeneův T predikát - podobný koncept pro µ-rekurzivní funkce
• Turingova úplnost

Reference

Obecné odkazy

• Arora, Sanjeev; Barak, Boaz (2009). Teorie složitosti: moderní přístup. Cambridge University Press. ISBN  978-0-521-42426-4. část 1.4, „Stroje jako struny a univerzální Turingův stroj“ a 1.7, „Důkaz věty 1.9“

Originální papír

• Turing, A. M. (1936). „Na vypočítatelných číslech s aplikací na Entscheidungsproblem“ (PDF).

Seminární práce

• Hennie, F. C .; Stearns, R. E. (1966). „Simulace dvou pásků vícevrstvých Turingových strojů“. Deník ACM. 13 (4): 533. doi:10.1145/321356.321362. S2CID  2347143.

Implementace

• Kamvysselis (Kellis), Manolis (1999). „Schéma implementace univerzálního Turingova stroje“. Vlastní vydání.

Formální ověření

• Asperti, Andrea; Ricciotti, Wilmer (2015). „Formalizace vícepásových Turingových strojů“ (PDF). Teoretická informatika. Elsevier. 603: 23–42. doi:10.1016 / j.tcs.2015.07.013. ISSN  0304-3975.

Další reference

• Copelande, Jacku, vyd. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of EnigmaOxford Velká Británie: Oxford University Press, ISBN  0-19-825079-7
• Davis, Martin (1980), „Co je to výpočet?“, In Steen, Lynn Arthur (vyd.), Matematika dnes: dvanáct neformálních esejí, New York: Vintage Books (Random House), ISBN  978-0-394-74503-9.
• Davis, Martin (2000), Engines of Logic: Mathematicians and the origin of the Computer (1. vyd.), New York NY: W. W. Norton & Company, ISBN  0-393-32229-7, (str.)
• Goldstine, Herman H .; von Neumann, John. Plánování a kódování problémů pro elektronický výpočetní přístroj. Institut pro pokročilé studium (Rep. 1947 ed.). Princeton.
  Bell, C. Gordon; Newell, Allen (1971). Počítačové struktury: čtení a příklady (Přetištěno ed.). New York: McGraw-Hill Book Company. str.92–119. ISBN  0-07-004357-4.
• Herken, Rolf (1995), Univerzální Turingův stroj - průzkum za půl stoletíSpringer Verlag, ISBN  3-211-82637-8
• Knuth, Donald E. (1968), The Art of Computer Programming Second Edition, Volume 1 / Fundamental Algorithms (2. 1973) | formát = vyžaduje | url = (Pomoc) (První vydání), Addison-Wesley Publishing Company První ze série tří textů Knutha.
• Kudlek, Manfred; Rogozhin, Yurii (2002), „Univerzální Turingův stroj se 3 stavy a 9 symboly“, Werner Kuich; Grzegorz Rozenberg; Arto Salomaa (eds.), Vývoj v teorii jazyků: 5. mezinárodní konference, DLT 2001 Vídeň, Rakousko, 16. – 21. Července 2001, revidované příspěvky, Přednášky v informatice, 2295, Springer, str. 311–318, doi:10.1007 / 3-540-46011-x_27, ISBN  978-3-540-43453-5
• Minsky, Marvin (1962), "Velikost a struktura univerzálních Turingových strojů využívajících systémy značek, teorie rekurzivních funkcí", Proc. Symp. Čistá matematika, Providence RI: American Mathematical Society, 5: 229–238, doi:10.1090 / pspum / 005/0142452
• Neary, Turlough; Woods, Damien (2009), „Čtyři malé univerzální Turingovy stroje“ (PDF), Fundamenta Informaticae, 91 (1): 123–144, doi:10.3233 / FI-2009-0036
• Neary, Turlough; Woods, Damien (2009b), „Malé slabě univerzální Turingovy stroje“, 17. mezinárodní symposium o základech teorie výpočtu, Přednášky v informatice, 5699, Springer, str. 262–273
• Penrose, Rogere (1989), Císařova nová mysl Oxford UK: Oxford University Press, ISBN  0-19-851973-7, (hc.), (str.)
• Rogozhin, Yurii (1996), „Malé univerzální Turingovy stroje“, Teoretická informatika, 168 (2): 215–240, doi:10.1016 / S0304-3975 (96) 00077-1
• Shannon, Claude (1956), „Univerzální Turingův stroj se dvěma vnitřními stavy“, Studie automatů„Princeton, NJ: Princeton University Press, s. 157–165
• Turing, A.M. (1936), „Na vypočítatelných číslech, s aplikací na problém Entscheidungs“, Proceedings of the London Mathematical Society, 2, 42, str. 230–65, doi:10.1112 / plms / s2-42.1.230
• Turing, A.M. (1938), „O vypočítatelných číslech, s aplikací na problém Entscheidungs: Oprava“, Proceedings of the London Mathematical Society, 2 (publikováno 1937), 43 (6), s. 544–6, doi:10,1112 / plms / s2-43,6,544)
  Davis ed, Martin (1965). Nerozhodnutelný (Dotisk ed.). Hewlett, NY: Raven Press. str. 115–154. s opravami Turingova UTM Emil Post srov poznámka pod čarou 11 str: 299CS1 maint: další text: seznam autorů (odkaz)

externí odkazy

Smith, Alvy Ray. „Univerzální Turingův stroj na vizitky“ (PDF). Citováno 2. ledna 2020.