5.2 Lineárně omezené Turingovy stroje

Turingův stroj

Turingův stroj (TS) se skládá z řídící jednotky (stavy, přechodová funkce), neomezené pásky (paměti) rozdělené do buněk a čtecí hlavy, která čte a prepisuje jednotlivé symboly na pásce. Čtecí hlava Turingova stroje se na rozdíl od čtecí hlavy konečného automatu může pohybovat oběma směry, či posečkat na stejném místě.

Definice (Turingův stroj)

Turingův stroj

Formálně definujeme Turingův stroj jako uspořádanou sedmici $R = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$, kde:

$Q$ je konečná neprázdná množina stavů,
$\Sigma$ je konečná neprázdná vstupní abeceda,
$\Gamma$ je konečná neprázdná pracovní abeceda ($\Sigma \subset \Gamma$),
$\delta$ je přechodová funkce,
$q_0$ je počáteční stav,
$B \in (\Gamma \setminus \Sigma)$ je prázdný symbol (blank),
$F \subseteq Q$ je množina koncových stavů.

Na začátku výpočtu se Turingův stroj nachází v počátečním stavu $q_0$, páska je vyplněna symboly $B$, na „prvních“ buňkách pásky je zapsán vstup a čtecí hlava ukazuje na první buňku vstupu.

Turingův stroj

Definice (Deterministický Turingův stroj)

Deterministický Turingův stroj

Deterministický Turingův stroj (DTS) pracuje s následující definicí přechodové funkce $\delta$:

\[ \delta : (Q \setminus F) \times \Gamma \to Q \times \Gamma \times \{-1, 0, 1\} \]

Definice přechodové funkce nám říká, že je-li Turingův stroj v nekoncovém stavu a z pásky čte nějaký symbol z pracovní abecedy, poté přejde do dalšího stavu, na pásku zapíše nějaký symbol a čtecí hlavu posune vlevo ($-1$), vpravo ($1$) nebo zůstane na místě ($0$).

Zastavení výpočtu

Ocitne-li se Turingův stroj během výpočtu v koncovém stavu, vždy se zastaví a výpočet tak dále nepokračuje.

Turingův stroj se zastaví právě tehdy, když se dostane do konfigurace, ze které již neexistuje žádný přechod, který by mohl provést (např. koncový stav nebo nedefinovaný přechod).

Definice (Nedeterministický Turingův stroj)

Nedeterministický Turingův stroj

Nedeterministický Turingův stroj (NTS) pracuje s následující definicí přechodové funkce $\delta$:

\[ \delta : (Q \setminus F) \times \Gamma \to \mathcal{P}(Q \times \Gamma \times \{-1, 0, 1\}) \]

Nedeterministický Turingův stroj si na rozdíl od deterministického Turingova stroje může v určité fázi výpočtu vybrat, jak pokračovat.

Znázornění Turingova stroje

Znázornění Turingova stroje se liší zápisem přechodové funkce $\delta$:

Formální zápis (DTS):

\[\delta(S, a) = (A, c, 1)\]

(ze stavu $S$ na symbol $a$ na pásce jdeme do stavu $A$, na pásku zapíšeme symbol $c$ a posuneme se o jednu pozici doprava).

Ohodnocený orientovaný graf: Vrcholy grafu reprezentují stavy. Přechodovou funkci znázorňujeme orientovanými hranami mezi stavy a ohodnocujeme je čtenými symboly, symboly k zápisu a pohybem hlavy.

Konfigurace a výpočet

Definice (Konfigurace Turingova stroje)

Konfigurace Turingova stroje

Nechť $R = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$ je Turingův stroj. Konfigurace je trojice $(\alpha, q, \beta) \in \Gamma^* \times Q \times \Gamma^*$.

$q$ je okamžitý vnitřní stav,
obsah pásky je tvořen řetězcem $\alpha\beta$ (okolní nekonečný prostor je vyplněn symboly $B$),
hlava $R$ se na pásce nachází na pozici $|\alpha| + 1$ (tedy čte první symbol řetězce $\beta$).

