5. Turingův stroj a jeho výpočet, Turingův stroj jako akceptor, rekurzivní a rekurzivně spočetné jazyky

Question 1

Turingův stroj

Answer 1

je popsaný britským matematikem Alanem Turingem (1936) je teoretický počítač s neomezenou pamětí, schopný provádět libovolný výpočet, který lze algoritmicky vyjádřit.

Skládá z nekonečné pásky rozdělené do buněk, které mohou obsahovat symboly nebo čtecí hlavy

Čtecí hlavy mohou číst a zapisovat symboly na pásce a pohybovat se po něm doprava a doleva

Turingův stroj pracuje na základě pravidel, která říkají, jak má čtecí hlava reagovat na symboly na pásce

Tyto pravidla jsou reprezentovány v tzv. Turingově stroji v podobě konečného počtu stavů a pravidel

Question 2

Výpočet Turingova stroje

Answer 2

Výpočet je dán sekvencí stavů a pravidel, které jsou aplikovány na každou buňku na pásce

Tyto pravidla jsou založena na aktuálním stavu stroje a na symbolu, který se v dané buňce nachází

Každé pravidlo říká, jak má stroj přejít do nového stavu, co má zapsat do buňky, kam se má čtecí hlava
posunout a jaké další pravidlo se má použít na následující buňku

Celý proces lze provádět nekonečně dlouho, dokud se stroj nezastaví

Question 3

Postup výpočtu

Answer 3

1, Na začátku se Turingův stroj nachází v určitém počátečním stavu na levém konci nekonečné
pásky, která je rozdělena na buňky obsahující symboly

2, Čtecí hlava se posune na buňku, kterou má číst a přečte symbol, který se v této buňce nachází

3, Na základě přečteného symbolu a aktuálního stavu stroje vyhodnotí stroj, jaké pravidlo se má použít

4, Provede změny podle pravidla a pokračuje dále ve čtení symbolů a aplikaci pravidel na následující buňky na pásce

5, Pokud stroj dosáhne konce pásky a nemá další pravidlo, které by se na něj měl aplikovat, zastaví se. V opačném případě pokračuje v čtení a aplikaci pravidel, dokud není zastaven

Question 4

Turingův stroj jako akceptor

Answer 4

Turingův stroj může být použit jako akceptor, tedy jako zařízení, které akceptuje (přijímá) nebo odmítá určitý jazyk

Jazyk je množina řetězců nad určitou abecedou, kterou je Turingův stroj schopen přijímat nebo odmítat

Turingův stroj použit jako akceptor, může být konfigurován tak, aby přijímal nebo odmítal daný jazyk na
základě toho, zda se nachází v koncovém stavu nebo nikoliv

Koncové stavy jsou stavy, ve kterých se stroj nachází, když dokončí čtení vstupního řetězce

Turingův stroj může být také použit pro přijímání kontextového jazyka, což je jazyk, který nelze přijímat pomocí regulárního výrazu nebo konečných atomatů

Pro přijímání takového jazyka je nutné použít nějaký pokročilejší model, jako je právě Turingův stroj

Pro každý jazyk musí být sestaven Turingův stroj s odpovídajícími pravidly pro přechod mezi stavy, zápis symbolů na pásce a posun čtecí hlavy

Question 5

Rekurzivní jazyky

Answer 5

formální jazyk, který je definovány pomocí formálních modelů, jako je např. Turingův stroj

má mnoho aplikací v informatice a matematice

Jazyky, které lze přijímat deterministickým Turingovým strojem, který vždy zastaví a rozhodne, zda je vstupní řetězec součástí jazyka, nebo ne

Rekurzivní jazyky jsou uzavřené na rozhodování a lze určit, zda řetězec patří do jazyka

Question 6

Rekurzivně spočetné jazyky

Answer 6

Jazyky, které lze přijímat nebo generovat pomocí nedeterministického Turingova stroje

Tyto stroje mohou běžet nekonečně dlouho a nemusí vždy zastavit

Rekurzivně spočetné jazyky nejsou uzavřené na rozhodování a nelze určit, zda řetězec patří do jazyka