The flashcards below were created by user
hrbi
on FreezingBlue Flashcards.
-
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
-
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í
-
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ý
-
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
-
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é
|
|