Příklady Turingova stroje - Turing machine examples

Následují příklady k doplnění článku Turingův stroj.

Turingův první příklad

Následující tabulka je Turingův první příklad (Alan Turing 1937):

"1. Může být konstruován stroj pro výpočet posloupnosti 0 1 0 1 0 1 ..." (0 1 0 ...) (Nerozhodnutelné str. 119)

S ohledem na to, jaké akce stroj ve skutečnosti provádí, Turing (1936) (Nerozhodnutelné str. 121) uvádí následující:

„Tuto [ukázkovou] 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 jsou operace ve třetím sloupci prováděny postupně a stroj poté přejde do konfigurace m v posledním sloupci. “ (Nerozhodnutelné str.

Dává to velmi jasně najevo, když redukuje výše uvedenou tabulku na jedinou instrukci s názvem „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 nedojdeme ke sloupci zcela vpravo, kde je konečná m-konfigurace „b“:

Jak bylo pozorováno řadou 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 lze být provedeno bez snížení jeho výpočetní síly; Více na Post-Turingův stroj.

Jak je uvedeno v článku Turingův stroj, Turing navrhl, aby jeho stůl byl dále atomizován povolením pouze jediného tisku / mazání následovaného jediným pohybem pásky L / R / N. Dává nám tento příklad první převedené tabulky (Nerozhodnutelné, str. 127):

Turingovo prohlášení stále znamená pět atomových operací. Na daný pokyn (m-konfigurace) stroj:

1. pozoruje páskový symbol pod hlavou
2. na základě pozorovaného symbolu jde do příslušné sekvence instrukcí, která se má použít
3. vytiskne symbol S_j nebo maže nebo nic nedělá
4. posune pásku doleva, doprava nebo vůbec
5. přejde do konečné m-konfigurace pro tento symbol

Protože akce Turingova stroje nejsou atomové, musí simulace stroje atomizovat každou pětici n-tic do sekvence 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) Vyzkoušejte páskový symbol pod hlavou: Pokud je symbol S₀ přejděte na q_i.01, pokud symbol S₁ přejděte na q_i.11, pokud symbol S₂ přejděte na q_i.21 atd.

(q_i.01) vytisknout symbol S_j0 nebo vymazat nebo nedělat nic, pak přejděte na q_i.02

(q_i.02) přesuňte pásku doleva nebo doprava, vůbec ne, pak přejděte na qm0

(q_i.11) vytisknout symbol S_j1 nebo vymazat nebo nedělat nic, pak přejděte na q_i.12

(q_i.12) přesuňte pásku doleva nebo doprava, vůbec ne, pak přejděte na qm1

(q_i.21) vytisknout symbol S_j2 nebo vymazat nebo nedělat nic, pak přejděte na q_i.22

(q_i.22) přesuňte pásku doleva nebo doprava, vůbec ne, pak přejděte na qm2

(atd. - všechny symboly musí být zohledněny)

