Next: About this document
Up: No Title
Previous: No Title
Tehtävää 1 lukuunottamatta kaikkien seuraavien tehtävien
ratkaisussa saa käyttää hyväksi Churchin-Turingin teesiä,
jonka mukaan mikä tahansa intuitiivisesti ``mekaaninen''
laskurutiini (algoritmi) voidaan toteuttaa myös Turingin
koneella. Tunnetuiksi saa olettaa myös Kleenen
kvanttorikarakterisoinnin luokalle RE (luentojen Lause 1.1)
sekä luokkien RE ja REC Laskennan teoria -monisteen luvussa 6
esitellyt perusominaisuudet.
-
Laadi Turingin kone, joka tunnistaa aakkoston
parillisen pituisten palindromien muodostaman
kielen . (Merkintä
tarkoittaa merkkijonoa w takaperin kirjoitettuna,
so. jos , niin .)
Esitä koneen tilannejonot sen käsitellessä syötteitä
0110 ja 1011.
-
Todista seuraavat aritmeettisen hierarkian kieliluokkien ominaisuudet.
- .
- Kaikilla : jos ( ), niin
( ).
-
Todista oikeaksi aritmeettisen hierarkian kieliluokkien
kvanttorikarakterisointi (luentojen Lemma 1.4):
kieli , jos ja vain jos
on olemassa kieli siten, että kaikilla :
missä
-
Todista, että aritmeettisen hierarkian luokilla ,
, on seuraavat sulkeumaominaisuudet (luentojen
Lemmat 1.5 ja 1.7).
- Jos , niin ,
.
- Jos , , niin .
- Jos ja , niin .
-
Tutustu Laskennan teoria -monisteen Lauseen 6.11 ja/tai Lauseen 6.12
todistukseen (monisteen ss. 88-92) ja osoita vastaavaa tekniikkaa
käyttäen, että kieli
ei ole rekursiivinen.
-
Määritä, millä aritmeettisen hierarkian tasolla (enintään) sijaitsevat
seuraavat joukot:
-
-
-
Huom.:
Luennoijan virkamatkan takia kurssilla ei ole luentoa tiistaina 2.2.
Pekka Orponen
Fri Jan 21 01:55:34 EET 2000