Fórum studentů MFF UK

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.

[quote="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?[/quote]

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

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?

Nazdar, tak jak to je?

Pise se v poznamkach ze [latex]f:\mathbb{N}^{k} \rightarrow \mathbb{N}[/latex] a definicni obor [latex]dom(f) \in \mathbb{N}[/latex]. 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 [latex]\mathbb{N}^{k}[/latex] 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?