Bc. Jan Kaláb <[email protected]>
Popište pomocí kompozitního diagramu jednopáskový Turingův stroj M, který provádí sčítání dvou čísel ve dvojkové soustavě. Pokud bude vstupní kofigurace pásky ΔA#BΔω, kde A, B ∈ {0, 1}⁺, tak stroj zastaví normálně a na pásce bude po zastavení konfigurace Δ*ΔCΔω, kde C = A + B (ve dvojkové soustavě). Pokud bude na vstupu jiný, než povolený řetězec, tak chování stroje není stanovené.
Viz přiložený kompozitní diagram.
Dvojzásobníkový automat D definujeme jako n-tici D = (Q, Σ, Γ, δ, q₀, Z₀, F), kde
Konfigurace, přechod a jazyk přijímaný dvojzásobníkovým automatem jsou definovány obdobně jako u zásobníkových automatů.
Popište ideu důkazu (podobně jako je tomu u vět 7.2 a 7.3 v přednáškách), že třída jazyků přijímaných dvojzásobníkovými automaty je ekvivalentní třídě jazyků přijímaných Turingovými stroji. Uvažujte pouze dvojzásobníkové automaty přijímající přechodem do akceptačního stavu.
Pozn.: Nezapomeňte, že v důkazu ekvivalence je třeba dokázat oba směry.
Aby byla třída jazyků dvojzásobníkové automatu ekvivalentní třídě jazyků Turingových strojů, musí být dvojzásobníkové automaty schopny provádět stejné operace jako Turingovy stroje. Tedy posun na pásce vlevo, vpravo, čtení a zápis.
Nejdříve ukážeme implementaci pásky pomocí dvou zásobníků. Čtecí hlavu představuje vrchol prvního zásobníku. Obsah páský nalevo od čtecí hlavy pak představuje zbytek prvního zásobníku, obsah pásky napravo pak celý obsah druhého zásobníku.
Nyní můžeme přistoupit k popisu implementace jednotlivých funkci Turingova stroje pomocí dvojzásobníkového automatu:
Tím jsme ukázali, že dvojzásobníkový automat má stejnou funkcionalitu jako Turingův stroj. Nyní ještě ukážeme, že pomocí Turingova stroje dokážeme simulovat dvojzásobníkový automat.
Předpokládejme, že páska Turingova stroje ne nekonečná oběma směry. Zapíšeme na pásku nějaký oddělovací symbol ∉ Σ. Obsah pásky nalevo od něj bude představovat první zásobník, obsah pásky napravo od něj pak druhý zásobník. Vložení symbolu na zásobník bude vypadat následovně: Přesuneme hlavu na Δ za koncem řetězce na pásce (levým nebo pravým, podle toho na který zásobník chceme vkládat) a symbol na pásku zapíšeme. Vyjmutí symbolu ze zásobníku bude podobné: Přesuneme hlavu na poslední symbol znak řetězce na pásce (levý nebo pravý, podle toho ze kterého zásobníku chceme číst) a přepíšeme jej na Δ.
Tímto jsme ukázali, že dvojzásobníkový automat dovede simulovat Turingův stroj a naopak, tudíž jsou třídy jejich jazyků ekvivalentní.
Dokažte, že problém, zda jazyk daného TS obsahuje alespoň jedno slovo z jazyka L₃ = {ww | w ∈ {a, b}*} je nerozhodnutelný. Inspirujte se v přednáškách a semináři STI.
Nápověda: Vhodným postupem je redukce jazyka HP na (problém zastavení) na jazyk problému P = {⟨M⟩ | (L(M) ∩ L₃) ≠ ∅}
Na obrázku 1 je zobrazen TS M₄.
G₄ = {{S, F, B}, {a, b}, P, S}
P:
w = abbaa
| Δ | a | b | b | a | a | Δω |
|---|---|---|---|---|---|---|
| Δ | a | b | b | a | a | Δω |
| Δ | a | b | b | a | a | Δω |
| Δ | a | b | b | a | a | Δω |
| Δ | a | b | b | a | a | Δω |
| Δ | a | b | b | a | a | Δω |
| Δ | a | b | b | a | a | Δω |
| Δ | a | b | b | a | a | Δω |
| Δ | a | b | b | a | Δ | Δω |
| Δ | a | b | b | a | Δ | Δω |
| Δ | a | b | b | Δ | Δ | Δω |
| Δ | a | b | b | Δ | Δ | Δω |
| Δ | a | b | Δ | Δ | Δ | Δω |
| Δ | a | b | Δ | Δ | Δ | Δω |
| Δ | a | Δ | Δ | Δ | Δ | Δω |
| Δ | a | Δ | Δ | Δ | Δ | Δω |
| Δ | Δ | Δ | Δ | Δ | Δ | Δω |
| Δ | Δ | Δ | Δ | Δ | Δ | Δω |
| Δ | Δ | Δ | Δ | Δ | Δ | Δω |
| Δ | Y | Δ | Δ | Δ | Δ | Δω |
| Δ | Y | Δ | Δ | Δ | Δ | Δω |
S ⇒ aF ⇒ abB ⇒ abbB ⇒ abbaS ⇒ abbaaF ⇒ abbaa