Dukaz

Základní přednáška z teorie algoritmů a efektivní vyčíslitelnosti. Turingovy stroje. Částečně rekurzivní funkce. Rekurzivní a rekurzivně spočetné množiny. Algoritmicky nerozhodnutelné problémy. Věta o rekurzi. Kreativní množiny.
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Dukaz

Příspěvek od Him »

Nevite nekdo, jak se dokazuje toto:

B = \{x : W_x = \emptyset\} - dokázat, že není rekurzivní ani rekurzivně spočetná
B = \{x : W_x 
eq \emptyset\} - dokázat, že není rekurzivní

?
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
QZuzka
Matfyz(ák|ačka) level III
Příspěvky: 209
Registrován: 2. 12. 2007 19:51
Typ studia: Informatika Mgr.
Bydliště: Praha 4

Re: Dukaz

Příspěvek od QZuzka »

Him píše:Nevite nekdo, jak se dokazuje toto:

B = \{x : W_x = \emptyset\} - dokázat, že není rekurzivní ani rekurzivně spočetná
B = \{x : W_x 
eq \emptyset\} - dokázat, že není rekurzivní

?
Pokud koukám dobře, tak to druhé jde přímo z Riceovy věty (existuje turingáč, který přijímá něco, existuje turingáč, který nepřijímá nic).

To první... Vím, že druhá - k tomu doplňková není rekurzivní. Pokud bych uměla dokázat, že je ta druhá rekurzivně spočetná, tak Postovou větou dokážu, že ta první není. Ale teď zrovna nevidím žádný slušný důkaz, že je RS (i když ona RS celkem zřejmě je, protože každý turingáč, který popisuje neprázdný jazyk se pro nějaký vstup (ten z jazyka) zastaví. A teď by to chtělo něco chytrého dodat, aby to byl formálně přijatelný důkaz, a to něco mě právě nenapadá..)
StepanP
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 17. 2. 2011 00:30
Typ studia: Informatika Mgr.

Re: Dukaz

Příspěvek od StepanP »

Zkusil jsem to rozepsat, jak říkala QZuzka. Rozhodně to ale není důkaz s jistotou, jen návrh :)

Označím si množinu a její doplňek:

$A = \{x: W_x 
eq \emptyset}\}$
$\overline A = \{x: W_x = \emptyset}\}$

Podle Strojilových skript, strana 5, důsledek 2:

$A$ je rekurzivně spočetná, protože se dá vyjádřit jako

$A=\{x: \exists y,s\ (y \mbox{ patří do } W_x \mbox{ za $s$ kroků})\}$

Postova věta: Množina $A$ je rekurzivní, právě když $A$ i $\overline A$ jsou rekurzivně spočetné. Neboli $A$ není rekurzivní, právě když $A$ nebo $\overline A$ není rekurzivně spočetná.

Takže: Předpokládejme, že $A$ není rekurzivní. Víme, že $A$ je rekurzivně spočetná (Strojil), takže to musí být $\overline A$, kdo není rekurzivně spočetný. Jinak by obě množiny byly rekurzivně spočetné a z Postovy věty by $A$ byla rekurzivní, což by byl spor s předpokladem.

Předpoklad $A$ není rekurzivní by měl platit z Riceovy věty, jak napsala QZuzka. Možná to ale plyne rovnou z toho důsledku 2, protože se tam dokáže: $K je 1-převoditelný na $A$. Kde $K je:

$K = \{x : x \in W_x\} = \{x:\varphi_x(x)\!\!\downarrow\} = \{x:\Psi_1(x,x)\!\!\downarrow\}$

Protože 1-převoditelnost je silnější než m-převoditelnost, tak je rovnou také m-převoditelný. Z lemma 2 strana 4 víme: Pokud $D$ je rekurzivní a $C je m-převoditelné na D$, pak je $C$ rekurzivní. Dále z věty 3 strana 3: $K$ není rekurzivní.

Takže: Kdyby $A$ bylo rekurzivní, tak by $K$ bylo rekurzivní, protože podle důsledku 2 je $K$ m-převoditelné na $A$ a podle lemma 2 by tedy bylo $K$ rekurzivní. Což by byl spor s větou 3.

Závěr: $A$ není rekurzivní. $\overline A$ není rekurzivně spočetná.
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Dukaz

Příspěvek od Him »

Diky moc!
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
Odpovědět

Zpět na „TIN064 Vyčíslitelnost I“