"korteerzhide" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

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 Kolmekohaliste korteerzhide jaoks c3(x,y,x) = c(x,c(y,z)) I-kohaliste jaoks analoogne rekursiivne lahendus. Cantori f.n ja selle pöördf.-n on lihtrekursiivsed. Registermasina käsud saab Cantori numbrite järgi kodeerida.. Seega saab programmi koodiks naturaalarv, millest saab leida prorammi pikkuse, iga käsu eraldi, jne. F.-nide ühakohalised esindajad: Kui superpositsioonioperaatori suhtes kinnine f.-nide klass sisaldab korteezhide kodeerimise ja dekodeerimise f.-ne cm,c1m, cmm, siis selle klassi iga m-kohalise f