# Ćwiczenia z JFiZO 15.04.2020 #### Zadania 82, 83, 85, 86, 87, 88, 89, 91, 95, 96. Oznaczenia: $\newcommand{\N}{\mathbb{N}} \N,$ $\newcommand{\reduces}{\leq_{rek}} \reduces,$ $\newcommand{\complement}[1]{\overline{#1}} \complement{A}$ :::info **Zadanie 82**. Rozszerz definicję zbioru rekurencyjnego tak, aby można było rozważać rekurencyjne zbiory par liczb naturalnych i udowodnij, że jeśli zbiór $A \subseteq \N^2$ jest rekurencyjny, to zbiór $\{n : \exists m [n, m] \in A\}$, czyli rzut A na pierwszą oś, jest zbiorem rekurencyjnie przeliczalnym. **Autor**: twoja stara ::: *Rozwiązanie:* Rozszerzmy definicję zbioru rekurencyjnego na $\mathbb{N}\times\mathbb{N}$: $\forall_{a,b \in A}\ \varphi_A(\langle a,b \rangle) = 1 \iff \langle a,b \rangle \in A \ \land \ \varphi_A(\langle a,b \rangle) = 0 \iff \langle a,b \rangle \notin A$ Napiszmy program $\phi_B$ w MUJP dla zbioru $B = \{n : \exists m [n, m] \in A\}$. ``` wczytaj n for i=1 to inf uruchom A(n, i) jeżeli zwróci 1 -> zwróć 1 ``` Jeżeli dla $n \in N$ istnieje takie $m$, że $[n,m] \in A$, to $\phi_B$ zwróci 1. Zatem zgodnie z definicją zbioru rekurencyjnie przeliczalnego, B jest r.e. :::info **Zadanie 83**. Pokaż, że każdy zbiór rekurencyjnie przeliczalny jest rzutem pewnego zbioru rekurencyjnego, to znaczy jeśli $B$ jest r.e. to istnieje taki rekurencyjny $A \subseteq \N^2$ rekurencyjny, że $B = \{n : \exists m [n, m] \in A\}$. **Autor**: pijana ::: *Rozwiązanie:* Robimy program dla $A$ w MUJP: $\varphi_A:$ ``` Program: Wczytaj n, m Odpalamy φ_B(n) na m sekund if sie zakonczy, zwróc 1 else zwróc 0 ``` :::info **Zadanie 85**. Pokaż, że $\{n : |Dom(\phi_n)| \geq 7\}$ jest rekurencyjnie przeliczalny. **Autor**: anonn ::: Przechodzimy przekątniowo i zliczamy, ile razy progrzechodzimy przekątniowo i zliczamy, ile razy progamy się zakończy ``` Program: Wczytaj n for i=1 to inf licznik = 0 for j=1 to i odpal φ_n(j) na i sekund jeżeli się zakończy: licznik += 1 jeżeli licznik >= 7: zwróć 1 ``` :::info **Zadanie 86**. Niech $A, B, C, D$ będą zbiorami rekurencyjnie przeliczalnymi, takimi że każda liczba naturalna należy do dokładnie dwóch z nich. Udowodnij, że w takim razie wszystkie cztery zbiory są rekurencyjne. **Autor**: $anon^{n}$ ::: Weźmy $\varphi_A, \varphi_B, \varphi_C, \varphi_D$ ``` program φ_A': wczytaj n od k=1 to inf: uruchom jednocześnie φ_A, φ_B, φ_C, φ_D na k sekund (argument: n) jeśli φ_A(n) = 1: return 1 jeśli dwa programy inne od φ_A zwróciły 1: return 0 ``` :::info **Zadanie 87**. Udowodnij, że jeśli $\phi$ jest niemalejącą całkowitą funkcją rekurencyjną, to zbiór $\phi(\N)$ jej wartości jest rekurencyjny. Czy pozostaje to prawdą bez założenia o całkowitości $\phi$? **Autor**: anon 5 ::: * Jeżeli $\varphi$ jest (od pewnego momentu) funkcją stałą, to rozwiązanie jest natychmiastowe - funkcja stała tworzy zbiór skończony * wpp robimy program rozstrzygający przynależność do $\varphi(\N)$: ``` wczytaj n od m=1 to inf if φ(m) = n return 1 if φ(m) > n return 0 ``` Jeżeli $\varphi$ nie jest całkowite, (w szczególności $\varphi$ też nie jest rekurencyjne) to jej zbiór wartości $\varphi(\mathbb{N})$ __nie jest__ rekurencyjny - weźmy $\phi$ takie, że $\phi(n) = n$ jeśli $\phi_{n}(n) \in \mathbb{N}$. Wtedy $\varphi[\N] = K$. :::info **Zadanie 88**. Udowodnij, że każdy niepusty zbiór rekurencyjnie przeliczalny jest postaci $\phi(\mathbb{N})$ dla pewnej całkowitej funkcji rekurencyjnej $\phi$. **Autor**: Piotrum ![](https://i.imgur.com/XazW41i.png) ![](https://i.imgur.com/JKPpFS9.png) ::: Zdefiniujmy bijękcję $f$ z $\N$ na $\N \times \N$. $f(1) = \langle1,1\rangle,$ $f(2) = \langle2,1\rangle, f(3) = \langle2,2\rangle, f(4) = \langle1,2\rangle,$ $f(5) = \langle3,1\rangle, f(6) = \langle3,2\rangle, f(7) = \langle3,3\rangle, f(8) = \langle1,3\rangle, f(9) = \langle2,3\rangle, ...$ Napiszmy program obliczający $\phi$ dla dowolnego $A$ będącego zbiorem r.e. i dowolnego $n \in \N$: ``` wczytaj n licznik = 0 for i=1 to inf: x,y = f(i) uruchom φ_A(x) na y sekund jeśli φ_A(x) się zakończył i zwrócił 1: licznik += 1 jeśli licznik == n: zwróć x ``` Podany program spełnia wszystkie wymagania, by $\phi(\N)$ był równoważny $A$: * $\forall n \in \N : \phi(n) \in A$ Bo program zwróci jedynie wartość, dla której $\phi_A$ zwraca wynik. * $\forall a \in A : \exists n \in \N : \phi(n) = a$ Jeżeli $a \in A$, to musi istnieć para $a, y \in \N$, że $\phi_A(a)$ włączone na $y$ sekund zwróci $1$. Wiemy, że istnieje $i \in \N$, takie że $f(i) = \langle a, y \rangle$. Ponieważ w naszym programie licznik zwiększa się co najwyżej raz z każdą iteracją pętli, to wiemy, że istnieje $n \leq i$, dla którego licznik zwiększy się przy $i$-tej iteracji do wartości $n$. Wtedy $\phi(n) = a$. <!-- ![](https://i.imgur.com/iB3mhDZ.png) --> :::info **Zadanie 89**. Udowodnij, że każdy nieskończony zbiór rekurencyjnie przeliczalny jest postaci $\phi(\mathbb{N})$ dla pewnej całkowitej, różnowartościowej funkcji rekurencyjnej $\phi$. **Autor**: Michaliszyn ::: dunno :::info **Zadanie 91**. (Długie, więc za 2 punkty) Załóżmy, że $f$ jest funkcją rekurencyjną, całkowitą. Które z poniższych implikacji są prawdziwe? * jeśli $A$ jest rekurencyjny, to $f(A)$ też; * jeśli $A$ jest rekurencyjny, to $f^{-1}(A)$ też; * jeśli $A$ jest r.e., to $f(A)$ też; * jeśli $A$ jest r.e., to $f^{-1}(A)$ też. Co zmieni się, jeśli założymy, że $f$ jest funkcją częściową? **Autor**: Polesiuk ::: dunno :::info **Zadanie 95**. Niech $A, B \subseteq \N$. Mówimy, że $A \reduces B$ jeśli istnieje całkowita funkcja rekurencyjna $f$ (zwana redukcją), taka że $f(x) \in B$ wtedy i tylko wtedy gdy $x \in A$. Pokaż, że dla każdych dwóch zbiorów $A, B \subseteq \N$ istnieje ich najmniejsze ograniczenie górne w sensie $\reduces$, to znaczy taki zbiór $C$, że: i) $A \reduces C$ oraz $B \reduces C$, ii) jeśli $D$ jest taki, że $A \reduces D$ oraz $B \reduces D$, to $C \reduces D$. **Autor**: $\sqrt{anon}$ ::: Weźmy $C \subseteq \mathbb{N}$ 1) Pokażemy, że $A \reduces C$ tworzymy $f_{A \rightarrow C}(n) = 2n$ Podobnie dla $B \reduces C$ tworzymy $f_{B \rightarrow C}(n) = 2n+1$ Zatem takie funkcja istnieją $\square$ 2) Weźmy takie $D$, zbudujemy redukcje $C \reduces D$ $$ f_{C \rightarrow D} = \begin{cases} f_{A \rightarrow D}(\frac{n}{2}),\ &2 | n \\ f_{B \rightarrow D}(\frac{n-1}{2}),\ &\mathrm{wpp} \end{cases} $$ :::info **Zadanie 96**. Czy $K \reduces \complement{K}$? Czy $\complement{K} \leq_{rek} K$? **Autor**: $\sum_n^{a}{on}$ ::: Zaczniemy od punktu drugiego: czy $\complement{K} \leq_{rek} K$? Załóżmy, że to prawda, zatem istnieje redukcja $f$ taka, że $n \in \complement{K} \iff f(n) \in K$. ``` program: wczytaj n uruchom i zwróć φ_K(f(n)) ``` Program kończy się, gdy $n$ należy do $\complement{K}$, ale zbiór $\complement{K}$ nie jest r.e. Wniosek: $\complement{K} \nleq_{rek} K$. --- Wracamy do punktu pierwszego: czy $K \reduces \complement{K}$? Załóżmy, że to prawda, zatem istnieje redukcja $f$ taka, że $n \in K \iff f(n) \in \complement{K}$. Weźmy dowolny element $n \in \complement{K}$. Zauważmy, że $n \notin K$, zatem $f(n) \notin \complement{K}$, zatem $f(n) \in K$. Otrzymaliśmy redukcję $n \in \complement{K} \iff f(n) \in K$ -- udowodniliśmy jednak przed chwilą, że taka redukcja prowadzi do sprzeczności. Wniosek: $K \nleq_{rek} \complement{K}$.