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...
Chyba ve skriptach, Vycislitelnost
- Necroman
- Supermatfyz(ák|ačka)
- Příspěvky: 459
- Registrován: 20. 1. 2005 19:46
- Typ studia: Informatika Mgr.
- Login do SIS: suchm4am
- Bydliště: Louny / kolej Jednota, Praha
- Kontaktovat uživatele:
Chyba ve skriptach, Vycislitelnost
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
-
- Matfyz(ák|ačka) level I
- Příspěvky: 16
- Registrován: 4. 6. 2007 09:37
- Typ studia: Informatika Mgr.
- Login do SIS: cunav5am
Re: Chyba ve skriptach, Vycislitelnost
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ě
Asi ale stejně píšu pozdě
- Necroman
- Supermatfyz(ák|ačka)
- Příspěvky: 459
- Registrován: 20. 1. 2005 19:46
- Typ studia: Informatika Mgr.
- Login do SIS: suchm4am
- Bydliště: Louny / kolej Jednota, Praha
- Kontaktovat uživatele:
Re: Chyba ve skriptach, Vycislitelnost
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.
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
-
- Matfyz(ák|ačka) level I
- Příspěvky: 16
- Registrován: 4. 6. 2007 09:37
- Typ studia: Informatika Mgr.
- Login do SIS: cunav5am
Re: Chyba ve skriptach, Vycislitelnost
Ano, totiž pokud najdeme bod takový, že , tak tu větu splňuje.