Turing stroj: popis a příklady Turingových strojů

Stroj Turing je jedním z nejzajímavějších a nejzajímavějších intelektuálních objevů 20. století. Jedná se o jednoduchý a užitečný abstraktní model výpočetní techniky (počítačové a digitální), který je docela běžný pro realizaci jakékoliv počítačové úlohy. Díky jednoduchému popisu a chování matematická analýza tvoří základ teoretické informatiky. Tato studie vedla k hlubší znalosti digitálních počítačů a počtu, včetně pochopení, že existují některé výpočetní problémy, které nelze vyřešit na běžných uživatelských počítačích.

Co to je a kdo vytvořil

Alan Turing se snažil popsat nejprimitivnější model mechanického zařízení, které by mělo stejné základní schopnosti jako počítač. Turing poprvé popsal auto v roce 1936 v článku "Na počítačích s aplikací k problému solvability", který se objevil ve sborníku Londýnské matematické společnosti.

Stroj Turing je počítačové zařízení sestávající z čtecí / zapisovací hlavy (nebo "skeneru") s papírovou páskou procházející přes něj. Páska je rozdělena na čtverce, z nichž každá nese jeden znak - "0" nebo "1". Účelem mechanismu je, aby působil jak jako prostředek pro vstup a výstup, tak jako pracovní paměť pro ukládání výsledků mezistupňů výpočtů.

Z čeho se zařízení skládá

Každý takový stroj se skládá ze dvou částí:

1. Neomezená páska. Je nekonečný v obou směrech a rozdělen na buňky.
2. Automatický řízený program, skener pro čtení a zápis dat. To může být v každém okamžiku v jednom z mnoha států.

Každé zařízení spojuje dvě konečná datová řada: abeceda příchozích symbolů A = {a0, a1, ..., am} a abeceda stavů Q = {q0, q1, ..., qp}. Stav q0 se nazývá pasivní. To je věřil, že zařízení ukončí svou práci, když to dopadne na něj. Stav q1 se nazývá počáteční - stroj zahájí výpočty a začíná v něm. Vstupní slovo se nachází na pásku po jednom písmenu v řadě v každé pozici. Na obou stranách jsou pouze prázdné buňky.

Jak mechanismus funguje

Stroj Turing má zásadní rozdíl od výpočetních zařízení - jeho paměťové zařízení má nekonečnou pásku, zatímco u digitálních zařízení má toto zařízení pás o určité délce. Každá třída úkolů je řešena pouze jedním turingovým strojem. Jiné typy úkolů zahrnují psaní nového algoritmu.

Ovládací zařízení, které je v jednom stavu, se může pohybovat v libovolném směru podél pásu. Napíše do buněk a čte od nich znaky poslední abecedy. Při pohybu se volí prázdný prvek, který vyplňuje pozice, které neobsahují vstupní data. Algoritmus pro stroj Turing určuje pravidla přechodu pro řídicí zařízení. Nastavují hlavu pro čtení a zápis na následující parametry: zápis do buňky nového znaku, přechod do nového stavu, pohyb po levé nebo pravé straně pásky.

Vlastnosti mechanismu

Turingův stroj, stejně jako ostatní výpočetní systémy, má své vlastní vlastnosti a jsou podobné vlastnostem algoritmů:

1. Diskrétnost Digitální stroj pokračuje v dalším kroku n + 1 až po dokončení předchozího. Každý dokončený krok přiřadí, co n + 1 bude.
2. Srozumitelnost Přístroj provádí pouze jednu akci pro stejnou buňku. Vloží znak z abecedy a provede jeden pohyb: vlevo nebo vpravo.
3. Determinismus. Každá poloha v mechanismu odpovídá jednomu provedení konkrétního schématu a v každém stupni akce a pořadí jejich provedení jsou jednoznačné.
4. Výkonnost. Přesný výsledek pro každý stupeň je určen strojem Turing. Program provede algoritmus a v konečném počtu kroků vstoupí do stavu q0.
5. Mass. Každé zařízení je definováno nad platnými slovy v abecedě.

Funkce Turingova stroje

Řešení algoritmů často vyžaduje implementaci funkce. V závislosti na možnosti zápisu řetězce pro výpočet se funkce nazývá algoritmicky řešitelná nebo nerozpustná. Jako soubor přírodních nebo racionálních čísel, slova v konečné abecedě N pro stroj, se posuzuje posloupnost množiny B - slova v binární abecedě B = {0.1}. Výsledek výpočtu také bere v úvahu hodnotu "undefined", která nastane, když algoritmus visí. Pro implementaci funkce je důležité mít v konečné abecedě formální jazyk a řešitelnost problému rozpoznávání správných popisů.

Program pro zařízení

