Turingův stroj

Turingův stroj (MT)  je abstraktní exekutor (abstraktní počítač). To bylo navrženo Alanem Turingem v roce 1936 formalizovat koncept algoritmu .

Turingův stroj je rozšířením konečného automatu a podle Church-Turingovy teze je schopen simulovat všechny vykonavatele (nastavením přechodových pravidel), které nějakým způsobem implementují proces výpočtu krok za krokem, ve kterém je každý krok výpočtu docela základní.

To znamená, že pomocí nějakého Turingova stroje lze implementovat jakýkoli intuitivní algoritmus [1] .

Zařízení

Složení Turingova stroje zahrnuje pásku neomezenou v obou směrech (jsou možné Turingovy stroje, které mají několik nekonečných pásek), rozdělenou do buněk [2] [3] , a ovládací zařízení (také nazývané zapisovací-čtecí hlava ( GZCH ) ), schopný být v jednom z mnoha stavů . Počet možných stavů řídicího zařízení je konečný a přesně daný.

Ovládací zařízení se může pohybovat po pásce doleva a doprava, číst a zapisovat do buněk znaky nějaké konečné abecedy. Je přidělen speciální prázdný symbol, který vyplní všechny buňky na pásce, kromě těch z nich (konečné číslo), na které se zapisují vstupní data.

Řídicí zařízení pracuje podle přechodových pravidel , která představují algoritmus implementovaný daným Turingovým strojem. Každé přechodové pravidlo dává stroji pokyn, v závislosti na aktuálním stavu a symbolu pozorovaném v aktuální buňce, zapsat nový symbol do této buňky, přejít do nového stavu a přesunout jednu buňku doleva nebo doprava. Některé stavy Turingova stroje lze označit jako terminální a přechod na kterýkoli z nich znamená konec práce, zastavení algoritmu.

Turingův stroj je považován za deterministický , pokud každá kombinace symbolu státu a stuhy v tabulce odpovídá nejvýše jednomu pravidlu. Pokud existuje pár „symbol páska-stav“, pro který existují 2 nebo více instrukcí, nazývá se takový Turingův stroj nedeterministický .

Popis Turingova stroje

Konkrétní Turingův stroj je specifikován výčtem prvků množiny písmen abecedy A, množiny stavů Q a množiny pravidel, podle kterých stroj funguje. Mají tvar: q i a j →q i1 a j1 d k (pokud je hlava ve stavu q i , a ve sledované buňce je napsáno písmeno a j , pak hlava přejde do stavu q i1 , a Do buňky se zapíše j1 místo a j , hlava udělá pohyb d k , který má tři možnosti: buňka doleva (L), buňka doprava (R), zůstat na místě (N)). Pro každou možnou konfiguraci <q i , a j > existuje právě jedno pravidlo (pro nedeterministický Turingův stroj může být pravidel více). Neexistují žádná pravidla pouze pro konečný stav, ve kterém se stroj jednou zastaví. Kromě toho musíte určit počáteční a koncový stav, počáteční konfiguraci na pásce a umístění hlavy stroje.

Příklad

Příklad Turingova stroje pro násobení čísel v unární číselné soustavě . Záznam pravidla „q i a j →q i1 a j1 R/L/N“ je třeba chápat takto: q i  je stav, ve kterém se toto pravidlo provádí, a j  je údaj v buňce, ve které je hlavička nachází, q i1  je stav, do kterého chcete přejít, a j1  - to, co potřebujete zapsat do buňky, R / L / N - příkaz k přesunu.

Stroj funguje podle následujících pravidel:

Popis stavů:

Vynásobte pomocí MT 3 x 2 v systému jednotek. Protokol uvádí počáteční a konečný stav MT, počáteční konfiguraci na pásce a umístění hlavy stroje (podtržený symbol).

Start. Jsme ve stavu q 0 , do stroje jsme zadali údaje: *111x11=*, hlava stroje je umístěna na prvním znaku *.

