Teoria informacji/TI Ćwiczenia 13

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenia

Ćwiczenie 1 [Liczby pierwsze]

{{{3}}}


Ćwiczenie 2 [Liczby losowe]

{{{3}}}

Ćwiczenie 3 [Generowanie funkcji]

Przyjmujemy, że parą słów , jest

Przypuśćmy, że zbiór wartości obliczanych przez maszynę Turinga , tzn. , jest zbiorem par, przy czym

(i) ,

(ii) (tzn. jest grafem funkcji częściowej).

Dowiedź, że nie jest możliwe, by dla nieskończenie wielu , zachodziło

gdzie jest funkcją taką, że