Dukaz

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í

?

Him wrote: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á..)

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 \text{ patří do } W_x \text{ 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á.

Diky moc!