1109144841
Zadanie 96. Tak samo jak w poprzednim zadaniu, tylko odpowiedni fragment brzmi: ”Maszyna działa tak, że na początku głowica ustawiona jest w stanie qo na pierwszym symbolu słowa wejściowego. Gdy w stanie q głowica widzi symbol a € E, to przechodzi do stanu q', zamiast a wpisuje a1, gdzie S(q,a) = (q',a'). Następnie jest przesuwana o jedną komórkę w prawo, chyba że a było blankiem, wtedy wiadomo że przeskanowano cały dotychczas używany fragment taśmy i głowica zawraca, to znaczy po wykonaniu każdej kolejnej instrukcji przesuwana jest o jedną komórkę w lewo, aż w końcu ponownie znajdzie się nad pierwszym symbolem na taśmie. Wtedy ponownie zawraca w prawo itd.”
9 Nierozstrzygalność. Kanoniczne zadania.
Zadanie 97. Powtórz, podany na wykładzie, dowód nierozstrzygalności Problemu Odpo-wiedniości Posta.
Zadanie 98. Dla gramatyki bezkontekstowej G niech Lq oznacza generowany przez nią język. Skorzystaj z nierozstrzygalności problemu odpowiedniości Posta aby pokazać, że zbiór tych par gramatyk G, H dla których zachodzi Lq fi Lu ^ 0 nie jest rekurencyjny. Czy jest on rekurencyjnie przeliczalny?
Zadanie 99. (za 2 punkty) Udowodnij, że nie istnieje algorytm rozstrzygający, dla danej gramatyki bezkontekstowej G i alfabetu A, czy A* — L(G)
Zadanie 100. Czy istnieje algorytm rozstrzygający, dla danych dwóch gramatyk bezkon-tekstowych G i H, czy L(G) = L(H)?
Zadanie 101. Udowodnij nierozstrzygalność problemu sprawdzenia dla danego procesu Thu-ego II i słowa w czy zbiór Aw = {u : w <5 i/} jest skończony.
Wskazówka (nieobowiązkowa, jak wszystkie wskazówki): Rozważ maszyny Turinga z dodanym gdzieś na taśmie licznikiem, który jest zwiększany o jeden przy każdym ruchu wykonywanym przez maszynę. Naśladuj dowód nierozstrzygalności problemu słów.
Zadanie 102. (za 2 punkty) Rozpatrzmy skończony zbiór par słów P i binarną relację —* na słowach zdefiniowaną jak następuje: w —>p v wtedy i tylko wtedy gdy istnieje para (a, b) e P taka, że w = ax i v = xb gdzie x jest pewnym słowem. Niech —*p będzie przechodnim domknięciem —*p (to znaczy najmniejszą relacją przechodnią zawierającą —*p).
Czy problem: dane P, x, y, czy x —>p y ? jest rozstrzygalny?
Zadanie 103. (trudne, za 2 punkty) Funkcję / : N —* N nazywamy funkcją Conway’a jeśli istnieją liczby naturalne p, a\, 61,02,62,..., ap, bp takie, że dla każdego n jeśli n = k mod p to f{n) = na/c/bk- Pokaż, że nie ma algorytmu, który dla danych p,a\, 61,02,62,..., ap, bp odpowiedziałby, czy dla definiowanej przez te współczynniki funkcji Conway’a istnieje m takie, że fm(2) = 1 gdzie fm oznacza funkcję / złożoną m razy ze sobą.
Zadanie 104. (za 2 punkty) Udowodnij nierozstrzygalność następującego problemu: dany jest skończony zbiór kolorów C, zawierający co najmniej kolory: czerwony i biały, oraz zbiór N C C4 czwórek kolorów, uznanych za nieestetyczne. Mamy nieskończenie wiele kwadratowych kafelków każdego koloru o boku długości 1. Czy istnieje kwadrat (o całkowitych wymiarach i boku nie mniejszym niż 2), który można wypełnić kafelkami w taki sposób by w lewym dolnym i w lewym górnym narożniku znalazł się czerwony kafelek, pozostałe kafelki dolnego i górnego brzegu były białe, oraz by w całym kwadracie nie pojawiła się nieestetyczna sekwencja kafelków, tj. cztery sąsiadujące kafelki:
|
Cl |
C2 |
|
C3 |
C4 |
takie że (ci, C2, C3, C4) € N.
11
Wyszukiwarka
Podobne podstrony:
strona (4) 13 Dla tranzystora T2 tak samo jak wyżej, zmieniam tylko wartości napięcia UCE2 oraz prą
ANSI C 5 1 ELEMENTARZ Program wygląda prawie tak samo jak poprzednio, przy czym teraz zmienne fahr
skanuj0023 (70) Wymiary podobne jak poprzednio, a mianowicie długość około 60 mm, wymiary górnej pła
17 08prPP Zadanie 17. (2 pkt) W przewodzie pokarmowym człowieka działają enzymy trawienne, na przykł
Zadaniem BIOBEZPIECZEŃSTWA ferm jest podjęcie takich działań które mają na celu niedopuszczenie
chemiafilmowy6 Zadanie *i. W pracowni chemicznej c iilor otrzymuje się, działając kwasem solnym na
chemiametale 6 Zadanie k. W pracowni chemicznej chlor otrzymuje się, działając kwasem solnym na mang
Obraz9 Zadanie 26. W szkicu sytuacyjnym właściwym dla działań straży pożarnych na miejscu pożaru za
chemiafilmowy6 Zadanie *4. W pracowni chemicznej chlor otrzymuje się, działając kwasem solnym na ma
Zadanie 18. Przeprowadzono doświadczenie, w którym badano działanie pewnego odczynnika na dwa wodne
Zadanie 18. Przeprowadzono doświadczenie, w którym badano działanie pewnego odczynnika na dwa wodne
więcej podobnych podstron