Fórum studentů MFF UK

Dakujem, myslel som na nieco podobne...

Mám množinu A, množinu B, jejich ČRF f_a a f_b. Dostanu prvek x a mám rozhodnout, zda patří do průniku/sjednocení, tak pustím paralelně výpočet f_a(x) a f_b(x). Pro průnik čekám, až zastaví oba (pak x do průniku patří), pro sjednocení čekám, až zastaví některý z těch dvou (pak x patří do sjednocení). Dokud čekám, tak nic nevracím, tj. taky můžu čekat věčně (což nastane pokud x nepatří do průniku/sjednocení). Takže jsem ČRF a průnik/sjednocení je r.s..

Doplněk nezachovává RS. Příklad: K. Ukázat, že K je r.s., kdežto doplněk K není. K je r.s. protože když dostanu x, pustím program x na vstup x a čekám, dokud neskončí. Doplněk K není r.s., protože kdyby byl, pak má nějaký index, třeba y. Takže si označím: doplněk K = W_y. Stačí ukázat spor - y patří do K doplňku právě když program y nad vstupem y nezastaví (z def. K doplněk). y patří do W_y právě když program y nad vstupm y zastaví (z def. W_y) - spor.

Otazka pre tych, co tu dvojku riesili: Ako ste na to isli? Lebo asi nestaci povedat, ze vidime, ze zlozenim dvoch ORF ziskame opat ORF (pri rekurzivnych mnozinach), resp ze zjednotenie/prienik def. oborov CRF je opat def obor nejakej CRF, ale doplnok def oboru CRF nie je def obor CRF

Odhadem 8 lidí odešlo dobrovolně a 4 byli odejiti Otázka 2. byla nutná i s důkazem (k mojí smůle).

Kucera opet prekvapil. Dnesni priklady byly:

• 1. Vztah mezi uplne produktivni a produktivni mnozinou vcetne dukazu lemmatu o zachovani uplnosti pri prevodu
• Dokazat zda je prunik,sjednoceni a doplnek rek. spoc. mnozin. take rekurzivne spocetny
• Godelovy vety