04.02.2015:
1) Věta o nízké bázi
2) Výběr z:
(a) Pod 1-generickou nejsou nerekurzivní množiny
(b) 1-generická neobsahuje nekonečnou rekurzivně spočetnou podmnožinu
U 2a jsem se trochu zamotal ale bez problémů mi to uznal s tím že myšlenka je správně ale za detaily neručí. Celkově ty papíry četl docela bleskově.
[NTIN073] - Rekurze I
-
- Matfyz(ák|ačka) level I
- Příspěvky: 1
- Registrován: 5. 2. 2015 12:14
- Typ studia: Informatika Mgr.
- Login do SIS: 27221206
Re: [NTIN073] - Rekurze I
Za sebe: dukazy obou veci jsem spis obkreslil, druhy jsem si pamatoval asi tak z 1%, nicmene znamka je spis za pochopeni a schopnost pouzit nez za topeni se v technickych drobnostech.
Pridavam seznam moznych otazek co se ucit, protoze moc nikde jinde detailnejsi sylabus najit nejde, predpokladam ze ale bude zkouset jen ty "zajimavejsi".
Pridavam seznam moznych otazek co se ucit, protoze moc nikde jinde detailnejsi sylabus najit nejde, predpokladam ze ale bude zkouset jen ty "zajimavejsi".
- - ekvivalence definice trid pomoci jednokvantifikatorovy formule a jako "tridy nekonecnych vetvi binarnich stromu"
- Izolovane prvky trid jsou rekurzivni
- Schoenfield: Kazda neprazdna trida ma prvek rekurzivni v
- Low basis theorem: Kazda neprazdna trida ma Low prvek
- Kazda neprazdna trida ma skoro rekurzivni (computably dominated, s O.R. majorantou) prvek
- definice mod(x) a wmod(x)
- ekvivalence: <=> a je stupen 0-1 DiagonallyNonComputable funkce <=> a je stupen kompletniho rozsireni Peanovy aritmetiky
- Arshlanovo kriterium (jediny RS stupen obsahujici DNC funkci je
- Bairova veta o kategoriich: Uplny metricky prostor je v sobe co-meager. (coz je tosame jako "spocetny otevreny husty prunik je neprazdny", z cehoz je cca 666x lip videt vyhoda pro 1-gen forcing)
- 1-gen mnozina: neni rekurzivni, existuje 1-gen mnozina , 1-gen mnozin je co-meager ("hodne")
- Kleene-Post: Existuji ktere jsou T-neporovnatelne (finite extension method)
- 1-gen mnozina neobsahuje nekonecnou RS podmnozinu a nejsou pod ni nerekurzivni r.s. mnoziny
- Friedberg: obor hodnot skoku je horni konus halting problemu ()
- Definice 1-gen pomoci mnozin stringu (a ekvivalentni n-genericnost)
- Kuriozita: Pod kazdou r.s. a nerekurzivni mnozinou je 1-gen mnozina
- Reseni postova problemu pomoci finite injury method (existuje r.s. stupen )
- nejakej nahled na to ze existuje i infinite injury method
- Avoiding upper cone: Pro kazde C existuje neporovnatelne r.s. A (coz je Low Basis Theorem akorat s podminkou toho C navic)
- Pod kazdou DNC funkci mensi nez halting problem je nejaka nerekurzivni a r.s. mnozina.
- Davpe
- Matfyz(ák|ačka) level II
- Příspěvky: 98
- Registrován: 22. 9. 2010 16:07
- Typ studia: Informatika Bc.
- Login do SIS: pegrimed
- Kontaktovat uživatele:
Re: [NTIN073] - Rekurze I
S dovolením doplním poslední přednášku;)
- Pro neprázdnou třídu která je podmnožinou (0,1)-DNR existuje t.ž. pro
Pro neprázdnou třídu která je podmnožinou (0,1)-GNR existuje t.ž. pro lib. .
- Existují r.s. množiny A, B které jsou T-neporovnatelné a