Formleg mál og reiknanleiki

Dćmi 9

1. Sýniđ ađ staflavél međ tvo stafla er jafngild Turing-vél.

2. [Próf '96] Fyrir hverja af eftirfarandi fullyrđingum, segiđ hvort ţćr séu sannar eđa ósannar og gefiđ stutta réttlćtingu.
   1. Sérhvert hlutmengi reglulegs máls er reglulegt.
   2. Sérhvert endanlegt mengi er samhengisóháđ.
   3. Fyrir gefna Turing-vél M, máliđ L(M) er rakiđ (recursive) ţţaa M stöđvast á öllu inntaki.
   4. Sérhvert óendanlegt rekjanlegt mál (recursively enumerable) inniheldur óendanlegt reglulegt hlutmengi.
   5. Ţađ er óleysanlegt ađ ákvarđa (undecidable) hvort ađ gefin Turing-vél M komi einhvern tímann aftur í upphafsstöđu sína á einhverju inntaki.

3. [Haustpróf '97] Segiđ (og sýniđ) hvort eftirfarandi mál séu rakin (recursive), rekjanleg (enumerable), and-rekjanleg (co-enumerable), eđa hvorki rekjanleg né and-rekjanleg.
   1. L = { <M, k> | M samţykkir a.m.k. eitt inntak af lengd k}
   2. L = { <M, k> | M samţykkir a.m.k. eitt inntak af lengd k og M hafnar a.m.k. einu inntaki af lengd k}
   3. L = { <M, w> | M notar mest 23 hólf á bandinu á inntaki w}

4. Dćmi 5.7 á bls. 195 í kennslubók.

5. Dćmi 5.17 á bls. 195 í kennslubók.

Skiliđ ţessum dćmum fyrir hádegi mánudaginn 2. nóvember.