581336 Laskennan teoria (kevät 2006) Harjoitus 1 (23.-27.1.)
1. Kuvaa luennolla esitetyn kielen f 0n1ng tunnistavan Turingin koneen laskenta (ts. luettele ti- lanteet alkutilanteesta pysähtymiseen) syötteillä
(a) 0011 ja (b) 001011.
2. Esitä Turingin kone, joka tunnistaa kielen
f wwRj w 2 f a; b gg;
missä wRon merkkijono w takaperin.
3. Turingin kone voidaan vaihtoehtoisesti määritellä siten, että siinä ei ole hyväksyvien tilojen joukkoa F Q, vaan erilliset hyväksyvä lopputila qyes 2 Q ja hylkäävä lopputila qno 2 Q.
Vaadimme, että tiloista qyes ja qno ei ole määritelty siirtymää millään merkillä, mutta kaikista muista tiloista on siirtymä kaikilla nauha-aakkoston merkeillä. Kone hyväksyy, jos se päätyy tilaan qyes, ja hylkää, jos se päätyy tilaan qno.
Osoita, että mille tahansa luennolla esitetyn määritelmän mukaiselle Turingin koneelle M voi- daan esittää tämän vaihtoehtoisen määritelmän mukainen kone M0, joka hyväksyy tasan ne syötteet, jotka M hyväksyy, ja hylkää tasan ne syötteet, jotka M hylkää.
4. Mikä on L(M) Turingin koneella
M = (f q0; q1; q2; q3g; f 0; 1 g; f 0; 1; B g; ; q0; B; f q3g) kun
(a) (q0; 1) = (q1; B; R), (q1; 0) = (q0; B; R) ja (q1; B) = (q3; B; R);
(b) (q0; 0) = (q0; 1; R), (q0; 1) = (q1; 0; R), (q1; 1) = (q1; 0; R) ja (q1; B) = (q3; B; R); sekä (c) (q0; 0) = (q1; 1; R), (q1; 1) = (q2; 0; L), (q2; 1) = (q0; 1; R) ja (q1; B) = (q3; B; R).
Jos siirtymää ei ole merkitty, se on määrittelemätön.
