Turingův stroj

Z Wikipedie, otevřené encyklopedie

Turingův stroj (TS) je teoretický model počítače popsaný matematikem Alanem Turingem. Skládá se z procesorové jednotky, tvořené konečným automatem, programu ve tvaru pravidel přechodové funkce a potenciálně nekonečné pásky pro zápis mezivýsledků. Využívá se pro modelování algoritmů v teorii vyčíslitelnosti.

[editovat] Definice

Turingův stroj je šestice $M = (Q,Γ, s, b, F,δ)$ kde :

$Q$ je konečná množina vnitřních stavů
$Γ$ je konečná abeceda symbolů a znaků
$s\in Q$ je počáteční stav
$b\in \Gamma$ je symbol reprezentující prázdný symbol ( $b$ neni součástí vstupní abecedy přijímaného řetězce)
$F\subseteq Q$ je množina koncových stavů
přechodová funkce, kde:
- $L$ znamená posun čtecí hlavy vlevo
- $R$ znamená posun čtecí hlavy vpravo

[editovat] Konfigurace

Konfigurace Turingova stroje je prvek $\left \langle q, s, n \right \rangle$ množiny $Q\times\{yb^\omega \mid y \in \Gamma^*\}\times \mathbb{N}_0$ , kde q je aktuální stav, s je nejmenší souvislá část pásky obsahující všechny neprázdné symboly a n je pozice čtecí hlavy (číslo buňky).

Počáteční konfigurace Turingova stroje pro vstup $w\in\Sigma^*$ je konfigurace $(s, w b ω,0)$ .

[editovat] Výpočet

Na začátku výpočtu je Turingův stroj v počáteční konfiguraci a na pásce je zapsané vstupní slovo. Dále pracuje v jednotlivých krocích:

pokud je aktuální stav zároveň stavem koncovým, výpočet končí
čtecí hlava přečte jeden vstupní symbol z buňky, na které se právě nachází
pokud je v přechodové funkci pro aktuální stav a přečtený symbol definovaný přechod, provede se (v případě více možných přechodů u nedeterministických strojů se vybere jeden náhodně):
- změní se stav
- na aktuální pozici hlavy se zapíše příslušný symbol
- hlava se příslušným způsobem posune

[editovat] Modifikace

Existuje velké množství různých modifikací Turingova stroje, všechny však mají stejnou sílu, tzn. že přijímají stejnou třídu jazyků jako základní model.

n-páskový TS
- čte z a zapisuje do více pásek najednou
- jediná změna je v přechodové funkci:

$\delta: Q\times\Gamma^n\rightarrow Q\times(\Gamma\times\{\leftarrow,\rightarrow,\uparrow\})^n$

nedeterministický TS
- umožňuje „výběr z více možností“

$\delta\subseteq Q\times\Gamma\rightarrow Q\times\Gamma\times\{\leftarrow,\rightarrow,\uparrow\}$

[editovat] Univerzální TS

Univerzální Turingův stroj je takový TS U, který jako vstup přijímá kód jiného TS T (jeho Gödelovo číslo) a vstupní slovo stroje T. Dokáže rozkódovat přechodovou funkci stroje T a výpočet tohoto stroje simulovat. Univerzální TS dokáže vypočítat libovolnou částečně rekurzivní funkci (neboli je ekvivalentní k univerzální částečně rekurzivní funkci), rozhoduje jakýkoliv rekurzivní jazyk a přijímá libovolný rekurzivně spočetný jazyk.