1. krok. Podíváme se na tabulku pravidel, co bude stroj dělat, když je ve stavu q 0 a nad symbolem „*“. Toto pravidlo je z 1. sloupce 5. řádku - q 0 *→q 0 *R. To znamená, že přejdeme do stavu q 0 (tedy neměníme), symbol se změní na „*“ (tedy se nemění) a posuneme se po zadaném textu „*111x11=*“. vpravo o jednu pozici (R), pak je pro 1. znak 1. Stav q 0 1 (1. sloupec 1. řádek) je zase zpracováván pravidlem q 0 1→q 0 1R. To znamená, že je zde opět jen přechod doprava o 1 pozici. To se děje, dokud se nepostavíme na symbol „x“. A tak dále: vezmeme stav (index u q), vezmeme symbol, na kterém stojíme (podtržený symbol), spojíme je a podíváme se na zpracování výsledné kombinace podle tabulky pravidel.

Jednoduše řečeno, algoritmus násobení je následující: označíme 1. jednotku 2. faktoru, nahradíme ji písmenem „a“ a přeneseme celý 1. faktor za rovnítko. Převod se provádí střídavým nahrazením jednotek 1. násobitele za "a" a přidáním stejného počtu jednotek na konec řádku (vlevo od "*" úplně vpravo). Poté změníme všechna „a“ až po znaménko násobení „x“ zpět na jednotky. A cyklus se opakuje. Koneckonců, A vynásobené B může být reprezentováno jako A + A + A B krát. Nyní označíme 2. jednotku 2. násobitele písmenem „a“ a opět jednotky převedeme. Pokud před znaménkem „=“ nejsou žádné jednotky, je násobení dokončeno.

Turingova úplnost

Dá se říci, že Turingův stroj je nejjednodušší počítač s lineární pamětí, který podle formálních pravidel transformuje vstupní data pomocí sekvence elementárních akcí .

Elementarita akcí spočívá v tom, že akce změní pouze malý kus dat v paměti (v případě Turingova stroje pouze jednu buňku) a počet možných akcí je konečný. Navzdory jednoduchosti Turingova stroje lze na něm spočítat vše, co lze spočítat na jakémkoli jiném stroji, který provádí výpočty pomocí sekvence elementárních operací. Tato vlastnost se nazývá úplnost .

Jedním z přirozených způsobů, jak dokázat, že výpočetní algoritmy, které lze implementovat na jednom počítači, lze implementovat na jiném, je simulovat první stroj na druhém.

Imitace je následující. Na vstup druhého stroje se přivádí popis programu (pravidel provozu) prvního stroje a vstupní data , která měla být přijata na vstupu prvního stroje. Takový program (pravidla fungování druhého stroje) je nutné popsat tak, aby v důsledku výpočtů byl výstup stejný, jaký by vrátil první stroj, kdyby přijal data .

Jak bylo řečeno, na Turingově stroji je možné napodobit (nastavením přechodových pravidel) všechny ostatní vykonavatele, kteří nějakým způsobem implementují proces výpočtu krok za krokem, ve kterém je každý krok výpočtu zcela elementární.

Na Turingově stroji můžete simulovat Postův stroj , normální Markovovy algoritmy a jakýkoli program pro běžné počítače, který převádí vstupní data na výstup podle nějakého algoritmu. Na různých abstraktních exekutorech je zase možné Turingův stroj napodobit. Exekutoři, u kterých je to možné, se nazývají Turing kompletní.

Existují programy pro konvenční počítače, které napodobují činnost Turingova stroje. Ale tato simulace je neúplná, protože Turingův stroj má abstraktní nekonečnou pásku. Nekonečnou datovou pásku nelze plně simulovat na počítači s konečnou pamětí: celková paměť počítače - RAM, pevné disky, různá externí paměťová média, registry procesoru a mezipaměť atd. - může být velmi velká, ale přesto je vždy konečná. . Teoretický limit množství informací, které mohou být uvnitř daného povrchu, je až do faktoru roven entropii černé díry se stejným povrchem.

