"raalil" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

-ni. x ­ programmi kood P y ­ registrite sisu P täitmisel Kuna instruktsioonid saame Cantori numbritega kodeerida .. proge kood aga on instruktsioonide jada (lõplik korteezh naturaalarvudest), leidub ka sellele Cantori number. Iga registermasinal realiseeritav f.-n on osaliselt rekursiivne f.-n. Osaliselt rekursiivsete funktsioonide hulk langeb kokku Turingi mõttes arvutatavate funktsioonide hulgaga ­ see tähendab, et ainult osaliselt rekursiivsed f.-nid on raalil arvutatavad. Ainult neile on võimalik koostada programm. 27. Cantori funktsioonid. Arvutatava funktsiooni ühekohalised esindajad. Korteez on elementide lõplik järjend. Kohati on vaja täielikku vastavust korteezhide ja naturaalarvude hulga vahel (täielikku järjestust). Cantori f.-n (sellele eksisteerib ka pöördf.-n): c(x,y) = 0.5(x+y)(x+y+1) + x pöördf.-n c1 = l(n) ­ annab esimese argumendi c2 = r(n) ­ annab teise argumendi