Vyčíslitelnost a složitost

Aktuální informace k předmětu, zápočtům, výukové materiály atd. najdete zde.

Seznam cvičení

• 22.9. Turingův stroj (TS) a příklady TS
  • Navrhněte TS, který ze zadaného slova nad abecedou {a,b} umaže od začátku i od konce nejdelší možné stejně dlouhé úseky znaků a (kde umazání znamená přepsání znaky □). Tedy např. k vstupnímu slovu aaababaa stroj nechá jako výstup slovo abab, kdežto vstupní slovo aaabab nezmění; ze slova aaa zbude ε. Řešení na str. 194 v [JAN-TI].
  • Domácí úkol: Navrhněte TS, který přijímá jazyk {w#w | w∈{a,b}*}.
• 29.9. Simulace variant TS
  • Dokažte, že k-páskový TS jde simulovat pomocí (standardního) jednopáskového TS. Idea řešení na str. 177 v Introduction to the Theory of Computation od M. Sipsera (3. edice).
  • Domácí úkol: dokažte, že TS s dvoudimenzionální páskou lze simulovat pomocí (standardního) jednopáskového TS.
6.10. Nerozhodnutelnost problému zastavení

• Problém DHP je varianta problému zastavení, kde vstup je kód TS M, tedy <M> a otázkou je, zda se M zastaví pro vstup <M> svého vlastního kódu.

  Dokažte, že problém DHP je nerozhodnutelný. Pomocí něj pak dokažte, že je nerozhodnutelný i HP (klasický problém zastavení). Řešení na str. 211 v [JAN-TI].

• Domácí úkol: nechť k-PDA je zásobníkový automat s k zásobníky, kde k-PDA definujeme jako P=(Q,Σ,Γ,δ,q₀,​Z₀​,F), s přechodovou funkcí δ: Q × (Σ ∪ {ε}) × Γ^k → 2^{Q × (Γ*)k}. Takže 0-PDA je vlastně NFA, 1-PDA je klasický PDA jak jej známe.

  Dokažte, že 2-PDA dovede simulovat TS, a tedy je silnější model, než 1-PDA (není třeba psát celou konstrukci, jde hlavně o ideu). Má smysl uvažovat 3-PDA?

• 13.10. Částečně rozhodnutelné jazyky a převoditelnost
  • Dokažte, že {<A, B> | A, B jsou DFA takové, že L(A)=L(B)} je rozhodnutelný.
  • Dokažte, že {<A> | A je takový DFA, že L(A)=∅} je rozhodnutelný. Řešení najdete na str. 196 v Introduction to the Theory of Computation od M. Sipsera (3. edice).
  • Dokažte, že jazyk L_ε={<M> | M je takový TS, že ε∈L(M)} je rekurzivně spočetný a zároveň není rozhodnutelný. Nerozhodnutelnost je popsána v teorému 5.8.2 zde, částečnou rozhodnutelnost dokažte redukcí na HP, tj. L_ε≤ HP.

  • Domácí úkol: dokažte, že jazyk {<M> | M je takový TS, že L(M) je regulární} není rozhodnutelný.

• 20.10. Riceova věta, triviální a I/O vlastnosti Turingových strojů
  • Dokažte, že každá triviální vlastnost Turingových strojů je I/O vlastností.
  • U každé z následujících vlastností TS rozhodněte, zda je triviální, nebo netriviální, a zda je, nebo není I/O vlastností. Pro ne-I/O vlastnosti najděte dva stroje M₁, M₂ se stejnou I/O tabulkou, z nichž jeden vlastnost má a druhý ne. Poté určete, u kterých vlastností plyne nerozhodnutelnost jazyka {<M> | M má danou vlastnost} přímo z Riceovy věty. U zbylých se pokuste rozhodnout, zda je jazyk rozhodnutelný.
    1. M má více než 100 stavů.
    2. L(M) = ∅.
    3. Výpočet M je pro každý vstup konečný.
    4. L(M) je částečně rozhodnutelný jazyk.
    5. M na vstupu ε provede více než 10 kroků.
    6. L(M) je konečný.
    7. M během výpočtu na vstupu ε někdy vstoupí do stavu q₇.
    8. L(M) obsahuje alespoň dvě různá slova.
    9. M počítá funkci f(x) = x+1 (čísla zapsaná binárně).
    10. L(M) = Σ*.
    11. Existuje TS M', který má méně stavů než M a stejnou I/O tabulku jako M.
    12. M rozhoduje Halting problém.
  • Domácí úkol k zamyšlení: Riceova věta říká pouze, že netriviální I/O vlastnosti jsou nerozhodnutelné, ale neříká nic o částečné rozhodnutelnosti. Najděte a své odpovědi zdůvodněte:
    • netriviální I/O vlastnost V, pro kterou je jazyk {<M> | M má V} částečně rozhodnutelný,
    • netriviální I/O vlastnost, pro kterou je částečně rozhodnutelný doplněk tohoto jazyka,
    • netriviální I/O vlastnost, pro kterou není částečně rozhodnutelný ani jazyk, ani jeho doplněk.
• 27.10. První zápočtový test
• 3.11. todo
• 10.11. todo
• 17.11. Státní svátek
• 24.11. todo
• 1.12. todo
• 8.12. Druhý zápočtový test
• 15.12. Opravné testy