Chyba ve skriptach, Vycislitelnost

[Necroman]

Objevil jsem zrejme chybu ve "strojilovych skriptech" na Vycislitelnost. Ve vete o rekurzi je podminka "pro kazdou CRF f muzeme najit bod a ..." spravne ma byt f ORF - je to tak uvedeno i v materialech Petra Kucery. Pokud by treba f byla CRF definovana jen v bode 1 a f(1) = 2, a BUNO φ1 != φ2, potom by veta
neplatila. Tak si to kdyztak upravte...

Kdyz se nad tim clovek zamysli, nabizi se otazka, existuje takova ORF funkce, pro kterou plati, ze pro kazde x je φx != φf(x)? to je funkce, ktera pro kazde x vrati kod jine funkce nez to, co pocita x? ... takova funkce ale asi nemuze existovat, protoze jeden z algoritmicky neresitelnych problemu je problem zda funkce φx a φy pocitaji to same...

[cunav5am]

Jestli jsem tu otázku pochopil dobře, tak taková funkce f nemůže existovat. Věta o rekurzi právě najde bod a, kde budou rovny: .
Asi ale stejně píšu pozdě

[Necroman]

Resil jse tuto vec s Ant. Kucerou a bylo mi receno, ze dana veta plati i pro CRF, pokud pripustime, ze φf(a) = φa nemusi davat pro zadne a smysl. Pokud ma tento vyraz davat smysl alespon pro jedno a, tak je potreba ORF.

[cunav5am]

Ano, totiž pokud najdeme bod takový, že , tak tu větu splňuje.