Varianty Turingova stroje

Model Turingova stroje umožňuje rozšíření. Lze uvažovat Turingovy stroje s libovolným počtem pásek a vícerozměrné pásky s různými omezeními. Všechny tyto stroje jsou však Turingovy kompletní a jsou modelovány běžným Turingovým strojem.

Turingův stroj běžící na polonekonečné pásce

Jako příklad takové redukce uvažujme následující větu: Pro jakýkoli Turingův stroj existuje ekvivalentní Turingův stroj běžící na polonekonečné pásce (tj. pásce, která je nekonečná v jednom směru).

Zvažte důkaz, který podal Yu.G. Karpov v knize Theory of Automata. Důkaz této věty je konstruktivní, to znamená, že uvedeme algoritmus, pomocí kterého lze pro jakýkoli Turingův stroj sestrojit ekvivalentní Turingův stroj s deklarovanou vlastností. Nejprve libovolně očíslujeme buňky pracovní pásky MT, to znamená, že určíme nové umístění informací na pásce:

Poté buňky přečíslujeme a budeme předpokládat, že symbol "*" není obsažen ve slovníku MT:

Nakonec Turingův stroj změníme tak, že zdvojnásobíme jeho počet stavů a ​​změníme posun čtecí a zapisovací hlavy tak, aby v jedné skupině stavů byla činnost stroje ekvivalentní jeho provozu ve stínované zóně a ve druhé skupině stavů stroj funguje jako původní stroj v nezastíněné oblasti. Pokud se během provozu MT objeví symbol '*', pak čtecí a zapisovací hlava dosáhla hranice zóny:

Počáteční stav nového Turingova stroje je nastaven v té či oné zóně, podle toho, kde v původní pásce byla v původní konfiguraci umístěna čtecí a zapisovací hlava. Je zřejmé, že nalevo od omezujících značek "*" není páska použita v ekvivalentním Turingově stroji.

Dvourozměrné Turingovy stroje

• Ant Langton

Viz také

• Multiplatformní program JFLAP - simulátor automatu, Turingovy stroje, gramatika, kreslí graf automatu
• Univerzální Turingův stroj
• Nedeterministický Turingův stroj
• Pravděpodobnostní Turingův stroj
• Turingův kvantový stroj
• Teorie algoritmů
• Turingova bažina
• Turingův diagram
• Minského auto

Další abstraktní implementátoři a formální výpočetní systémy

• Normální Markovův algoritmus ( produkční programování )
• Postův stroj ( automatické programování )
• Rekurzivní funkce (teorie vyčíslitelnosti)
• Lambda kalkul ( funkční programování )
• Brainfuck ( imperativní programování )

Poznámky

1. ↑ Nefyodov, 1992 , str. 97.
2. ↑ Nefyodov, 1992 , str. 94.
3. ↑ Ebbinhouse, 1972 , s. 24.

Literatura

• John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Kapitola 8. Úvod do teorie Turingova stroje // Úvod do teorie automatů, jazyků a počítání. - M .: Williams , 2002. - 528 s. - ISBN 0-201-44124-1 .
• Karpov Yu.G. Teorie automatů. - Peter, 2003. - ISBN 5-318-00537-3 .
• Ebbinhaus GD, Jacobs K., Man FK, Hermes G. Turingovy stroje a rekurzivní funkce. — M .: Mir, 1972. — 262 s.
• Nefedov V. N., Osipova V. A. Kurz diskrétní matematiky. — M. : MAI, 1992. — 260 s.

Odkazy

• Turingův stroj // Přednáška Alexandra Shena v projektu PostNauka (04/06/2013)

Slovníky a encyklopedie	Velká dánština velká čínština Britannica (online) Universalis
V bibliografických katalozích BNE : XX550362 BNF : 11978871z GND : 4203525-9 J9U : 987007555894805171 LCCN : sh85138778 NDL : 00573533 SUDOC : 027831655