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

Konfigurace TS

• 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 přijímaný TS

• Jazyk $L(T)$ nazýváme jazyk přijímaný TS $T$
  • = částečně rekurzivní jazyk
  • = rekurzivně spočetný jazyk
  • = akceptovaný jazyk
• Třída jazyků se nazývá $RecEnum$

Jazyk rozhodovaný TS

• 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í TS $T$.
  • = jazyk rozhodovaný
  • = jazyk rekurzivní
• Třída jazyků se nazývá $Rec$ (je podtřídou $RecEnum$)

Navigace

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