[NTIN073] - Rekurze I

Co se jinam nevejde

[NTIN073] - Rekurze I

Příspěvekod Davpe » 4. 2. 2015 13:49

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ě.
Uživatelský avatar
Davpe
Matfyz(ák|ačka) level II
 
Příspěvky: 98
Registrován: 22. 9. 2010 15:07
Typ studia: Informatika Bc.
Login do SIS: pegrimed

Re: [NTIN073] - Rekurze I

Příspěvekod exa » 5. 2. 2015 12:36

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".

    - ekvivalence definice \Pi^0_1 trid pomoci jednokvantifikatorovy formule a jako "tridy nekonecnych vetvi binarnich stromu"
    - Izolovane prvky \Pi^0_1 trid jsou rekurzivni
    - Schoenfield: Kazda neprazdna \Pi^0_1 trida ma prvek rekurzivni v \emptyset'
    - Low basis theorem: Kazda neprazdna \Pi^0_1 trida ma Low prvek
    - Kazda neprazdna \Pi^0_1 trida ma skoro rekurzivni (computably dominated, s O.R. majorantou) prvek
    - definice mod(x) a wmod(x)
    - ekvivalence: a \gg \emptyset <=> a je stupen 0-1 DiagonallyNonComputable funkce <=> a je stupen kompletniho rozsireni Peanovy aritmetiky
    - Arshlanovo kriterium (jediny RS stupen obsahujici DNC funkci je \emptyset'
    - 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 \lt \emptyset', 1-gen mnozin je co-meager ("hodne")
    - Kleene-Post: Existuji A,B < \emptyset' 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 (\forall A > \emptyset' \exists B: B'=A)
    - Definice 1-gen pomoci \Pi^0_1 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 \emptyset < A < \emptyset')
    - 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.
exa
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

Příspěvekod Davpe » 5. 2. 2015 16:03

S dovolením doplním poslední přednášku;)
    Pro neprázdnou \Pi^0_1 třídu A která je podmnožinou (0,1)-DNR existuje x_0 t.ž. A \cap \{f : f(x_0) = i \} \neq \emptyset pro i = 0,1
    Pro neprázdnou \Pi^0_1 třídu A která je podmnožinou (0,1)-GNR existuje x_0 t.ž. A \cap \{f : f(<x_0, j>) = B(j)\  \forall j \} \neq \emptyset pro lib. B \in 2^\omega .

A v sešitě mám ještě náznak důkazu Posta pro dvě množiny:
    Existují r.s. množiny A, B které jsou T-neporovnatelné a \emptyset < A, B < \emptyset'
Uživatelský avatar
Davpe
Matfyz(ák|ačka) level II
 
Příspěvky: 98
Registrován: 22. 9. 2010 15:07
Typ studia: Informatika Bc.
Login do SIS: pegrimed


Zpět na Ostatní

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron