Osoita, että jos ,
,
niin myös
,
.
(Tämä aputulos, relativoidussa muodossaan, oli keskeisellä
sijalla luentojen Lauseen 1.11 (ii) todistuksessa. Tuloksen
oikeellisuus on melko helppo todeta tapauksessa
,
mutta tapaus
vaatii mutkikkaamman ns.
pyyhkäisysimuloinnin (engl. dovetailing), jossa ensin
simuloidaan haluttua laskentaa tietty määrä askelia yhdellä
syötteellä, ja askellaskurin tultua täyteen siirrytään toiseen
syötteeseen.)
kuuluu luokkaan , mutta ei luokkaan
.
Päättele tästä, että aritmeettinen hierarkia on ääretön,
so. että kaikilla
on
(luentojen Lause 1.6 (ii)),
ja siis erityisesti mikään
-täydellinen kieli
ei voi kuulua luokkaan
, kun
.
joukossa määritelty relaatio
on
osittainjärjestys, jonka minimialkio on .
Totea, tehtävän 3 tulokseen nojaten, että asteiden joukossa
määritelty ns. hyppyoperaatio (engl. jump operation)
on hyvin määritelty ja tuottaa jokaiselle
asteelle asteen
, jolla
(so.
, mutta ei
).
Mikä on aste
?
Huom.: Luennoijan virkamatkan takia kurssilla ei ole luentoa tiistaina 2.2.