Čtení: 40 minHodnotí se: zápočtový test, úloha 1 (6 b)

1 Návrh Turingova stroje

Po přečtení umíš

převést jazyk na fáze výpočtu a pak na přechodovou funkci
splnit požadavek na počet pásek, čas i nedeterminismus
najít chyby na prázdném slově a na okraji pásky
zdůvodnit časovou složitost stroje

Na zápočet stačí 10 z 30 bodů, takže tato úloha za 6 bodů a self-redukce za 6 bodů tě k němu dovedou. Je to nejlépe nacvičitelná část testu.

1.1 Ukázka: přičtení jedničky

Stroj čte binární číslo a přičte k němu 1. Nejvyšší bit je vlevo. Člověk by šel na konec čísla a nesl přenos zpět. Stroj udělá totéž:

δ(q0, 0) = (q0, 0, →)     jdi na konec čísla
δ(q0, 1) = (q0, 1, →)
δ(q0, ♯) = (qc, ♯, ←)     konec, otoč se a nes přenos
δ(qc, 1) = (qc, 0, ←)     1 + přenos = 0, přenos pokračuje
δ(qc, 0) = (qA, 1, •)     0 + přenos = 1, hotovo
δ(qc, ♯) = (qA, 1, •)     čísla došla, přidej novou jedničku

Vyzkoušej si ho. Krok provede jeden přechod a ukáže ho, zvýrazněné políčko je hlava. Změň vstup a sleduj, jak se nese přenos.

Vstup:

Stroj je hotový ve dvou průchodech, takže běží v čase $O(n)$ .

Celé umění je vidět už tady: stav je to, co si stroj pamatuje (jdu doprava, nesu přenos), a páska je zbytek paměti.

1.2 Co je Turingův stroj

Definice 1.2 (Deterministický Turingův stroj)

Má konečnou množinu stavů $Q$ , vstupní abecedu $\Sigma$ , abecedu pásky $G \supsetneq \Sigma$ s prázdným symbolem ♯, $k$ pásek a přechodovou funkci. Přechod zapisujeme

