Teoria informacji/TI Ćwiczenia 14

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenia

Ćwiczenie 1 [Nieobliczalność ]

Liczbę rzeczywistą

nazwiemy obliczalną (rekurencyjną), jeśli istnieje algorytm (maszyna Turinga), który dla danej liczby oblicza -tą cyfrę w rozwinięciu binarnym liczby .

Liczbę nazwiemy rekurencyjnie aproksymowalną, jeśli jest granicą obliczalnego ciągu liczb wymiernych, tzn. istnieje funkcja obliczalna , taka że

Dowiedź, że każda liczba rekurencyjna jest też rekurencyjnie aproksymowalna.
Dowiedź, że istnieją liczby rzeczywiste , które nie są rekurencyjnie aproksymowalne.
Dowiedź, że liczby wymierne, algebraiczne, a także liczby i są rekurencyjne.
Dowiedź, że stała Chaitina jest rekurencyjnie aproksymowalna (niezależnie od wyboru maszyny uniwersalnej).
Dowiedź, że stała Chaitina nie jest rekurencyjna.



Definicja [Test]

Funkcję nazwiemy testem, jeśli dla każdych

Zauważmy, że dla każdego istnieje co najwyżej skończenie wiele takich, że . Intuicyjnie, funkcja wskazuje, jak bardzo słowo "odbiega od normy". Warunek stwierdza, że takich ciągów nie może być zbyt wiele (w przeciwnym razie stanowiłyby normę).

Ćwiczenie 2 [Uniwersalny test Martina-Lofa]

Niech będzie przeliczalną rodziną testów.

Dowiedź, że funkcja określona wzorem

jest testem.

Interesujący jest zwłaszcza przypadek, kiedy funkcja sama należy do rodziny .

Test nazwiemy efektywnym, jeśli istnieje maszyna Turinga , która przyjmując na wejściu parę

 jeśli  zatrzymuje się i daje odpowiedź TAK;
 jesli  daje odpowiedź NIE, lub się zapętla. 

Innymi słowy, zbiór jest rekurencyjnie przeliczalny, chociaż funkcja nie musi być rekurencyjna.

Zauważmy, że rodzina wszystkich testów efektywnych jest przeliczalnie wiele. (Dlaczego ?)


Dowiedź, że jest testem efektywnym.