od kolage » 13. 2. 2013 15:04
Nejake poznamky:
1. Chce to nejak prevest z halting problemu / z K1 na tuto mnozinu S a dokazat tak, ze neni rekurzivni. Pak dokazat, ze -S je R.S. (-S = {<x,y> | Wx prunik Wy je neprazdny} ... f ~ existuje z: z in Wx & z in Wy - zhruba takto - to je RSP)
2. Jednoduse pres SMN vetu - klasika
3. Asi nejsnadneji z vrcholoveho pokryti (k se zanecha a, ale s mnozinou R se pak nejak machruje ?!)
- Přílohy
-
Nejake poznamky:
1. Chce to nejak prevest z halting problemu / z K1 na tuto mnozinu S a dokazat tak, ze neni rekurzivni. Pak dokazat, ze -S je R.S. (-S = {<x,y> | Wx prunik Wy je neprazdny} ... f ~ existuje z: z in Wx & z in Wy - zhruba takto - to je RSP)
2. Jednoduse pres SMN vetu - klasika
3. Asi nejsnadneji z vrcholoveho pokryti (k se zanecha a, ale s mnozinou R se pak nejak machruje ?!)