Osoita, että kaikilla on
ja
. (Ohje: Todistus induktiolla k:n
suhteen. Induktioaskelta varten tarkastele mielivaltaisen polynomisessa
ajassa toimivan
-koneen M tunnistamaa kieltä A, ja sen
rinnalla kieltä
Totea, että kieli kuuluu luokkaan
,
ja että väite
seuraa tästä pienillä lisätarkasteluilla.
Huom.: Vastaavalla argumentilla voidaan osoittaa, että
Savitchin lauseen seurauksena on
kaikilla .)
Huomautus: Myös kieltä QBF rajoittamalla saadaan luonnollisia
-täydellisiä kieliä:
(Todistus saadaan tässä tapauksessa yksinkertaisesti soveltamalla Cookin lauseen todistusta epädeterminististen koneiden sijaan alternoiviin Turingin koneisiin.)
Kurssin ensimmäinen välikoe on ke 1.3. klo 8-11. Kokeen alue on kurssin alusta alternoiviin Turingin koneisiin asti.
KÄÄNNÄ
Todista tätä tietoa ja luentojen Lausetta 5.5 (uniformi
diagonalisointilause) käyttäen seuraavat väitteet kaikilla :
Lisätieto: Samaa tekniikkaa käyttäen voidaan itse asiassa
todistaa seuraava vahvempikin tulos.
Jos ja
ovat rekursiivisia kieliä, joilla
,
niin on olemassa rekursiiviset kielet
, joilla
Kurssin ensimmäinen välikoe on ke 1.3. klo 8-11. Kokeen alue on kurssin alusta alternoiviin Turingin koneisiin asti.