Pogovor:Izračunljiva funkcija

Iz MaFiRaWiki

Ali je prav izračunljiva delna funckija ali delno izračunljiva funkcija? Funkcija, ki je izračunljiva, a ponekod ni definirana, je še vedno povsem izračunljiva na svojem definicijskem območju. Torej je to delna funkcija, ki je izračunljiva, skratka izračunljiva delna funkcija. AndrejBauer 11:20, 2 oktober 2006 (CEST)

To je stvar dogovora. Odvisno je, kako interpretiramo pojem izračunljiva funkcija.

  • Prva možnnost: izračunljivo pomeni delno izračunljivo. V tem primeru je najbrž boljša prva možnost.
  • Če pa privzamemo, da izračunljivo pomeni totalno izračunljivo (izračunljivo z algoritmom, ki se vedno ustavi), potem je boljša druga možnost.TomazPisanski 12:07, 2 oktober 2006 (CEST)

Še tole, mislim, da je Kleene leta 1952 vpeljal pojem "paritally recursive function" z enakim pomenom kot delno izračunljiva funkcija. To bi pomenilo, da je funkcija, ki je sicer v Platonovih nebesih povsod definirana le deloma izračunljiva.TomazPisanski 12:14, 2 oktober 2006 (CEST)

Algoritmi

Ni res, da mora algoritem nujno računati popolnoma izračunljivo funkcijo, lahko je tudi delna funkcija. Edina zahteva je, da algoritem deluje pravilno in da se ustavi povsod na definicijskem območju funkcije. AndrejBauer 11:29, 2 oktober 2006 (CEST)

Spet imamo opravka z dvema šolama, ki uporabljata isti izraz (algoritem) z različnima pomenoma. Jaz že dobrih 20 let učim, da se mora algoritem vsakič ustaviti. (Tako so nas učili na Penn State). Tako ga ločimo od računske procedure. Nujno pa je potrebno jasno ločevati med obema pojmoma, sicer so lahko težave.TomazPisanski 12:08, 2 oktober 2006 (CEST)

Kako pa ti praviš "algoritmom", ki se vedno ustavijo?TomazPisanski 12:14, 2 oktober 2006 (CEST)

Osebna orodja