Příklady Turingova stroje - Turing machine examples
Následující příklady doplňují článek Turingův stroj .
Turingův úplně první příklad
Následující tabulka je Turingovým úplně prvním příkladem ( Alan Turing 1937):
- „1. Stroj lze sestrojit pro výpočet sekvence 0 1 0 1 0 1 ...“ (0 <prázdné> 1 <prázdné> 0 ...) ( nerozhodnutelné str. 119)
| Konfigurace | Chování | ||
|---|---|---|---|
| m-konfigurace (stav) |
Symbol pásky | Páskové operace | Konečná konfigurace m (stav) |
| b | prázdný | P0, R. | C |
| C | prázdný | R. | E |
| E | prázdný | P1, R. | F |
| F | prázdný | R. | b |
Pokud jde o akce, které stroj ve skutečnosti provádí, Turing (1936) ( Nerozhodnutelný s. 121) uvádí následující:
- „Tuto [příkladovou] tabulku (a všechny následující tabulky stejného druhu) je třeba chápat tak, že pro konfiguraci popsanou v prvních dvou sloupcích se operace ve třetím sloupci provádějí postupně a stroj poté přejde do m-konfigurace v posledním sloupci. " (Nerozhodnutelný s. 121)
Dává to velmi jasně najevo, když redukuje výše uvedenou tabulku na jedinou instrukci nazvanou „b“ ( nerozhodnutelná str. 120), ale jeho instrukce se skládá ze 3 řádků. Pokyn „b“ má tři různé možnosti symbolů {Žádný, 0, 1}. Po každé možnosti následuje sled akcí, dokud se nedostaneme do sloupce úplně vpravo, kde je konečná konfigurace m „b“:
| Aktuální m-konfigurace (instrukce) | Symbol pásky | Operace na pásce | Konečná konfigurace m (instrukce) |
|---|---|---|---|
| b | Žádný | P0 | b |
| b | 0 | R, R, P1 | b |
| b | 1 | R, R, P0 | b |
Jak poznamenala řada komentátorů včetně samotného Turinga (1937) (např. Post (1936), Post (1947), Kleene (1952), Wang (1954)), Turingovy pokyny nejsou atomové - další zjednodušení modelu může být provedeny bez snížení jeho výpočetního výkonu; více na stroji Post – Turing .
Jak je uvedeno v článku Turingův stroj , Turing navrhl, aby byl jeho stůl dále atomizován umožněním pouze jediného tisku/vymazání, po kterém následuje pohyb jedné pásky L/R/N. Dává nám tento příklad první převedené tabulky ( Undecidable , str. 127):
| Aktuální m-konfigurace (Turingův stav) | Symbol pásky | Tisková operace | Pohyb pásky | Konečná m-konfigurace (Turingův stav) |
|---|---|---|---|---|
| q 1 | prázdný | P0 | R. | q 2 |
| q 2 | prázdný | P prázdné, tj. E | R. | q 3 |
| q 3 | prázdný | P1 | R. | q 4 |
| q 4 | prázdný | P prázdné, tj. E | R. | q 1 |
Turingovo prohlášení stále zahrnuje pět atomových operací. Při dané instrukci (m-konfigurace) stroj:
- pozoruje páskový symbol pod hlavou
- na základě pozorovaného symbolu přejde k příslušné sekvenci instrukcí, kterou má použít
- vytiskne symbol S j nebo vymaže nebo nedělá nic
- pohybuje páskou doleva, doprava nebo vůbec
- přejde na konečnou konfiguraci m pro daný symbol
Protože akce Turingova stroje nejsou atomové, musí simulace stroje atomizovat každou 5-tici na sekvenci jednodušších akcí. Jedna z možností - použitá v následujících příkladech „chování“ jeho stroje - je následující:
- (q i ) Testovací symbol pásky pod hlavou: Pokud je symbol S 0, přejděte na q i .01, pokud symbol S 1 přejděte na q i .11, pokud symbol S 2 přejděte na q i .21 atd.
- (q i .01) vytiskněte symbol S j 0 nebo vymažte nebo nedělejte nic, pak přejděte na q i .02
- (q i .02) posuňte pásku doleva nebo doprava, vůbec ne, pak přejděte na qm0
- (q i .11) vytiskněte symbol S j 1 nebo vymažte nebo nedělejte nic, pak přejděte na q i .12
- (q i .12) posuňte pásku doleva nebo doprava, vůbec ne, pak přejděte na qm1
- (q i .21) vytiskněte symbol S j 2 nebo vymažte nebo nedělejte nic, pak přejděte na q i .22
- (q i .22) posuňte pásku doleva nebo doprava, vůbec ne, pak přejděte na qm2
- (atd. - se všemi symboly se musí počítat)
Takzvané „kanonické“ stroje s konečným stavem provádějí testy symbolů „paralelně“; více viz mikroprogramování .
V následujícím příkladu toho, co stroj dělá, si povšimneme některých zvláštností Turingových modelů:
- „Konvence psaní obrázků pouze na alternativní čtverce je velmi užitečná: vždy ji využiji.“ (Nerozhodnutelný s. 121)
Při tisku tedy přeskakuje každé další políčko. Vytištěné čtverečky se nazývají F-čtverce; prázdné čtverce mezi nimi mohou být použity pro „značky“ a nazývají se „E-čtverce“ jako v „náchylných k vymazání“. F-čtverce jsou zase jeho „figurkové čtverce“ a budou nést pouze symboly 1 nebo 0-symboly, které nazýval „figury“ (jako v „binárních číslech“).
V tomto případě začíná páska „prázdně“ a „figury“ se na ni poté vytisknou. Pro stručnost jsou zde uvedeny pouze stavy TABLE:
Zde je zobrazen stejný „běh“ se všemi mezilehlými potisky pásek a pohyby:
Podrobný pohled na tabulku odhaluje určité problémy s Turingovým vlastním příkladem - ne všechny symboly jsou započítány.
Předpokládejme například, že jeho páska nebyla zpočátku prázdná. Co by se stalo? Turingův stroj bude číst jiné hodnoty, než jsou zamýšlené hodnoty.
Kopírovací podprogram
Jedná se o velmi důležitý podprogram používaný v rutině „násobení“.
Příklad Turingova stroje zpracovává řetězec 0s a 1s, přičemž 0 představuje prázdný symbol. Jejím úkolem je zdvojnásobit jakoukoli sérii 1 s, která se na pásce objeví, tak, že mezi ně napíšete 0. Například když hlava čte „111“, zapíše 0, pak „111“. Výstupem bude „1110111“.
Aby tento Turingův stroj splnil svůj úkol, bude potřebovat pouze 5 provozních stavů, které se nazývají {s 1 , s 2 , s 3 , s 4 , s 5 }. Každý stát provádí 4 akce:
- Přečtěte si symbol pod hlavou
- Napište výstupní symbol, který určuje stát
- Přesuňte pásku doleva nebo doprava podle rozhodnutí státu
- Přepnout do následujícího stavu podle aktuálního stavu
„Běh“ sekvencí strojů prostřednictvím 16 konfigurací stroje (aka Turingovy státy):
Chování tohoto stroje lze popsat jako smyčku: začíná v s 1 , nahrazuje první 1 číslicí 0, poté se pomocí s 2 přesune doprava, přeskočí 1 s a objeví se první 0. s 3 pak přeskočí další sekvenci 1 s (původně žádné) a nahradí první 0, kterou najde, s 1. s 4 se přesune zpět doleva, přeskočí 1 s, dokud nenajde 0 a přepne na s 5 . s 5 se poté přesune doleva, přeskočí 1 s, dokud nenajde 0, které původně napsal s 1 .
Nahradí 0 nulou 1, posune se o jednu pozici doprava a znovu zadá s 1 pro další kolo smyčky.
To pokračuje, dokud s 1 nenajde 0 (to je 0 uprostřed dvou řetězců 1 s), kdy se stroj zastaví.
Alternativní popis
Další popis vidí problém v tom, jak sledovat, kolik „1“ existuje. Nemůžeme použít jeden stav pro každé možné číslo (stav pro každý z 0,1,2,3,4,5,6 atd.), Protože pak bychom potřebovali nekonečné stavy, které by reprezentovaly všechna přirozená čísla, a stavový stroj je konečný - budeme to muset nějakým způsobem sledovat pomocí pásky.
Základní způsob, jak to funguje, je zkopírování každé „1“ na druhou stranu, pohyb tam a zpět - je dostatečně inteligentní, aby si pamatoval, na které části cesty je. Podrobněji přenáší každou „1“ na druhou stranu tím, že rozpoznává dělící „0“ uprostřed a rozpoznává „0“ na druhé straně, aby věděl, že dosáhla konce. Vrací se stejnou metodou, detekuje prostřední „0“ a poté „0“ na původní straně. Tato „0“ na původní straně je klíčem k hádance, jak sleduje počet jedniček.
Jde o to, že před nesením „1“ označí tuto číslici jako „převzatou“ a nahradí ji „0“. Když se vrátí, vyplní „0“ zpět „1“, poté přejde na další , označí ji „0“ a cyklus zopakuje, přenese „1“ napříč a tak dále. Při každém výletu napříč a zpět se značka „0“ přesune o krok blíže ke středu . Díky tomu sleduje, kolik „1“ je zaznamenáno.
Když se vrátí, značka „0“ vypadá jako konec sbírky „1“ k ní - jakékoli „1“, které již byly přeneseny, jsou pro ni neviditelné (na druhé straně značky „0“ ) a tak to vypadá, jako by to fungovalo na (N -1) čísle „1“ s - podobně jako důkaz matematickou indukcí .
Úplný „běh“ ukazující výsledky přechodných „pohybů“. Chcete -li to vidět lépe, klikněte na obrázek a poté klikněte na stažení ve vyšším rozlišení:
3stavový zaneprázdněný bobr
Následující Turingova tabulka pokynů byla odvozena z Petersona (1988), strana 198, obrázek 7.15. Peterson pohne hlavou; v následujícím modelu se páska pohybuje.
| Symbol pásky | Aktuální stav A. | Současný stav B | Současný stav C. | ||||||
|---|---|---|---|---|---|---|---|---|---|
| Napište symbol | Přesuňte pásku | Další stav | 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 | L | B |
| 1 | 1 | L | C | 1 | R. | B | 1 | N. | STŮJ |
Kresba „stavu“ 3stavového zaneprázdněného bobra zobrazuje vnitřní posloupnosti událostí, které jsou nutné ke skutečnému provedení „stavu“. Jak bylo uvedeno výše, Turing (1937) naprosto jasně ukazuje, že toto je správná interpretace 5-tic, které popisují instrukci ( Undecidable , str. 119). Další informace o atomizaci Turingových 5-tic naleznete na Post-Turingově stroji :
Následující tabulka ukazuje "komprimovaný" běh - pouze Turingovy stavy:
Úplný „běh“ 3stavového zaneprázdněného bobra. Výsledné Turingovy stavy (to, čemu Turing říkal „m-konfigurace“-„konfigurace stroje“) jsou zobrazeny zvýrazněně šedě ve sloupci A a také pod pokyny stroje (sloupce AF-AU)):
Reference
Úplné reference viz Turingův stroj .
- Ivars Peterson, 1988, The Mathematical Tourist: Snapshots of Modern Mathematics , WH Freeman and Company, New York, ISBN 0-7167-2064-7 (pbk.). Turingovy stroje jsou popsány na str. 194ff, příklad zaneprázdněného bobra je na obrázku 7.15 na straně 198.
- Martin Davis editor, 1965, The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions , Raven Press, New York, no ISBN, no card catalog number.
- Alan Turing, 1937, On Computable Numbers, with an Application to the Entscheidungsproblem , str. 116ff, with short comments by Davis on page 115.
- Alan Turing, 1937, On Computable Numbers, with an Application to the Entscheidungsproblem. Oprava , str. 152-154.
