Nevite nekdo, jak se dokazuje toto:
- dokázat, že není rekurzivní ani rekurzivně spočetná
- dokázat, že není rekurzivní
?
Dukaz
-
- 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
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).Him píše:Nevite nekdo, jak se dokazuje toto:
- dokázat, že není rekurzivní ani rekurzivně spočetná
- dokázat, že není rekurzivní
?
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á..)
-
- Matfyz(ák|ačka) level I
- Příspěvky: 1
- Registrován: 17. 2. 2011 00:30
- Typ studia: Informatika Mgr.
Re: Dukaz
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:
Podle Strojilových skript, strana 5, důsledek 2:
je rekurzivně spočetná, protože se dá vyjádřit jako
Postova věta: Množina je rekurzivní, právě když i jsou rekurzivně spočetné. Neboli není rekurzivní, právě když nebo není rekurzivně spočetná.
Takže: Předpokládejme, že není rekurzivní. Víme, že je rekurzivně spočetná (Strojil), takže to musí být , kdo není rekurzivně spočetný. Jinak by obě množiny byly rekurzivně spočetné a z Postovy věty by byla rekurzivní, což by byl spor s předpokladem.
Předpoklad 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: je 1-převoditelný na . Kde je:
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 je rekurzivní a je m-převoditelné na , pak je rekurzivní. Dále z věty 3 strana 3: není rekurzivní.
Takže: Kdyby bylo rekurzivní, tak by bylo rekurzivní, protože podle důsledku 2 je m-převoditelné na a podle lemma 2 by tedy bylo rekurzivní. Což by byl spor s větou 3.
Závěr: není rekurzivní. není rekurzivně spočetná.
Označím si množinu a její doplňek:
Podle Strojilových skript, strana 5, důsledek 2:
je rekurzivně spočetná, protože se dá vyjádřit jako
Postova věta: Množina je rekurzivní, právě když i jsou rekurzivně spočetné. Neboli není rekurzivní, právě když nebo není rekurzivně spočetná.
Takže: Předpokládejme, že není rekurzivní. Víme, že je rekurzivně spočetná (Strojil), takže to musí být , kdo není rekurzivně spočetný. Jinak by obě množiny byly rekurzivně spočetné a z Postovy věty by byla rekurzivní, což by byl spor s předpokladem.
Předpoklad 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: je 1-převoditelný na . Kde je:
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 je rekurzivní a je m-převoditelné na , pak je rekurzivní. Dále z věty 3 strana 3: není rekurzivní.
Takže: Kdyby bylo rekurzivní, tak by bylo rekurzivní, protože podle důsledku 2 je m-převoditelné na a podle lemma 2 by tedy bylo rekurzivní. Což by byl spor s větou 3.
Závěr: není rekurzivní. není rekurzivně spočetná.