Teoria informacji/TI Ćwiczenia 14: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Niwinski (dyskusja | edycje)
214 edycji
Niwinski (dyskusja | edycje)
214 edycji
Linia 34: Linia 34:
}}
}}


{{cwiczenie|2 [Uniwersalny test Martina-Lofa]|Ćwiczenie 2|
{{definicja|[Test]|test|Funkcję <math>\delta : \{ 0,1 \}^* \to N </math> nazwiemy '''testem''', jesli dla każdych <math>m,n, </math>  
{{definicja|[Test]|test|Funkcję <math>\delta : \{ 0,1 \}^* \to N </math> nazwiemy '''testem''', jesli dla każdych <math>m,n, </math>  


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


{{cwiczenie|2 [Uniwersalny test Martina-Lofa]|Ćwiczenie 2|
: Niech <math>Z = \{ \delta_0 , \delta_1 , \ldots  \} </math> będzie przeliczalną rodziną testów. Dowiedź, że funkcja  określona wzorem  
: Niech <math>Z = \{ \delta_0 , \delta_1 , \ldots  \} </math> będzie przeliczalną rodziną testów. Dowiedź, że funkcja  określona wzorem  
<center><math>
<center><math>
Linia 56: Linia 56:
  jesli <math> \delta (w) < m, </math> daje odpowiedź '''NIE''', lub się zapętla.  
  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. Zauważmy, że testów efektywnych jest przeliczalnie wiele. (Dlaczego ?)
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.  
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible-content" style="display:none">
Zauważmy, że rodzina <math>E </math> wszystkich testów efektywnych jest przeliczalnie wiele. (Dlaczego ?)
Maszyna <math>M_{\delta }</math> jednoznacznie wyznacza test <math>\delta </math> (jak ?)
 
 
:Dowiedź, że <math>\delta^E </math> jest testem efektywnym.
<div class="mw-collapsible mw-made=collapsible mw-collapsed">  
<div class="mw-collapsible mw-made=collapsible mw-collapsed">  
<div class="mw-collapsible-content" style="display:none">
<div class="mw-collapsible-content" style="display:none">
<math> \delta (w) = \max \{ m: \delta (w) \geq m \}.</math>
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>
a maszyn Turinga jest oczywiście przeliczalnie wiele.
</div>
</div>
</div>
}}
</div>
Zauważmy, że dla każdego <math>w,</math> istnieje co najwyżej skończenie wiele <math>m, </math> takich że <math> \delta (w) \geq m </math>.
 
: Dowiedź, ż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>.
 
: Dowiedź, że następujaca funkcja jest testem:
<center><math>
\delta^U (w) = \max \{
</math></center>

Wersja z 22:09, 25 sie 2006

Ćwiczenia

Ćwiczenie 1 [Nieobliczalność Ω]

{{{3}}}

Definicja [Test]

Funkcję δ:{0,1}*→N nazwiemy testem, jesli dla każdych m,n,
|{w∈{0,1}n:δ(w)≥m}|2n≤12m

Zauważmy, że dla każdego w, istnieje co najwyżej skończenie wiele m, takich że δ(w)≥m. Intuicyjnie, funkcja δ(w) wskazuje, jak bardzo słowo w ,,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}}}
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Teoria_informacji/TI_Ćwiczenia_14&oldid=28224”