| dct.abstract |
Laskettavuusteoria eli rekursioteoria tutkii idealisoidun tietokoneen laskentakyvyn rajoja. Teorian perusyksikköjä ovat laskettavat osittaiset (vrt. totaalit) luonnollisten lukujen funktiot, yksipaikkaisessa tapauksessa \varphi_0,\varphi_1,..., ja niiden määrittelyjoukot W_0, W_1..., eli niin kutsutut rekursiivisesti lueteltavat joukot. Produktiiviset joukot ovat tyyppiesimerkkejä joukoista, jotka eivät ole rekursiivisesti lueteltavia: A ⊆ N on produktiivinen, jos jokin totaali laskettava funktio, A:n produktiivinen funktio, laskee kunkin W_x ⊆ A indeksistä x todistajan sille, että A \neq W_x. Produktiiviset joukot ovat laskettavuusteoriassa tärkeitä erityisesti siksi, että rekursiivisesti lueteltavista joukoista tietyllä tavalla monimutkaisimpia ovat ne, joiden komplementti on produktiivinen. Kanoninen esimerkki tällaisesta joukosta on tärkeän pysähtymisongelman diagonaali K. Laajempaa merkitystä matemaattisessa logiikassa tuo produktiivisuuden yhteys riittävän vahvojen aritmetiikan aksioomasysteemien teoreemojen ja aritmetiikan standardimallin toden teorian Gödel-lukuihin.
Työn tarkoituksena on tutkia produktiivisia joukkoja ja niiden produktiivisia funktioita yleisesti, sekä antaa esimerkkejä. Nähdään mm., että äärettömällä rekursiivisesti lueteltavalla joukolla on kontinuumin verran produktiivisia osajoukkoja, ja että joukolla N on maksimaalinen määrä osituksia produktiivisiin joukkoihin niin äärellisessä kuin äärettömässäkin tapauksessa. Nähdään myös, että jokainen totaali laskettava injektio on produktiivinen funktio, mutta surjektioille sama ei päde, ja että produktiivisen joukon produktiivinen funktio saa aina myös ''turhia'', joukon ulkopuolisia arvoja.
Monista esitettävistä laskettavien funktioiden indekseistä koostuvista produktiivisista joukoista paneudutaan erityisesti potenssijoukon laskettavuusteoreettiseen mukaelmaan, joukkojen A\subsetneq\N laskettaviin potenssijoukkoihin prod(A) = {x∈ N : W_x ⊆ A}. Niiden ympäriltä paljastuu rikas struktuuri. Jos A ⊆ prod(A), sanotaan että A on kasvava, ja jos prod(A) ⊆ A, sanotaan että A on vähenevä. Joukkoa, joka on sekä kasvava että vähenevä, sanotaan (laskettavan potenssijoukko-operaation) kiintopisteeksi. Kuten usein laskettavuusteoriassa, K toimii tässäkin kontekstissa eräänlaisena maamerkkinä. Osoitetaan, että kiintopisteiden joukossa on suppein ja laajin ja laajimman, θ:n, komplementti on rekursiivisesti lueteltava. Nähdään, että kukin A ⊆ θ voidaan kasvattaa suppeimmaksi A:n sisältäväksi kasvavaksi joukoksi prosessilla, jonka pituus on korkeintaan ω askelta. Annetun joukon kasvattaminen vastaavasti väheneväksi (mahdollisesti kiintopisteeksi) on huomattavasti kompleksisempaa ja johtaa määrittelemään sopivia ordinaalinotaatiosysteemejä. Jos A on esimerkiksi aidosti kasvava, niin prod-operaatiota on tätä varten toistettava (seuraajaordinaalien kohdalla; rajaordinaaleissa otetaan yhdiste) ainakin ω_1^{CK} kertaa, missä ω_1^{CK} on pienin ei-rekursiivinen ordinaali, eli Churchin-Kleenen ordinaali. Rekursiivisen aidosti kasvavan lähtöjoukon (esim. ∅) tapauksessa todistetaan yhtäsuuruus. |
fi |