Programy Turingova mechanismu jsou tvořeny tabulkami, ve kterých první řádek a sloupec obsahují znaky vnější abecedy a hodnoty možných vnitřních stavů automatu - vnitřní abecedy. Tabulková data jsou příkazy, které vnímá stroj Turing. Řešení problémů nastává tímto způsobem: písmeno čtené hlavou v buňce, nad níž se nachází, a vnitřní stav hlavy automatu určuje, který příkaz má být proveden. Konkrétně je takový příkaz umístěn na křižovatce symbolů externí abecedy a interní, které jsou v tabulce.

Komponenty pro výpočty

Abychom vytvořili Turingův stroj pro vyřešení jednoho konkrétního úkolu, je nutné pro něj stanovit následující parametry.

Vnější abeceda. Toto je nějaká konečná sada symbolů označená znaménkem A, jejíž základní prvky jsou nazývány písmeny. Jeden z nich - a0 - musí být prázdný. Například abeceda zařízení Turing pracujícího s binárními čísly vypadá takto: A = {0, 1, a0}.

Souvislý řetězec alfanumerických znaků na pásku se nazývá slovo.

Automatický stroj je zařízení, které funguje bez zásahu člověka. V Turingově stroji má několik různých stavů pro řešení problémů a za určitých podmínek se pohybuje z jedné pozice do druhé. Kombinace těchto stavů kočáru je vnitřní abecedou. Má označení písmen formu Q = {q1, q2 ...}. Jedno z těchto ustanovení - q1 - by mělo být počáteční, tj. Co začíná program. Dalším nezbytným prvkem je stav q0, který je konečný, to znamená, že dokončí program a umístí zařízení do zastávkové polohy.

Konverzační tabulka. Tato součást je algoritmem chování vozíku zařízení v závislosti na aktuálním stavu stroje a hodnotě čteného symbolu.

Algoritmus pro automat

Vozík Turingova zařízení během provozu je řízen programem, který během každého kroku provádí sekvenci následujících akcí:

1. Psaní externího znaku abecedy do polohy, včetně prázdné, nahrazením prvku, který byl v něm, včetně prázdného.
2. Přesuňte jeden krok vlevo nebo vpravo.
3. Změňte svůj vnitřní stav.

Při psaní programů pro každý pár znaků nebo pozic musí být přesně popsány tři parametry: _i -prvek z vybrané abecedy A, směr posunu vozu ("←" doleva, "→" doprava, "bod" - žádný pohyb) _k je nový stav zařízení. Například příkaz 1 "←" q ₂ je nastaven na "nahrazení znaku 1, přesunout hlavici vozíku doleva o jednu krokovou buňku a provést přechod do stavu q ₂ ".

Turingův stroj: příklady

Příklad 1. Při zadání algoritmu, který přidá jednu poslední číslici daného čísla umístěného na pásku. Vstupní data - slovo - číslice celého desetinného čísla, zapsané v po sobě následujících buňkách na pásku. V počátečním okamžiku je zařízení umístěno naproti pravému symbolu - číslice čísla.

Rozhodnutí. Pokud se poslední číslice rovná 9, musí být nahrazena číslem 0 a poté přidána jedna k předchozímu znaku. Program v tomto případě pro toto zařízení Turing může být napsán takto:

Zde q1 je stav změny číslice, q ₀ je zastávka. Pokud v q ₁ automat fixuje prvek ze série 0..8, pak ho nahrazuje jedním z hodnot 1 ... 9 a poté se přepne do stavu q ₀ , to znamená, že se přístroj zastaví. Pokud vozík opraví číslo 9, nahradí ho číslem 0, pak se přesune doleva, zastaví se ve stavu q ₁ . Tento pohyb pokračuje, dokud zařízení neukládá číslice menší než 9. Pokud jsou všechny znaky rovny 9, jsou nahrazeny nulami, 0 je nahrazeno předním prvkem, kočár se přesune doleva a zapíše 1 do prázdné buňky. Dalším krokem bude přechod na stav q ₀ - stop.

Příklad 2. Vzhledem k řadě znaků označujících otvírací a zavírací hranaté závorky. Je třeba postavit zařízení Turing, které by odstranilo dvojici vzájemných závorek, tj. Prvků uspořádaných v řadě - "()". Například počáteční data: ") (() (()), odpověď by měla být:") .. (("." Řešení: mechanismus, který je v q ₁ , analyzuje levý prvek v řádku.

Stav q ₁ : pokud je zobrazen symbol "("), posuňte doprava a přejděte na pozici q ₂ ; pokud je definováno "a ₀ ", zastavte.

Stav q ₂ : analýza konstanty "(" pro přítomnost dvojice se provádí, v případě shody se ukáže "). Je-li prvkem pár, pak se vozík vrátí doleva a přejde na q ₃ .

Stav q ₃ : nejprve vymazat symbol "(" a potom ") a přejděte na q ₁ .