Konvergence, definicni obory a spol.

Základní přednáška z teorie algoritmů a efektivní vyčíslitelnosti. Turingovy stroje. Částečně rekurzivní funkce. Rekurzivní a rekurzivně spočetné množiny. Algoritmicky nerozhodnutelné problémy. Věta o rekurzi. Kreativní množiny.
Uživatelský avatar
Almer
Site Admin
Příspěvky: 686
Registrován: 12. 10. 2004 10:58
Typ studia: Informatika Ph.D.
Bydliště: Mala Strana - 203
Kontaktovat uživatele:

Konvergence, definicni obory a spol.

Příspěvek od Almer »

Nazdar, tak jak to je?

Pise se v poznamkach ze f:\mathbb{N}^{k} \rightarrow \mathbb{N} a definicni obor dom(f) \in \mathbb{N}. A nekde dal se rika, ze konverguje, paklize je nekde definovana ( na definicnim oboru ). To je fajn, jenom otazka.

ORF je definovana totalne ( na rozdil od CRF ) a tim padem je definovana na \mathbb{N}^{k} a tim padem je vzdy konvergentni ?. Proc teda jsou dane PRF podmnozinou ORF ( nejsou rovny, protoze Ackermannova fce ).

Tedy jednoduse. Vse by davalo smysl ,paklize ORF jsou konvergentni a CRF jsou konvergentni a hezke:) A je tomu tak?
Zakládající člen klubu Ortodoxních Matfyzáků :-D

Jsem LAMER ale neumim se ani podepsat ]:-)
Uživatelský avatar
Almer
Site Admin
Příspěvky: 686
Registrován: 12. 10. 2004 10:58
Typ studia: Informatika Ph.D.
Bydliště: Mala Strana - 203
Kontaktovat uživatele:

Re: Konvergence, definicni obory a spol.

Příspěvek od Almer »

Napadlo mne jeste, ze by to mohlo byt takto.

ORF - jsou spocetne fce, a tedy pro ne Existuje TS, ktery se vzdy zastavi a jenom pro reseni se zastavi v prijimacim stavu. ( tudiz muze i v odmitacim pro ty vstupy, ktere nejsou resenim ).
PRF - jsou spocetne fce, ale hezci nez ORF ( nepouzivaji minimalizaci ).
CRF - nejsou totalni a tedy pro ne Existuje TS, ktery se zastavi v prijimacim vypoctu a nebo nevime.

Does it make sense?
Zakládající člen klubu Ortodoxních Matfyzáků :-D

Jsem LAMER ale neumim se ani podepsat ]:-)
Uživatelský avatar
beaver
Matfyz(ák|ačka) level III
Příspěvky: 189
Registrován: 2. 2. 2007 09:33
Typ studia: Nestuduji ale učím na MFF
Bydliště: Praha

Re: Konvergence, definicni obory a spol.

Příspěvek od beaver »

Almer píše:Napadlo mne jeste, ze by to mohlo byt takto.

ORF - jsou spocetne fce, a tedy pro ne Existuje TS, ktery se vzdy zastavi a jenom pro reseni se zastavi v prijimacim stavu. ( tudiz muze i v odmitacim pro ty vstupy, ktere nejsou resenim ).
PRF - jsou spocetne fce, ale hezci nez ORF ( nepouzivaji minimalizaci ).
CRF - nejsou totalni a tedy pro ne Existuje TS, ktery se zastavi v prijimacim vypoctu a nebo nevime.

Does it make sense?
Ano tak to je. Pro lepsi predstavu si to zkus prevest na bezne programy:

PRF - programy, ktere pouzivaji pouze cykly pevne delky (pod pojmem pevna delka si nepredstavuj jen konstantu, ale nejakou konecnou hodnotu ... treba ze vstupu)
ORF - programy, ktere pouzivaji i while cykly (tzn. nemusi byt uplne jasne, kolikrat se cyklus provede), ale vime, ze vzdy dokonverguji
CRF - jako ORF, ale na nektere vstupy se muzou zacyklit
Cožpak většina z nás svým způsobem nehledá svou kravičku?
T. Pratchett, z knihy "Kdepak je má kravička"
Uživatelský avatar
Almer
Site Admin
Příspěvky: 686
Registrován: 12. 10. 2004 10:58
Typ studia: Informatika Ph.D.
Bydliště: Mala Strana - 203
Kontaktovat uživatele:

Re: Konvergence, definicni obory a spol.

Příspěvek od Almer »

Jo, asi priste nejdrive se naucim dalsich 20 stranek nez se budu ptat.

O par stranek je to definovane pomoci odvozeni fci.

CRF - existuje odvozeni.
ORF - CRF ale totalni.
PRF - ORF ale jeji odvozeni je pouze pomoci operatoru primitivni rekurze a substituce, ktere jsou definovane tak, ze zachovavaji totalitu.
Zakládající člen klubu Ortodoxních Matfyzáků :-D

Jsem LAMER ale neumim se ani podepsat ]:-)
Odpovědět

Zpět na „TIN064 Vyčíslitelnost I“