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:

  1. Proveďte operaci O i [ O i = (a), (b), (c) nebo (d)] a poté postupujte podle směru j i
  2. 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 ′ ′
  3. 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ě

  1. 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“,
  2. pomocí abecedy více než dvou symbolů „s více než jedním způsobem označení pole“,
  3. 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

  1. počáteční podmíněný „skok“ (goto, větev), za kterým následuje
  2. 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ý
  3. bezpodmínečný „skok“ pro případ „0“ na jeho další instrukci
  4. 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ý
  5. 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í):

Počáteční m-konfigurace a symbol S Operace tisku Pohyb pásky Konečný případ m-konfigurace S = 0 Operace tisku Pohyb pásky Konečný případ m-konfigurace S = 1
Pokud S = 0, pak: P R. B
A <
Pokud S = 1, pak: P L B
instrukce # 1 2 3 4 5 6 7
Instrukce po Turingovi J1 P R. J. P L J.
skoková instrukce # 5 B B

Podle konvencí stroje Post -Turing se každá z instrukcí Print, Erase, Left a Right skládá ze dvou akcí:

  1. Akce pásku: {P, E, L, R}, potom
  2. 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í:

  1. Akce pásku: podívejte se na symbol na pásku pod hlavou
  2. 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í:

  1. Akce pásku: podívejte se na symbol na pásku pod hlavou
  2. 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

  1. { J0 xxx, J1 xxx}
  2. { J1 xxx, J xxx}
  3. { 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
Stavový diagram dvoustavového zaneprázdněného bobra (malá kresba, pravý roh) se převede na ekvivalentní stroj Post-Turing s nahrazením 7 instrukcí Post – Turing za stav „Turing“.
2stavový Busy Beaver běží na počítači P – T
Instrukce HALT přidává 15. stav.
2stavový Busy Beaver běží na počítači P – T
„Běh“ dvoustavového zaneprázdněného bobra se všemi mezikroky stroje Post-Turing.

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.