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