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.