Post -Turingův stroj - Post–Turing machine
Po Turingův stroj je „program, formulace“ pro typ Turing stroj , který obsahuje variantu Emil Post ‚s Turingovsky ekvivalentním modelu z výpočtu . Postův model a Turingův model, ačkoli jeden druhému velmi podobný, byly vyvinuty nezávisle. Turingův papír byl přijat k publikaci v květnu 1936, následovaný Postem v říjnu.) Post-Turingův stroj používá binární abecedu , nekonečnou posloupnost binárních úložných míst a primitivní programovací jazyk s instrukcemi pro obousměrný pohyb mezi úložišti umístění a změny jejich obsahu jeden po druhém. Názvy „Post – Turingův program“ a „Post – Turingův stroj“ používal Martin Davis v letech 1973–1974 (Davis 1973, s. 69 a dále). Později v roce 1980 Davis používal název „Turing – Post program“ (Davis, v Steen s. 241).
1936: Post model
V jeho 1936 papíru, „Finite Kombinatorické Procesy-formulace 1“, Emil Post popsal model, který on se domníval, je „ logicky ekvivalentní k rekurzívnosti “.
Postův model výpočtu se liší od modelu Turingova stroje v další „atomizaci“ úkonů, které by lidský „počítač“ prováděl během výpočtu.
Postův model využívá „ prostor symbolů “ skládající se z „obousměrné nekonečné posloupnosti mezer nebo rámečků“, přičemž každé pole může být v jedné ze dvou možných podmínek, konkrétně „označené“ (jako jediným svislým tahem) a „neoznačené“ “(prázdný). Zpočátku konečně -Mnoho z polí jsou označeny, zbytek je sám před brankářem. „Pracovník“ se pak má pohybovat mezi schránkami, být uvnitř a pracovat pouze v jedné krabici najednou, podle pevné konečné „sady směrů“ ( pokynů ), které jsou očíslovány v pořadí (1,2,3, ..., n ). Počínaje rámečkem „vyčleněným jako výchozí bod“ má pracovník postupovat podle sady pokynů jeden po druhém, počínaje instrukcí 1.
Pracovník může provádět pět různých primitivních operací:
- (a) Označení pole, ve kterém je, pokud je prázdné
- (b) Vymazání značky v poli, ve kterém je, pokud je označena
- (c) Přesun do pole vpravo
- (d) Přesun do pole nalevo
- (e) Určení, zda je pole, ve kterém je, je nebo není označeno.
Potom i -tý „směr“ (pokyn) daný pracovníkovi má mít jednu z následujících forem:
- Proveďte operaci O i [ O i = (a), (b), (c) nebo (d)] a poté postupujte podle směru j i
- Proveďte operaci (e) a podle odpovědi ano nebo ne odpovídajícím způsobem sledujte směr j i ′ nebo j i ′ ′
- Přestaň .
(Výše uvedený odsazený text a kurzíva jsou stejné jako v originále.) Post poznamenává, že tato formulace je „v počátečních fázích“ vývoje, a zmiňuje několik možností „větší flexibility“ v konečné „konečné podobě“, včetně
- nahrazení nekonečna rámečků prostorem konečných rozšiřitelných symbolů, „rozšířením primitivních operací, které umožní nezbytné rozšíření daného prostoru konečných symbolů, jak proces pokračuje“,
- pomocí abecedy více než dvou symbolů „s více než jedním způsobem označení pole“,
- zavedení konečně mnoha „fyzických předmětů, které mají sloužit jako ukazatele, které pracovník může identifikovat a přesouvat z boxu do boxu“.
1947: Postova formální redukce Turingových 5-tic na 4-tice
Jak bylo stručně uvedeno v článku Turingův stroj , Post ve svém příspěvku z roku 1947 ( Rekurzivní neřešitelnost problému z Thue ) atomizoval Turingovy 5-tice na 4-tice:
- "Naše čtyřčata jsou ve vývoji Turingů pětičlenky. To znamená, že tam, kde naše standardní instrukce objednává buď tisk (přetisk) nebo pohyb, doleva nebo doprava, standardní instrukce Turinga vždy objednává tisk a pohyb, pravý, levý nebo žádný" ( poznámka pod čarou 12, Nerozhodnutelný , s. 300)
Stejně jako Turing definoval vymazání jako tisk symbolu „S0“. A tak jeho model připustil čtyřčata pouze tří typů (srov. Nerozhodnutelný , s. 294):
- q i S j L q l ,
- q i S j R q l ,
- q i S j S k q l
V této době ještě zachovával Turingovu konvenci stavového stroje-neformalizoval pojem předpokládaného sekvenčního provádění kroků, dokud konkrétní test symbolu „nerozvětvil“ provedení jinde.
1954, 1957: Wangův model
Ještě další redukci-na pouhé čtyři instrukce-zde představeného modelu Wang viz Wang B-machine .
Wang (1957, ale ACM představen v roce 1954) je často citován (srov. Minsky (1967), s. 200) jako zdroj „programové formulace“ Turingových strojů s binární páskou pomocí očíslovaných pokynů ze sady
- napiš 0
- napiš 1
- pohyb doleva
- pohyb vpravo
- pokud skenujete 0, přejděte na instrukci i
- pokud skenujete 1, přejděte na instrukci j
Jakýkoli Turingův stroj s binární páskou lze snadno převést na ekvivalentní „program Wang“ pomocí výše uvedených pokynů.
1974: první Davisův model
Martin Davis byl vysokoškolák Emil Post. Spolu se Stephenem Kleene dokončil doktorát pod Alonzo Church (Davis (2000) 1. a 2. poznámka pod čarou s. 188).
Následující model představil v sérii přednášek Courant Institute na NYU v letech 1973–1974. Toto je model, na který Davis formálně použil název „Post -Turingův stroj“ se svým „Post -Turingovým jazykem“. Předpokládá se, že pokyny jsou prováděny postupně (Davis 1974, s. 71):
1978: druhý Davisův model
Následující model se jeví jako esej Co je to výpočet? na stránkách Steen 241–267. Davis z nějakého důvodu přejmenoval svůj model na „stroj Turing – Post“ (s jedním zpětným posuvem na straně 256.)
V následujícím modelu Davis přiřadí čísla „1“ příspěvku „značka/lomítko“ a „0“ prázdnému čtverci. Cituji Davise: „Nyní jsme připraveni představit programovací jazyk Turing – Post. V tomto jazyce existuje sedm druhů pokynů:
- „TISK 1
- „TISK 0
- "JDI DOPRAVA
- „Jděte DOLEVA
- „Přejděte na krok i IF 1 se naskenuje
- „PŘEJDĚTE NA KROK i, POKUD JE SKENOVÁNO 0
- "STOP
„Program Turing – Post je pak seznam instrukcí, z nichž každý je jedním z těchto sedmi druhů. Ve skutečném programu musí být písmeno i v kroku buď pátého nebo šestého druhu nahrazeno konečné (kladné celé) číslo. “ (Davis ve Steenu, s. 247).
1994 (2. vydání): Davis – Sigal – Weyuker's Post – Turingův model programu
"Ačkoli formulace Turinga, kterou jsme představili, je v duchu bližší té, kterou původně poskytl Emil Post, díky Turingově analýze výpočtu se tato formulace zdála tak vhodná. Tento jazyk hrál zásadní roli v teoretické informatice." (Davis a kol. (1994) s. 129)
Tento model umožňuje tisk více symbolů. Model umožňuje B (prázdné) místo S 0 . Páska je nekonečná v obou směrech. Pohybuje se buď hlava, nebo páska, ale jejich definice DOPRAVA a DOPRAVA vždy v obou případech určují stejný výsledek (Turing použil stejnou konvenci).
- TISK σ; Nahraný symbol nahraďte σ
- IF σ GOTO L; IF scanned symbol je σ THEN goto "the first" instruction labeled L
- VPRAVO; Skenovat čtverec přímo od aktuálně skenovaného čtverce
- VLEVO; Skenovat čtverec bezprostředně vlevo od aktuálně skenovaného čtverce
Tento model redukuje na binární verze {0, 1} uvedené výše, jak je znázorněno zde:
- TISK 0 = VYMAZAT; Nahraný symbol nahraďte 0 = B = BLANK
- TISK 1; Nahraný symbol nahraďte 1
- IF 0 GOTO L; IF scanned symbol is 0 THEN goto "the first" instruction labeled L
- IF 1 GOTO L; IF scanned symbol je 1 THEN goto "the first" instruction labeled L
- VPRAVO; Skenovat čtverec přímo od aktuálně skenovaného čtverce
- VLEVO; Skenovat čtverec bezprostředně vlevo od aktuálně skenovaného čtverce
Příklady stroje Post -Turing
Atomizace Turingových pětinásobků na posloupnost instrukcí po Turingovi
Následující metodu „redukce“ (rozklad, atomizace)-od 2-symbolových Turingových 5-tic k sekvenci 2-symbolových Post-Turingových instrukcí-lze nalézt v Minsky (1961). Uvádí, že tato redukce na „ program ... sled instrukcí “ se nese v duchu B-stroje Hao Wanga (kurzíva v originále, srov. Minsky (1961) s. 439).
(Minskyho redukce na to, co nazývá „sub-rutina“, má za následek 5 namísto 7 instrukcí po Turingovi. Ne atomizoval Wi0: „Napište symbol Si0; přejděte do nového stavu Mi0“ a Wi1: „Napište symbol Si1; přejít do nového stavu Mi1 ". Následující metoda dále atomizuje Wi0 a Wi1; ve všech ostatních ohledech jsou metody identické.)
Toto snížení Turingových 5-tic na instrukce Post-Turing nemusí vést k „efektivnímu“ programu Post-Turing, ale bude věrné původnímu Turingovu programu.
V následujícím příkladu se každý Turingův 5-násobek 2-stavového zaneprázdněného bobra převede na
- počáteční podmíněný „skok“ (goto, větev), za kterým následuje
- 2 pokyny k akci pásku pro případ „0“-Tisk nebo Vymazání nebo Žádný, následovaný Vlevo nebo Vpravo nebo Žádný, následovaný
- bezpodmínečný „skok“ pro případ „0“ na jeho další instrukci
- 2 pokyny k akci pásku pro případ „1“-Tisk nebo Vymazání nebo Žádný, následovaný Vlevo nebo Vpravo nebo Žádný, následovaný
- bezpodmínečný „skok“ pro případ „1“ na jeho další pokyn
celkem 1 + 2 + 1 + 2 + 1 = 7 instrukcí za Turingův stav.
Například Turingův stav „A“ 2-stavového zaneprázdněného bobra, zapsaný jako dva řádky po 5 n-ticích, je:
Počáteční konfigurace m (Turingův stav) | Symbol pásky | Operace tisku | Pohyb pásky | Konečná m-konfigurace (Turingův stav) |
---|---|---|---|---|
A | 0 | P | R. | B |
A | 1 | P | L | B |
Tabulka představuje pouze jednu Turingovu „instrukci“, ale vidíme, že se skládá ze dvou řádků po 5 řazených kolekcích, jeden pro případ „symbol pásky pod hlavou = 1“, druhý pro případ „symbol pásky pod hlavou = 0 “. Turing zjistil ( nerozhodnutelné , str. 119), že dva levé sloupce-„m-konfigurace“ a „symbol“-představují aktuální „konfiguraci“ stroje-jeho stav zahrnující v daném okamžiku pásku i stůl-a poslední tři sloupce jsou jeho následné „chování“. Protože stroj nemůže být ve dvou "stavech" najednou, musí se stroj "rozvětvit" buď do jedné konfigurace, nebo do druhé:
Počáteční m-konfigurace a symbol S | Operace tisku | Pohyb pásky | Konečná m-konfigurace |
---|---|---|---|
S = 0 → | P → | R → | B |
→ A < | |||
S = 1 → | P → | L → | B |
Po „konfigurační větvi“ (J1 xxx) nebo (J0 xxx) stroj následuje jedno ze dvou následujících „chování“. Uvedeme tato dvě chování na jeden řádek a očíslujeme (nebo označíme) postupně (jednoznačně). Pod každý skok (větev, přejděte na) umístíme jeho „číslo“ (adresa, umístění):
Podle konvencí stroje Post -Turing se každá z instrukcí Print, Erase, Left a Right skládá ze dvou akcí:
- Akce pásku: {P, E, L, R}, potom
- Akce tabulky: přejděte na další instrukci v pořadí
A podle konvencí stroje Post – Turing se podmíněné „skoky“ J0xxx, J1xxx skládají ze dvou akcí:
- Akce pásku: podívejte se na symbol na pásku pod hlavou
- Akce tabulky: Pokud je symbol 0 (1) a J0 (J1), přejděte na xxx else přejděte na další instrukci v pořadí
A podle konvencí stroje Post-Turing se bezpodmínečný „skok“ Jxxx skládá z jediné akce, nebo chceme-li regulovat sekvenci 2 akcí:
- Akce pásku: podívejte se na symbol na pásku pod hlavou
- Akce tabulky: Pokud je symbol 0, přejděte na xxx else, pokud je symbol 1, přejděte na xxx.
Které a kolik skoků je zapotřebí? Bezpodmínečný skok J xxx je jednoduše J0 následovaný bezprostředně J1 (nebo naopak). Wang (1957) také ukazuje, že je vyžadován pouze jeden podmíněný skok, tj. Buď J0 xxx nebo J1 xxx. S tímto omezením je však pro stroj obtížné psát pokyny. Často se používají pouze dva, tzn
- { J0 xxx, J1 xxx}
- { J1 xxx, J xxx}
- { J0 xxx, J xxx},
ale použití všech tří { J0 xxx, J1 xxx, J xxx} eliminuje další pokyny. V příkladu 2-stavového Busy Beaver používáme pouze { J1 xxx, J xxx}.
2stavový zaneprázdněný bobr
Posláním zaneprázdněného bobra je vytisknout co nejvíce kusů, než se zastaví. Instrukce „Tisk“ zapíše 1, instrukce „Vymazat“ (v tomto příkladu není použita) zapíše 0 (tj. Je stejná jako P0). Páska se pohybuje „doleva“ nebo „doprava“ (tj. „Hlava“ je nehybná).
Stavová tabulka pro dvoustavového zaneprázdněného bobra Turingova stroje :
Symbol pásky | Aktuální stav A. | Současný stav B | ||||
---|---|---|---|---|---|---|
Napište symbol | Přesuňte pásku | Další stav | Napište symbol | Přesuňte pásku | Další stav | |
0 | 1 | R. | B | 1 | L | A |
1 | 1 | L | B | 1 | N. | H |
Pokyny pro verzi Post-Turing 2-stavového zaneprázdněného bobra: Všimněte si, že všechny pokyny jsou na stejném řádku a v pořadí. Toto je významný odklon od verze „Turing“ a je ve stejném formátu jako to, co se nazývá „počítačový program“:
Instrukce # | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Návod | J1 | P | R. | J. | P | L | J. | J1 | P | L | J. | P | N. | J. | H |
Skočit do # | 5 | 8 | 8 | 12 | 1 | 15 | |||||||||
Štítek Turingova stavu | A | B | H |
Alternativně můžeme tabulku zapsat jako řetězec. Použití „oddělovačů parametrů“ „:“ a oddělovačů instrukcí „,“ je zcela naší volbou a v modelu se neobjevuje. Neexistují žádné konvence (viz Booth (1967) s. 374 a Boolos a Jeffrey (1974, 1999) s. 23), kde najdete několik užitečných nápadů, jak kombinovat konvence stavových diagramů s pokyny - tj. Pomocí šipek označovat cíl skoků). V níže uvedeném příkladu jsou pokyny sekvenční počínaje „1“ a parametry/„operandy“ jsou považovány za součást jejich pokynů/„operačních kódů“:
- J1: 5, P, R, J: 8, P, L, J: 8, J1: 12, P, L, J1: 1, P, N, J: 15, H
Poznámky
Reference
- Stephen C. Kleene , Introduction to Meta-Mathematics, North-Holland Publishing Company , New York, 10. vydání 1991, první vydání 1952. Kapitola XIII je vynikajícím popisem Turingových strojů; Kleene ve svém popisu používá model podobný Postu a připouští, že Turingův model by mohl být dále atomizován, viz poznámka pod čarou 1.
- Martin Davis , redaktor: Nerozhodnutelný, základní dokumenty o nerozhodnutelných návrzích, neřešitelné problémy a výpočetní funkce , Raven Press, New York, 1965. Příspěvky obsahují příspěvky od Gödel , Church , Rosser , Kleene a Post.
- Martin Davis , „What is a computation“, in Mathematics Today , Lynn Arthur Steen, Vintage Books (Random House), 1980. Nádherný malý papír, možná nejlepší, jaký kdy byl o Turingových strojích napsán. Davis redukuje Turingův stroj na mnohem jednodušší model na základě Postova modelu výpočtu. Zahrnuje malou biografii Emila Posta.
- Martin Davis , Vypočitatelnost: s poznámkami Barryho Jacobse , Courant Institute of Mathematical Sciences, New York University, 1974.
- Martin Davis , Ron Sigal , Elaine J. Weyuker , (1994) Vypočitatelnost , složitost a jazyky: Základy teoretické informatiky-2. vydání , Academic Press: Harcourt, Brace & Company, San Diego, 1994 ISBN 0-12-206382- 1 (první vydání, 1983).
- Fred Hennie , Introduction to Computability , Addison – Wesley, 1977.
- Marvin Minsky , (1961), Recursive Unsolvability of Post's problem of 'Tag' and other Topics in Theory of Turing Machines , Annals of Mathematics, Vol. 74, č. 3, listopad 1961.
- Roger Penrose , Císařova nová mysl: Pokud jde o počítače, mysli a fyzikální zákony , Oxford University Press, Oxford England, 1990 (s opravami). Srov. Kapitola 2, „Algoritmy a Turingovy stroje“. Překomplikovaná prezentace (lepší model viz Davisův papír), ale důkladná prezentace Turingových strojů a problému se zastavením a Churchův lambda kalkul .
- Hao Wang (1957): „Varianta Turingovy teorie výpočetních strojů“, Journal of the Association for Computing Machinery (JACM) 4, 63–92.