1109144858

Zadanie 78. Udowodnij, że zbiór numerów tych programów, które zatrzymują się dla wszystkich argumentów oprócz co najwyżej skończonej liczby, nie jest rekurencyjnie przeliczalny.

Zadanie 79. Udowodnij podane na wykładzie twierdzenie Rice’a.

Zadanie 80. Poniższe zbiory nie są rozstrzygalne:

1.    zbiór numerów tych maszyn Turinga, które obliczają funkcje o dziedzinie różnej od N;

2.    zbiór numerów tych maszyn Turinga, które obliczają funkcje całkowitą i których czas działania jest rosnący względem rozmiaru danych;

3.    zbiór numerów tych maszyn Turinga, których czas działania dla żadnych danych nie jest liczbą pierwszą;

4.    zbiór numerów tych maszyn Turinga, które obliczają funkcje częściowe, których wartościami są wyłącznie liczby pierwsze.

Nierozstrzygalność których z nich daje się udowodnić wprost z twierdzenia Rice’a?

Zadanie 81. Udowodnij nierozstrzygalność zbioru z punktu 2. poprzedniego zadania.

Zadanie 82. Niech i,BCN. Mówimy, że A <_refc B jeśli istnieje całkowita funkcja reku-rencyjna / (zwana redukcją), taka że f{pc) G B wtedy i tylko wtedy gdy x G A. Pokaż, że dla każdych dwóch zbiorów i,BCN istnieje ich najmniejsze ograniczenie górne w sensie <_refc, to znaczy taki zbiór C, że:

i)    A <_refc C i B <_refc C,

ii)    jeśli D jest taki, że A <_refc D i B <_refc D to C <_refc D.

Zadanie 83. (Za 2 punkty) Czy K <_refe K? Czy K <_refc KI

Zadanie 84. Pokaż, że zbiór A = {n : 4>_n zatrzymuje się dla wszystkich danych po czasie mniejszym niż trzykrotna długość danych} nie jest rekurencyjny. Czy można do tego użyć tw. Rice’a?

Zadanie 85. Niech T będzie zbiorem tych par liczb (n, m) dla których 4>_n i (p_m to ta sama funkcja częściowa.

i)    Pokaż, że T nie jest rekurencyjnie przeliczalny.

ii)    Czy dopełnienie zbioru T jest rekurencyjnie przeliczalne?

Zadanie 86. Niech / :NxN-»N będzie pewną ustaloną obliczalną bijekcją. Oznaczmy klasę zbiorów rekurencyjnych jako Eo- Dla danego Ej niech IR = {A C N : N\^4 G Ej}, zaś A G Ej+i, jeśli istnieje B G IR, takie że A = {n G N : 3ra f(n,m) G B}. Jakie jest najmniejsze i dla którego zachodzi L G Ej?

Zadanie 87. Niech A, B będą podzbiorami zbioru liczb naturalnych. Załóżmy, że / jest redukcją świadczącą o tym, że A B. Załóżmy, że / jest „na” (tzn. jej obrazem jest cały zbiór liczb naturalnych). Pokaż, że w takim razie zachodzi również B <_refc A.

Zadanie 88. Podzbiór zbioru liczb naturalnych nazywamy co-r.e. jeśli jego dopełnienie jest rekurencyjnie przeliczalne. Odcinkami początkowymi zbioru liczb naturalnych nazywamy zbiory postaci {1,2, ...n} dla n G N. Oznaczmy przez B zbiór numerów tych programów, których dziedziny są odcinkami początkowymi zbioru liczb naturalnych.

a.    Czy zbiór B jest co-r.e.?

b.    Udowodnij, że istnieje zbiór trójek liczb naturalnych A, który jest co-r.e. i którego rzut na pierwszą oś jest zbiorem B. Uwaga. Wymaga to oczywiście milczącego rozszerzenia definicji zbiorów co-r.e. na zbiory trójek liczb.

9