8299308533

Zadanie 87. Nie korzystając z tw. Rice’a udowodnij, że zbiór B — {n : Dom((j)_n) i N — Dominu) są nieskończone} nie jest rekurencyjny.

Zadanie 88. Udowodnij, że zbiór B = {n : Dom{(j)_n) i N — Dom(<f>_n) są nieskończone} z poprzedniego zadania nie jest nawet rekurencyjnie przeliczalny.

Zadanie 89. 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 90. Udowodnij podane na wykładzie twierdzenie Rice’a.

Zadanie 91. 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 92. Udowodnij nierozstrzygalność zbioru z punktu 2. poprzedniego zadania.

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

i)    A ^rek C \ B ^rek C,

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

Zadanie 94. Czy K <_refc K? Czy K Krek K?

Zadanie 95. Niech T będzie zbiorem tych par liczb (n, m) dla których <p_n i <j)_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 96 (Hierarchia arytmetyczna). Niech / : N x N —* N będzie pewną ustaloną obliczalną bijekcją. Oznaczmy klasę zbiorów rekurencyjnych jako E_n. Dla danego Ej niech n, = {A C N : N\A 6 Ej}, zaś A € Ej+i, jeśli istnieje B 6 Hj, takie że A — {n € N : 3m f(n,m) e B}.

Niech L będzie zbiorem numerów tych niepustych funkcji rekurencyjnych których dziedzina jest skończona. Niech Jakie jest najmniejsze i dla którego zachodzi L € Ej?

Zadanie 97. Niech A, B będą podzbiorami zbioru liczb naturalnych. Załóżmy, że / jest redukcją świadczącą o tym, że A <_refc 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 <rek A.

Zadanie 98. 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 € N. Oznaczmy przez B zbiór numerów tych programów, których dziedziny są odcinkami początkowymi zbioru liczb naturalnych.

11