Turingův stroj

Z Wikipedie, otevřené encyklopedie

Skočit na: Navigace, Hledání
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 pravostranně 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.

Obsah

[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ů
  • \delta: Q\times\Gamma\rightarrow Q\times\Gamma \times \{L,R\} 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 \ranglemnož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,wbω,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:

  1. pokud je aktuální stav zároveň stavem koncovým, výpočet končí
  2. čtecí hlava přečte jeden vstupní symbol z buňky, na které se právě nachází
  3. 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.

  • TS s možností provedení výpočtu bez posunu čtecí hlavy
    • přechodová funkce je rozšířena o N (čtecí hlava zůstane na místě)
\delta: Q\times\Gamma\rightarrow Q\times\Gamma \times \{L,R,N\}
  • TS s oboustranně nekonečnou páskou
    • páska není zleva ohraničená
    • možný posun čtecí hlavy doleva z libovolné konfigurace
  • 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 2X 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.

[editovat] Související články

Citováno z „http://cs.wikipedia.org/wiki/Turing%C5%AFv_stroj“