Formleg mál og reiknanleiki

Dćmi 10

1. Dćmi 5.16 á bls. 195 í kennslubók.

2. Dćmi 5.21 á bls. 196 í kennslubók.

3. Sýniđ C (C++ eđa Java) forrit sem skrifar sjálf sig út.

4. Dćmi 6.5 á bls. 221 í kennslubók.

5. [Próf '96] Lát L_2-5 = {<M> | M er Turing-vél og 2 <= |L(M)| <= 5 }.
   1. Sýniđ ađ HALT_TM <_m L_2-5, ţar sem HALT_TM er Stöđvunarvandamáliđ fyrir Turing-vélar.
   2. Sýniđ ađ E_TM <_m L_2-5, ţar sem E_TM er Tómleikavandamáliđ fyrir Turing-vélar.
   3. Flokkiđ L_2-5 sem rakiđ (recursive), rekjanlegt (enumerable), and-rekjanlegt (co-enumerable) eđa hvorki rekjanlegt né and-rekjanlegt.

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