ScannedImage 9 2

Kolokwium trwa 90 minut. Rozwiązanie każdego zadania proszę oddać na oddzielnej kartce.

1.    (3 x 5 punktów) Zdecyduj o każdym z języków czy jest rekurencyjny czy nic. Odpowiedz uzasadnij. Można korzystać z pierwszego twierdzenia Rice’a.

(a)    L = {(M): {M) ma 2010 liter }

(b)    L = {(M): L(M) jest skończony }

(c)    L = {(M): L(M) = £*},

2.    (10 punktów) Skonstruuj maszynę Turinga, która sprawdza czy słowo wejściowe nad alfabetem binarnym jest palindromem czyli takim słowem x, że x = reverse(x). Maszyna ma akceptować palindromy a nieakceptować pozostałych słów.

3.    (3 x 5 punktów) Dla każdego z trzech poniższych języków zdecyduj jaki jest jego status. Czy jest on rekurencyjny. Czy jest rekurencyjnie przeliczalny, ale nie rekurencyjny. Albo czy nie jest rekurencyjnie przeliczalny. Odpowiedz uzasadnij.

(a)    L = {(M)w : maszyna M zatrzymuje się po więcej niż 2010 krokach na słowie w).

(b)    L = {(M)w : maszyna M zatrzymuje się po mniej niż 2010 krokach na słowie w}.

(c)    L = {(M) : maszyna M nie zatrzyma się na żadnym słowie w}.