Turingův stroj

Umělecké znázornění Turingova stroje.

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.

Jeden ze způsobu vyjádření Church-Turingovy teze říká, že ke každému algoritmu existuje ekvivalentní Turingův stroj.

[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
- $N$ znamená, že čtecí hlava zůstane na místě

[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 pro 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 (či neposune)

[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\{L,R,N\})^n$

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

$\delta: Q\times\Gamma\rightarrow 2^{Q\times\Gamma\times\{L,R,N\}}$

(Symbol $2 X$ značí potenční množinu k $X$ .)

[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.

Tento článek je příliš stručný nebo neobsahuje důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte nebo alespoň nahradíte tuto šablonu nějakou konkrétnější.

Kategorie: Výpočetní modely | Vyčíslitelnost

Turingův stroj v jiných jazycích: العربية, Беларуская, Български, Bosanski, Català, Dansk, Deutsch, English, Esperanto, Español, Eesti, Suomi, Français, Furlan, עברית, Hrvatski, Magyar, Bahasa Indonesia, Italiano, 日本語, 한국어, Lëtzebuergesch, Lietuvių, Nederlands, Polski, Português, Română, Русский, Simple English, Slovenčina, Slovenščina, Српски / Srpski, Svenska, ไทย, Türkçe, Українська, 中文

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/Turing%C5%AFv_stroj“
Stránka byla naposledy upravena v Stránka byla naposledy editována 18. 6. 2008 v 19:34.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).