Turingův stroj
Turingův stroj je termín z informatiky. Turingův stroj je spíše systém pravidel, stavů a přechodů než skutečný stroj. Poprvé jej v roce 1936 popsal anglický matematik a počítačový vědec Alan Turing. Turingův stroj má dva účely: rozhodování ve formálních jazycích a řešení matematických funkcí. Turingovy stroje jsou jedním z nejdůležitějších formálních modelů při studiu informatiky.
Model Turingova stroje
Společné základy
Turingův stroj se skládá z následujících komponent (zjednodušeně):
- Omezená množina stavů (s jedním stavem označeným jako počáteční stav; za běhu má Turingův stroj vždy aktuální stav).
- Nekonečná páska s paměťovými buňkami a čtecím/zapisovacím zařízením, které se může na pásce pohybovat.
- Definice tzv. přechodové funkce
Musí být také definována pracovní abeceda (sada znaků).
Při spuštění Turingova stroje musí být na nekonečné pásce stroje přítomno slovo (z pracovní abecedy). Čtecí/zapisovací zařízení na prvním znaku nyní přečte první znak a v závislosti na aktuálním stavu Turingova stroje přepisuje znak novým nebo se posune o jednu buňku doleva nebo doprava. Dále lze přepínat aktuální stav stroje.
Turingovy stroje, které rozhodují o jazycích
Pro teorii rozhodovatelnosti se říká, že Turingův stroj rozhoduje o jazyce, pokud je vždy schopen určit, zda je dané slovo obsaženo v určitém jazyce, nebo ne. Proto má stroj obvykle dva speciální stavy označené jako Accept a Reject. Po určité době dojde k dosažení jednoho z těchto dvou stavů (v závislosti na vstupním slově) a stroj se zastaví. Pokud bude vždy dosažen pouze jeden z těchto dvou stavů, říká se, že Turingův stroj polorozhoduje o jazyce.
Turingovy stroje, které počítají funkce
Pokud se Turingův stroj používá pro výpočet funkcí, má pouze jeden koncový stav. Když stroj dospěje do tohoto stavu, zastaví se a výsledek funkce (v závislosti na vstupu) lze najít na pásce.
Vliv Turingových strojů
Turingovy stroje nebyly vynalezeny za účelem jejich reálného sestrojení, ale jsou velmi důležité pro teoretickou informatiku, protože představují jeden z nejjednodušších modelů počítačů. Churchova-Turingova teze říká, že všechny počítače jsou tak výkonné jako Turingovy stroje. Toho lze využít při dokazování, zda je nějaký problém řešitelný počítačem, nebo ne.
Varianty
- Turingův stroj se může skládat z více nekonečných pásek (a více čtecích/zapisovacích zařízení). Je však prokázáno, že takové stroje jsou pouze stejně výkonné jako stroje s jednou páskou. Vícepáskové stroje jsou užitečné při řešení složitějších problémů.
- Pokud má Turingův stroj nedeterministickou přechodovou funkci, může při čtení znaku dojít k více přechodům z jednoho stavu do mnoha jiných. To opět nezvyšuje výkon Turingových strojů. Nicméně nedeterministické Turingovy stroje (jak se jim tehdy říkalo) mohou případně silně zkrátit dobu výpočtu. Touto otázkou se zabývá diskuse P versus NP a zatím není vyřešena. Většina vědců však předpokládá, že nedeterministické stroje mohou na určitých problémech pracovat mnohem rychleji.
- Univerzální Turingův stroj je varianta, která dokáže simulovat Turingův stroj se vstupem.