Takzvaný „kanonický“ konečné stavové automaty provádět zkoušky symbolů „paralelně“; Více na 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í čísel pouze na střídavé čtverce je velmi užitečná: vždy ji využiji.“ (Nerozhodnutelné str.

Při tisku tedy přeskočí každý druhý čtverec. Vytištěné čtverce se nazývají F-čtverce; prázdné čtverečky mezi nimi mohou být použity pro „značky“ a nazývají se „E-čtverce“ jako v „podléhají vymazání“. F-čtverce jsou zase jeho „figurové čtverce“ a budou nést pouze symboly 1 nebo 0 - symboly, které nazval „figurky“ (jako v „binárních číslech“).

V tomto příkladu začíná páska „prázdnou“ a na ni jsou poté vytištěny „číslice“. Pro stručnost jsou zde uvedeny pouze TABLE stavy:

Je zde zobrazen stejný „běh“ se všemi mezilehlými potisky pásky a pohyby:

Bližší pohled na tabulku odhalí určité problémy s Turingovým vlastním příkladem - ne všechny symboly jsou zohledněny.

Předpokládejme například, že jeho páska nebyla původně prázdná. Co by se stalo? Turingův stroj by četl jiné hodnoty než zamýšlené hodnoty.

Kopie podprogramu

Toto je velmi důležitý podprogram používaný v rutině "znásobení".

Příklad Turingova stroje zpracovává řetězec 0 s a 1 s, přičemž 0 představuje prázdný symbol. Jeho úkolem je zdvojnásobit jakoukoli sérii 1s, které se vyskytnou na pásku, zapsáním 0 mezi ně. Když například hlava přečte „111“, zapíše 0 a poté „111“. Výstup bude „1110111“.

Aby mohl Turingův stroj splnit svůj úkol, bude potřebovat pouze 5 provozních stavů, které se nazývají {s₁, s₂, s₃, s₄, s₅}. Každý stát provádí 4 akce:

1. Přečtěte si symbol pod hlavou
3. Napište výstupní symbol, o kterém rozhodne stát
5. Přesuňte pásku doleva nebo doprava podle rozhodnutí státu
7. Přepněte do následujícího stavu, o kterém rozhoduje aktuální stav

„Běh“ sekvencí strojů prostřednictvím 16 konfigurací strojů (neboli Turingovy stavy):

Chování tohoto stroje lze popsat jako smyčku: začíná v s₁, nahradí první 1 číslicí 0, poté použije s₂ přesunout doprava, přeskočit více než 1 s a narazit na první 0. s₃ pak přeskočí další sekvenci 1 s (zpočátku žádné nejsou) a nahradí první 0, kterou najde, 1. s₄ přesune zpět doleva, přeskočí přes 1 s, dokud nenajde 0 a přepne na s₅. s₅ pak se přesune doleva a přeskočí 1 s, dokud nenajde 0, kterou původně napsal s₁.

Nahradí 0 s 1, posune o jednu pozici doprava a zadá s₁ znovu na další kolo smyčky.

To pokračuje až do s₁ najde 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 je „1“. 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, aby představovaly všechna přirozená čísla, a státní 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 pohybem tam a zpět - je dostatečně inteligentní, aby si pamatoval, na které části cesty je. Podrobněji přenáší každou číslici „1“ na druhou stranu tím, že rozpoznává oddělovací „0“ uprostřed a rozpoznává „0“ na druhé straně, aby věděla, že je dosaženo konce. Vrátí se stejnou metodou, detekuje prostřední „0“ a poté „0“ na původní straně. Tato „0“ na původní straně je klíčem k skládačce toho, jak sleduje počet 1.

Trik spočívá v tom, že před přenesením „1“ označí tuto číslici jako „převzatou“ tím, že ji nahradí „0“. Když se vrátí, vyplní tuto „0“ zpět „1“, pak přejde na další, označit jej „0“ a opakovat cyklus, přenášet „1“ napříč a tak dále. S každou cestou napříč a zpět se značka „0“ posune o krok blíže ke středu. Takto sleduje, kolik "1" to má za sebou.

Když se vrátí, značka „0“ vypadá jako konec kolekce „1“ - všechny „1“, které již byly použity, jsou pro ni neviditelné (na druhé straně značky „0“) ) a tak to vypadá, jako by to fungovalo na (N-1) počtu „1“ - podobně jako důkaz od matematická indukce.

Úplný „běh“ zobrazující výsledky přechodných „pohybů“. Chcete-li to lépe vidět, klikněte na obrázek a poté klikněte na stažení ve vyšším rozlišení:

3-stav Busy Bobr

Následující Turingova tabulka pokynů byla odvozena od Petersona (1988) strana 198, obrázek 7.15. Peterson pohne hlavou; v následujícím modelu se páska pohybuje.

"Stavový" výkres 3-stavového zaneprázdněného bobra ukazuje vnitřní sekvence událostí potřebných ke skutečnému provedení "stavu". Jak je uvedeno výše, Turing (1937) jasně ukazuje, že se jedná o správnou interpretaci 5 n-tic, které instrukci popisují (Nerozhodnutelné, str. 119). Další informace o atomizaci Turingových n-tic najdete na Post-Turingův stroj:

Následující tabulka ukazuje „komprimovaný“ běh - pouze Turingovy stavy:

Úplný „běh“ 3-stavového zaneprázdněného bobra. Výsledné Turingovy stavy (to, co Turing nazval „m-konfigurace“ - „konfigurace stroje“) jsou zobrazeny zvýrazněny šedě ve sloupci A a také podle pokynů stroje (sloupce AF-AU)):

Reference

Kompletní reference viz Turingův stroj.

• Ivars Peterson, 1988, Matematický turista: momentky moderní matematiky, W. H. 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, žádné číslo ISBN, žádné katalogové číslo karty.

• Alan Turing, 1937, Na vypočítatelných číslech s aplikací na problém Entscheidungs, s. 116ff, s krátkým komentářem Davise na straně 115.
• Alan Turing, 1937, Na vypočítatelných číslech s aplikací na problém Entscheidungs. Oprava, str. 152-154.