8299308536

Zadanie 116. (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 C⁴ 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 c₄

takie że (ci, C2, C3, c₄) € N.

Na wykładzie mówiliśmy o nierozstrzygalności dziesiątego problemu Hilberta (nazwijmy go H10). Problem ten polega na tym, aby dla danego układu równań diofantycznych, to znaczy równań między wielomianami wielu zmiennych o współczynnikach całkowitych, odpowiedzieć, czy układ ten ma rozwiązanie w liczbach naturalnych.

Zadanie 117. Niech HlOprim będzie problemem ustalenia, dla danego układu równań diofantycznych, czy układ ten ma rozwiązanie w liczbach całkowitych, a (od -1 do 6 punktów). Pokaż, że H10prim<_refcH10. b (od -1 do 6 punktów) Pokaż, że HKKr-efcHlOprim.

Zadanie 118. Niech HlObis będzie problemem H10 w którym ograniczamy się jedynie do równań diofantycznych, w którym każdy wielomian jest stopnia co najwyżej dwa. Czy HlObis pozostaje nierozstrzygalny?

Wskazówka (do tego zadania i poprzedniego): W jednym z zadań możesz zechcieć odwołać się do faktu, że każda liczba naturalna daje się przedstawić jako suma czterech kwadratów liczb naturalnych.

13 Nierozstrzygalność. Różne inne zadania.

Zadanie 119. Udowodnij, że problem z dziesiątego problemu Hilberta (H10), to znaczy problem czy dany układ równań diofantycznych (czyli równań między wielomianami wielu zmiennych o współczynnikach całkowitych) ma rozwiązanie w liczbach całkowitych, pozostaje niezrozstrzygalny jeśli, zamiast o rozwiązanie w liczbach całkowitych, będziemy pytać o rozwiązanie w liczbach całkowitych nieparzystych. Wolno oczywiście skorzystać z nierozstrzygalności H10.

Zadanie 120. Czy istnieje algorytm rozstrzygający, dla danej gramatyki bezkontekstowej G, czy istnieje słowo w, takie że ww^Rw 6 L(G)?

Zadanie 121. Dla danych funkcji f,g,h : {0,1,... ,p — 1} —► {0, l,...,p— 1} i danego nieskończonego ciągu liczb naturalnych (ai, 02, <13,...), niech P/,s,h(a 1, <12, • • •) będzie ciągiem liczb naturalnych, którego i-ty element jest równy /(aj_i) +_p g(a,i) +_p h(ai+1), gdzie +_p oznacza dodawanie modulo p (przyjmujemy, że ao = 0). Udowodnij, że problem:

Dane funkcje /, g i h oraz skończone ciągi (b\, b2, ■ ■ ■, bk) i (ci,C2,... ,Cfc). Czy istnieje liczba iteracji n taka, że FJ_{g h}(bi,b2,..., 6k, 0,0,0,...) = (ci, C2,..., c*,, 0,0,0,...)? jest nierozstrzygalny.

Zadanie 122. Jak każdy pamięta, deterministyczny automat ze stosem, to urządzenie zadane przez skończony zbiór instrukcji w formacie: jeśli widzisz na taśmie wejściowej a, jesteś

14