Teoria informacji/TI Ćwiczenia 14: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 56: | Linia 56: | ||
Test <math> \delta</math> nazwiemy '''efektywnym''', jeśli istnieje maszyna Turinga <math>M_{\delta }</math>, która przyjmując na wejściu parę <math>\langle w,m \rangle, </math> | Test <math> \delta</math> nazwiemy '''efektywnym''', jeśli istnieje maszyna Turinga <math>M_{\delta }</math>, która przyjmując na wejściu parę <math>\langle w,m \rangle, </math> | ||
jeśli <math> \delta (w) \geq m, </math> zatrzymuje się i daje odpowiedź '''TAK'''; | |||
jesli <math> \delta (w) < m, </math> daje odpowiedź '''NIE''', lub się zapętla. | |||
Innymi słowy, zbiór <math> \{ \langle w,m \rangle : \delta (w) \geq m \} </math> jest rekurencyjnie przeliczalny, chociaż funkcja <math>\delta </math> nie musi być rekurencyjna. | Innymi słowy, zbiór <math> \{ \langle w,m \rangle : \delta (w) \geq m \} </math> jest rekurencyjnie przeliczalny, chociaż funkcja <math>\delta </math> nie musi być rekurencyjna. | ||
Zauważmy, że rodzina <math>E </math> wszystkich testów efektywnych jest przeliczalnie wiele. (Dlaczego ?) | Zauważmy, że rodzina <math>E </math> wszystkich testów efektywnych jest przeliczalnie wiele. (Dlaczego ?) | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | |||
<div class="mw-collapsible-content" style="display:none"> | |||
Maszyna <math>M_{\delta }</math> jednoznacznie wyznacza test <math>\delta ,</math> | |||
<center><math> \delta (w) = \max \{ m: \delta (w) \geq m \},</math></center> | |||
a maszyn Turinga jest oczywiście przeliczalnie wiele. | |||
</div> | |||
</div> | |||
:Dowiedź, że <math>\delta^E </math> jest testem efektywnym. | :Dowiedź, że <math>\delta^E </math> jest testem efektywnym. | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | |||
<div class="mw-collapsible-content" style="display:none"> | |||
Pokaż najpierw, że istnieje rekurencyjna numeracja wszystkich testów, tzn. maszyna Turinga <math> T </math>, taka że zbiór jej wartości <math>\{ T(x) : x \in \{ 0,1 \}^* \}</math> jest dokładnie zbiorem kodów <math>\{ \langle M_{\delta } \rangle : \delta \mbox{ jest testem } \}</math>. | |||
</div> | |||
</div> | |||
}} | }} | ||
Wersja z 22:29, 25 sie 2006
Ćwiczenia
Ćwiczenie 1 [Nieobliczalność ]
{{{3}}}
Definicja [Test]
Funkcję nazwiemy testem, jesli 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]
{{{3}}}
