Jazyk přijímaný TS, jazyk rozhodovaný TS

Konfigurace

• Konfigurace Turingova stroje je dána
  • stavem řídící jednotky
  • obsahem pásky
  • pozicí hlavy
• Konkrétní konfiguraci stroje $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,F)$ popíšeme trojicí
  • $(u,q,v)$, či zkráceně $uqv$, kde $u,v\in {\Gamma }^{\ast }$ a $q\in Q$
• Počáteční konfigurace stroje $M$ pro vstup $w\in {\Sigma }^{\ast }$ je konfigurace $q_{0}w$
• Akceptující konfigurace stroje $M$ pro vstup $w\in {\Sigma }^{\ast }$ je např. $w{q}_{Accept}$
• Zamítající konfigurace stroje $M$ pro vstup $w\in {\Sigma }^{\ast }$ je např. $w{q}_{Reject}$

Výpočet

• Výpočet Turingova stroje $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,F)$ na vstupním slově $w\in {\Sigma }^{\ast }$ chápeme jako posloupnost konfigurací $C_0,C_1,C_2,...$ kde $C_0$ je iniciální konfigurace $q_{0}w$ a pro $i=0,1,2,...$ máme $C_i{⊢}_M{C}_{i+1}$ (tedy $C_{i+1}$ dostaneme z $C_i$ jedním krokem, aplikací přechodové funkce $\delta$). Výpočet může skončit v koncové konfiguraci, nebo být nekonečný.
• Stroj $M$ akceptuje vstupní řetězec $w\in {\Sigma }^{\ast }$ právě když výpočet $M$ na $w$ je konečný a poslední konfigurace je akceptující.
• Stroj $M$ zamítá vstupní řetězec $w\in {\Sigma }^{\ast }$ právě když výpočet $M$ na $w$ je konečný a poslední konfigurace je zamítající.
• Množinu všech slov $w\in {\Sigma }^{\ast }$, které TS $T$ přijímá = akceptuje, značíme $L(T)$.
• Jazyk $L(T)$ nazýváme jazyk částečně rekurzivní = akceptovaný TS $T$.
• Pokud navíc platí, že TS $T$ zamítá každé slovo, které nepatří do $L(T)$, nazýváme jazyk $L(T)$ jazyk rekurzivní = rozhodovaný TS $T$.

Navigace

Předchozí: Turingův stroj, nedeterministický TS Následující: Church-Turingova teze, varianty TS Celý okruh: 1. Teoretické základy informatiky