Počáteční konfigurace pro vstup $w$ je $(\epsilon, q_0, w)$.

Definice (Přechod Turingova stroje)

Formální popis přechodu

Turingův stroj přejde z konfigurace $(\alpha, q, \beta)$ do konfigurace $(\gamma, r, \pi)$, značíme $(\alpha, q, \beta) \vdash (\gamma, r, \pi)$, pokud pro symboly $a, c, d \in \Gamma$ platí jedna z následujících podmínek:

Posun doleva – $\delta(q, a) = (r, c, -1)$:

\[\alpha = \gamma d, \quad \beta = a\beta', \quad \pi = dc\beta'\]

Posun doleva

Bez posunu – $\delta(q, a) = (r, c, 0)$:

\[\alpha = \gamma, \quad \beta = a\beta', \quad \pi = c\beta'\]

Bez posunu

Posun doprava – $\delta(q, a) = (r, c, 1)$:

\[\beta = ad\pi', \quad \gamma = \alpha c, \quad \pi = d\pi'\]

Posun doprava

Jazyk přijímaný Turingovým strojem

U Turingova stroje definujeme přijetí na základě dosažení koncového stavu.

TS přijímající přechodem do koncového stavu: Stroj přijme slovo $w$, pokud existuje posloupnost konfigurací začínající v počáteční konfiguraci a končící v konfiguraci, kde je stroj ve stavu $q \in F$. Na obsahu pásky po zastavení nezáleží.

\[ L(R) = \{ w \in \Sigma^* \mid \exists \alpha, \beta \in \Gamma^*, q \in F : (\epsilon, q_0, w) \vdash^* (\alpha, q, \beta) \} \]

Kdy Turingův stroj (ne)přijme vstupní řetězec?

Změna v definici přijímání

Na rozdíl od některých definic u zásobníkových automatů, u TS se standardně nevyžaduje prázdná páska ani specifický obsah pásky na konci. Stačí dosáhnout stavu $q \in F$.

Deterministický Turingův stroj (DTS):

Přijme: Výpočet skončí v koncovém stavu ($q \in F$).
Nepřijme:
- Výpočet skončí v nekoncovém stavu (zasekne se).
- Výpočet nikdy neskončí (cyklí se do nekonečna).

Nedeterministický Turingův stroj (NTS):

Přijme: Existuje alespoň jedna větev výpočtu, která skončí v koncovém stavu ($q \in F$).
Nepřijme: Žádná větev výpočtu nevede do koncového stavu (všechny větve buď skončí v nekoncovém stavu, nebo cyklí).

Definice (Lineárně omezený automat)

Lineárně omezený automat

Lineárně omezený automat (LOA, někdy též Lineárně omezený Turingův stroj) je nedeterministický Turingův stroj, ve kterém platí:

Pracovní abeceda obsahuje levou a pravou zarážku ¢ a $\$$.
LOA se nemůže posunout vlevo od ¢ a vpravo od $\$$, ani tyto symboly přepsat.

Formálně je Lineárně omezený automat uspořádaná osmice $R = (Q, \Sigma, \Gamma, \delta, q_0, ¢, \$, F)$, kde:

$Q$ je konečná neprázdná množina vnitřních stavů,
$\Sigma$ je konečná neprázdná vstupní abeceda,
$\Gamma$ je konečná neprázdná pracovní abeceda ($\Sigma \subset \Gamma$),
$\delta$ je zobrazení z $(Q \setminus F) \times \Gamma$ do $\mathcal{P}(Q \times \Gamma \times \{-1, 0, 1\})$,
$q_0 \in Q$ je počáteční stav,
¢ a $\$$ jsou symboly levá a pravá zarážka ($¢, \$ \in \Gamma \setminus \Sigma$),
$F \subseteq Q$ je množina koncových stavů.

LOA přijímá slovo $w \in \Sigma^*$, jestliže $\exists q \in F, \alpha, \beta \in \Gamma^*, (¢, q_0, w\$) \vdash^* (\alpha, q, \beta)$.