\delta(q, a, b) = (q', a', b', D_1, D_2), \qquad D \in \{\leftarrow, \to, \bullet\}.

Stroj podle stavu a čtených symbolů změní stav, přepíše symboly a pohne hlavami. Přijímá ve stavu $q_A$ a zamítá v $q_R$ .

Pokud v řešení přechod neuvedeš, napiš na začátek, že chybějící přechod znamená zamítnutí. Proseminář jinak chce úplnou funkci, tímto ji zkrátíš.

Definice 1.3 (Časová složitost)

Stroj pracuje v čase $T(n)$ , pokud na každém vstupu délky $n$ skončí po nejvýše $T(n)$ krocích. Měříme nejhorší případ přes všechny vstupy dané délky.

1.3 Postup v testu

Přečti si požadavky: kolik pásek, jaký čas, smí být nedeterministický?
Napiš fáze slovy. Tři věty stačí a dávají body i při chybě v tabulce.
Přiřaď stavy. Jedna fáze je obvykle jeden stav, plus informace, kterou si musíš pamatovat.
Napiš přechody. Začni šťastnou cestou.
Projdi tři vstupy: prázdné slovo, slovo z jazyka a slovo těsně mimo jazyk.
Zdůvodni čas: kolik průchodů, jak dlouhý každý z nich.

Varování 1.4 (Past prázdného slova)

Moje první verze dvoupáskového stroje v příkladu níže přijímala slovo a. Přijetí na ♯ jsem dal do stavu, ve kterém stroj kopíruje, a tak přijal každé slovo ze samých a. Odhalil to až test na krátkých slovech. Přijetí prázdného slova patří do samostatného počátečního stavu.

1.4 Řešené příklady ze cvičení

Příklad 1.5 (Dvě pásky, lineární čas:

\{a^n b^n\}

(cvičení 1.2))

Nápad: a zkopíruj na druhou pásku. Pak za každé b odškrtni jedno a zpět.

δ(q0, ♯, ♯) = (qA, ♯, ♯, •, •)     prázdné slovo
δ(q0, a, ♯) = (q1, a, a, →, →)
δ(q1, a, ♯) = (q1, a, a, →, →)     kopíruj
δ(q1, b, ♯) = (q2, b, ♯, •, ←)     první b, vrať se na poslední a
δ(q2, b, a) = (q2, b, a, →, ←)     páruj
δ(q2, ♯, ♯) = (qA, ♯, ♯, •, •)     obě došla současně

Vstup:

Čas: hlava 1 jde jen doprava a jeden krok je navíc na přepnutí, tedy $n + 2 = O(n)$ .

Zkus v krokovači aab a abb. Skončí bez přechodu, takže stroj zamítne.

Příklad 1.6 (Jedna páska:

\{a^n b^n c^n\}

(cvičení 1.3))

Nápad: Vždy označ jedno a jako X, jedno b jako Y a jedno c jako Z a vrať se. Až a dojdou, zkontroluj, že zbyly jen značky.

δ(q0, a) = (q1, X, →)     q0: další a, nebo kontrola
δ(q0, Y) = (q4, Y, →)
δ(q0, ♯) = (qA, ♯, •)
δ(q1, a) = (q1, a, →)     q1: jdi k prvnímu b
δ(q1, Y) = (q1, Y, →)
δ(q1, b) = (q2, Y, →)
δ(q2, b) = (q2, b, →)     q2: jdi k prvnímu c
δ(q2, Z) = (q2, Z, →)
δ(q2, c) = (q3, Z, ←)
δ(q3, a|b|Y|Z) = (q3, stejný symbol, ←)     q3: vrať se k X
δ(q3, X) = (q0, X, →)
δ(q4, Y|Z) = (q4, stejný symbol, →)     q4: konečná kontrola
δ(q4, ♯) = (qA, ♯, •)

Vstup:

Čas: $n/3$ průchodů po $O(n)$ krocích, tedy $O(n^2)$ .

Příklad 1.7 (Palindromy na jedné pásce (cvičení 1.1))

Nápad: Přečti a smaž první znak, zapamatuj si ho ve stavu, dojdi na konec a porovnej. Stav qr0 znamená „jdu doprava a pamatuji si 0“.

δ(q0, 0) = (qr0, ♯, →)    δ(q0, 1) = (qr1, ♯, →)    δ(q0, ♯) = (qA, ♯, •)
δ(qr0, 0|1) = (qr0, stejný, →)     δ(qr0, ♯) = (qc0, ♯, ←)
δ(qr1, 0|1) = (qr1, stejný, →)     δ(qr1, ♯) = (qc1, ♯, ←)
δ(qc0, 0) = (qb, ♯, ←)    δ(qc0, ♯) = (qA, ♯, •)
δ(qc1, 1) = (qb, ♯, ←)    δ(qc1, ♯) = (qA, ♯, •)
δ(qb, 0|1) = (qb, stejný, ←)       δ(qb, ♯) = (q0, ♯, →)

Čas: $O(n^2)$ . Přechod $\delta(q_{c0}, \sharp)$ řeší lichou délku, kdy byl smazaný znak prostředek.

Příklad 1.8 (Stroj pro DFA (cvičení 1.5))

Stavy TS jsou stavy automatu. Pro každý stav $p$ a znak $a$ přidej $\delta_{TS}(p, a) = (\delta(p, a), a, \to)$ . Na ♯ přejdi do $q_A$ , pokud $p \in F$ , jinak do $q_R$ . Stroj běží v čase $n + 1$ .

1.5 Nedeterminismus: hádej a ověř

Definice 1.9 (Nedeterministický stroj)

Přechodů smí být víc a vzniká strom výpočtů. Stroj přijme, pokud přijme aspoň jedna větev. Zamítne, jen když zamítnou všechny.

Postup je vždy stejný:

Co uhodnu? Dělitele, podmnožinu, polohu středu.
Jak dlouho hádám? Polynomiálně vůči délce vstupu.
Jak deterministicky ověřím? Také polynomiálně.

Zamítající větve neřeš. Stačí, že pro slovo z jazyka nějaká větev existuje a pro slovo mimo jazyk žádná.

Příklad 1.10 (Palindromy za

n + 1

kroků na dvou páskách (cvičení 2.1))

Hádáme střed. Každý krok posune hlavu 1 doprava, takže každá větev skončí do $n + 1$ kroků.

δ(q0, ♯, ♯) = (qA, ♯, ♯, •, •)              prázdné slovo
pro s ∈ {0, 1} ve stavech q0 i qc:
  (qc, s, s, →, →)    ještě první polovina, kopíruj
  (qe, s, s, →, •)    toto byl poslední znak sudé poloviny
  (qe, s, ♯, →, ←)    toto je prostředek liché délky
δ(qe, s, s) = (qe, s, s, →, ←)              porovnávej
δ(qe, ♯, ♯) = (qA, ♯, ♯, •, •)              obě hlavy došly

Stejnou chybu jako výše jsem udělal i tady: přijetí ve stavu qc by přijalo vše. Proto přijímá jen q0 a qe.

Příklad 1.11 (Nejdelší společná podposloupnost (cvičení 2.2))

Vstup je $1^k \# w_1 \# \dots \# w_m$ . Hádáme řetězec $x$ délky $k$ bit po bitu na pracovní pásku. Unární $k$ znamená, že hádání je kratší než vstup. Ověříme pro každé $w_i$ hladovým průchodem, že $x$ je jeho podposloupnost. To je polynomiální čas.

1.6 Prostor

Někdy test chce paměť. Vstupní páska je pak jen ke čtení a počítá se jen pracovní páska.

Příklad 1.12 (

\{0^n 1^n\}

v prostoru

O(\log n)

)

Místo kopírování si na pracovní pásku piš binární počítadlo. Za každou 0 ho zvyš, za každou 1 sniž. Na konci musí být 0 a mezi tím nesmí 0 následovat po 1. Počítadlo do $n$ má $O(\log n)$ bitů. Čas je $O(n \log n)$ .

1.7 Typické chyby

Přijetí prázdného slova ve stavu, kam se stroj vrací i později.
Chybějící tvrzení, že neuvedený přechod znamená zamítnutí.
Zapomenutý návrat hlavy a čtení špatného políčka o jedno vedle.
Dvě pásky, ale odhad času jako u jedné.
U NDTS hádání exponenciálně dlouhého kandidáta.

1.8 Kvíz

Kvíz

1. Proč dvě pásky stačí na palindromy v

O(n)

, když jedna páska potřebuje procházet slovo znovu a znovu? Druhá páska má větší abecedu Druhá páska drží kopii, kterou lze číst opačným směrem Stroj má víc stavů

2. NDTS má na slově 3 zamítající a 1 přijímající větev. Co udělá? Zamítne Přijme Záleží na pořadí větví

3. Co musíš hlídat u návrhu NDTS v polynomiálním čase? Může být správně více možností, ale také žádná. Délku hádání Čas ověření Počet větví musí být polynomiální Každá větev musí skončit

4. Kolik kroků udělá stroj pro

\{a^n b^n\}

z příkladu na slově aabb? Odpověď:

5. Proč se u

1^k\#w_1\#\dots

píše

k

unárně? Kvůli jednoduššímu čtení Aby hádání délky

k

bylo polynomiální ve vstupu Aby šel vstup rozdělit

6. Jakým třem vstupům projdeš stroj v testu a proč?

Ukázat řešení

Prázdné slovo kvůli okrajovému případu, slovo z jazyka kvůli šťastné cestě a slovo těsně mimo jazyk, aby stroj zbytečně nepřijímal.

1.9 Příklady na procvičení

Cvičení 1.13

Sestroj dvoupáskový stroj pro $\{0^n 1^{2n}\}$ v čase $O(n)$ .

Řešení

Nuly zkopíruj na druhou pásku a za každou nulu sežer dvě jedničky.

δ(q0, ♯, ♯) = (qA, ♯, ♯, •, •)
δ(q0, 0, ♯) = (q1, 0, 0, →, →)
δ(q1, 0, ♯) = (q1, 0, 0, →, →)
δ(q1, 1, ♯) = (q2, 1, ♯, •, ←)
δ(q2, 1, 0) = (q3, 1, 0, →, •)     první jednička k této nule
δ(q3, 1, 0) = (q2, 1, 0, →, ←)     druhá jednička, další nula
δ(q2, ♯, ♯) = (qA, ♯, ♯, •, •)

Cvičení 1.14

Popiš NDTS pro problém Composites (binárně zapsané $n$ je složené).

Řešení

Hádej $N$ bitů čísla $d$ . Ověř $1 < d < n$ a dělení se zbytkem 0. Obojí je polynomiální v $N \approx \log_2 n$ . Zkoušení všech dělitelů by bylo exponenciální v $N$ .

1.10 Tahák

Tahák

Stav = co si pamatuji, páska = zbytek paměti.
Postup: fáze slovy → stavy → přechody → prázdné slovo, slovo z jazyka, slovo mimo → čas.
Napiš: „neuvedený přechod znamená zamítnutí“.
Přijetí prázdného slova jen v počátečním stavu.
Dvě pásky: kopie + čtení proti sobě = $O(n)$ .
Jedna páska: značky + průchody = většinou $O(n^2)$ .
NDTS: hádej polynomiálně, ověř polynomiálně, větví smí být exponenciálně.
Prostor: místo kopie binární počítadlo = $O(\log n)$ .

Kapitolu mám prostudovanou