Stránka 1 z 1

[NTIN073] - Rekurze I

Napsal: 4. 2. 2015 13:49
od Davpe
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ě.

Re: [NTIN073] - Rekurze I

Napsal: 5. 2. 2015 12:36
od exa
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.

Re: [NTIN073] - Rekurze I

Napsal: 5. 2. 2015 16:03
od Davpe
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 \} 
eq \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 \} 
eq \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'