TIN 18. Nerozhodnutelnost

Card Set Information

Author:
hrbi
ID:
222687
Filename:
TIN 18. Nerozhodnutelnost
Updated:
2013-06-06 17:34:37
Tags:
tin
Folders:

Description:
mssz 2013
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user hrbi on FreezingBlue Flashcards. What would you like to do?


  1. Diagonalizace
    • důkaz, že množina není spočetná
    • sporem - předpokládám, že spočetná je
    • pak existuje bijektivní zobrazení f na přirozená čísla
    • sestavím "matici" tak, že v horizontálním směru mám prvky nějaké spočetné množiny, ve vertikálním pak všechny prvky množiny, kterou vyšetřuji
    • prvky matice jsou pak "reprezentací" prvků vyšetřované množiny
    • vytvořím nový prvek tak, že vezmu všechny hodnoty na diagonále a pozměním je
    • tento nový prvek jistě nepatří do vyšetřované množiny → spor

  2. Existence jazyků mimo třídu 0
    • pro každou abecedu Σ existuje jazyk nad Σ, který není typu 0
    • důkaz:
    • libovolný jazyk typu 0 nad Σ může být přijat TS
    • všechny tyto TS můžeme systematicky vypisovat - je jich spočetně mnoho
    • množina Σ* obsahuje nekonečně mnoho řetězců a proto je množina všech jazyků 2Σ* nespočetná (viz diagonalizace)
    • rozdílná mohutnost → existuje jazyk, který TS nepřijme → věta platí
  3. Problém zastavení (HP)
    • zajímá nás, zda daný TS zastaví pro danou vstupní větu w
    • HP = {# | M zastaví při w}
    • není rozhodnutelný: diagonalizace
    • je částečně rozhodnutelný: lze ukázat použitím modifikovaného TU, který zastaví přijetím vstupu # právě tehdy, když M zastaví při w, při abnormálním zastavení M také přejde do koncového stavu
    • komplementární problém co-HP = {# | M nezastaví při w} není ani částečně rozhodnutelný, jazyk co-HP tedy není ani rekurzivně vyčíslitelný
  4. Redukce
    • používá se k důkazu, že daný problém není (částečně) rozhodnutelný, neboli, že daný jazyk není rekurzivní (rekurzivně vyčíslitelný)
    • princip:
    • víme, že jazyk A není rekurzivní (rekurzivně vyčíslitelný)
    • zkoumáme jazyk B
    • ukážeme, že lze A úplným TS převést (redukovat) na B
    • pak B rovněž není rekurzivní (rekurzivně vyčíslitelný)
    • formálně:
    • A ⊆ Σ*, B ⊆ Ψ* jsou jazyky, redukce jazyka A na jazyk B je totální, rekurzivně vyčíslitelná funkce σ: Σ* → Ψ* taková, že ∀w ∈ Σ*: w ∈ A ⇔ σ(w) ∈ B
    • pak A ≤ B
  5. Postův problém
    • Postův systém: S = <(α0, β0), (α1, β1), ..., (αk, βk)>, αi, βi ∈ Σ+
    • rešení Postova systému: neprázdná posloupnost I = <i1, i2, ..., im> taková, že αi1αi2...αim = βi1βi2...βim
    • Postův problém (PCP): existuje řešení daného Postova systému?
    • nerozhodnutelné

What would you like to do?

Home > Flashcards > Print Preview