Důkaz, že L_u není rekurzivní

Betlista
Matfyz(ák|ačka) level I
Příspěvky: 24
Registrován: 21. 11. 2007 14:59
Typ studia: Informatika Mgr.

Důkaz, že L_u není rekurzivní

Příspěvek od Betlista »

Zdravím,

nějak nemůžu přjít na to jak dokázat větu 5.9 (očíslování podle poznámek od Kučery): Univerzální jazyk L_u je rek. spočetný, ale není rekurzivní.

Rozumím tomu, že kdyby \overline{L_u} byl rek. spočetný, tak podle věty 5.8 (když jazyk L i jeho doplněk je rek. spočetný, pak je L rekurzivní) musí být L_u rekurzivní.

Ztratil jsem se někde tam, že když pro spor předpokládáme existenci M, takového, že \overline{L_u} = L(M) a pomocí M pak udělám M', jak je možné, že L(M') = L_{DIAG}? Rozumím tomu, co dělá M', ale přijde mi, že to není to, co bych očekával od TS pro L_{DIAG}, protože kdybych měl M_w takový, že přijme slovo w, tak M' ho taky prijme, ale L_{DIAG} je přesný opak, on by nepřijal (z definice L_{DIAG}).

Na druhou stranu nejde to jednoduše otočit, že když M' přijme já nepřijmu, protože kdyby se M' nezastavil, tak nevím o tom, že mám přijmout...
Odpovědět

Zpět na „NTIN090 Základy složitosti a vyčíslitelnosti“