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 L2-5 = {<M> | M er Turing-vél og 2 <= |L(M)| <= 5 }.
    1. Sýniđ ađ HALTTM <m L2-5, ţar sem HALTTM er Stöđvunarvandamáliđ fyrir Turing-vélar.
    2. Sýniđ ađ ETM <m L2-5, ţar sem ETM er Tómleikavandamáliđ fyrir Turing-vélar.
    3. Flokkiđ L2-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.


hh (hja) hi.is, 3. nóvember, 1998.