# Ćwiczenia 8.04.2021

$\newcommand{\N}{\mathbb{N}}$

### Zadanie 87.

Udowodnij, że jeśli f jest niemalejącą całkowitą funkcją rekurencyjną, to zbiór f(N) jej wartości jest rekurencyjny. Czy pozostaje to prawdą bez założenia o całkowitości f?

* $\varphi(\N )$ skończony - trywialne

* $\varphi(\N )$ nieskończony

$\forall n \exists m>n: \varphi(m) > \varphi(n)$

$\psi(n)$:
for i = 1,2,..:
* if $\varphi(i) = n$: return 1
* if $\varphi(i) > n$: return 0

Czy pozostaje to prawdą bez założenia o całkowitości f?

$f(n) = \varphi_n(n)$
$\varphi(\N ) = K$

$f(n) = n$ oraz $dom(f) = K$

### Zadanie 88.
Udowodnij, że każdy niepusty zbiór rekurencyjnie przeliczalny jest postaci $\phi(\N)$ dla pewnej całkowitej funkcji rekurencyjnej $\phi$.

Niech $f: \N \rightarrow \N \times \N$
$f(1) = \langle 1,1 \rangle$
$f(2) = \langle 2,1 \rangle$
$f(3) = \langle 1,2 \rangle$
$f(4) = \langle 2,2 \rangle$
$\ldots$

wczytaj n
licznik = 0
for i=1 to inf:
    x,y = f(i)
    uruchom \phi_A(x) na y sekund
    jeśli \phi_A(x) się zakończył i zwrócił 1: licznik += 1
    jeśli \phi_A(x) się zakończył i zwrócił 0: pomiń
    jeśli \phi_A(x) nie zakończył działania (nie zwrócił wyniku): pomiń
    jeśli licznik == n: zwróć x

$\phi$ jest rekurencyjna, bo istnieje program ją implementujacy

$\phi$ jest całkowita – skoro zbiór A jest niepusty, to $\phi$ zatrzymuje się dla dowolnego $n \in N$, ponieważ jeśli $\phi_A(x)$ zatrzymał się po $y$ sekundach to zatrzyma się również po $y+1$ sekundach (jest tak ponieważ takich par jest nieskończenie wiele) aż licznik osiągnie $n$

$\forall n \in \N : \phi(n) \in A$ ponieważ $\phi$ zwraca jedynie elementy ze zbioru $A$, jeśli dany element nie należy do $A$ to wykonywana jest instrukcja pomiń (tak samo w przypadku gdy się nie zakończyły obliczenia/program się pętli)

$\forall x \in A \ \exists n \in \N : \phi(n)=x$ ponieważ dla danego $x \in A$ istnieje skończona liczba kroków $y$, dla której $\phi_A(x)$ kończy działanie i zwraca $1$. Para $\langle x, y \rangle$ jest równa $f(i)$ dla jakiegoś $i \in \N$, gdzie $f$ podaną wyżej bijekcją. Zauważmy, że licznik zwiększa się o co najwyżej raz w każdym przebiegu pętli i zwraca wynik wtedy kiedy licznik osiągnie wartość $n$, czyli $\phi(n) = x$

### Zadanie 89
Niech $\phi$ będzie funkcją z zadania 88. Definiujemy $\psi$:
$n$ <- input
$Z$ <- $\{\}$
for $s = 1, 2, ...$
&nbsp;&nbsp;&nbsp;&nbsp;$Z$ <- $Z \cup \{\phi(s)\}$
&nbsp;&nbsp;&nbsp;&nbsp;if $|Z| = n$
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return $\phi(s)$

### Zadanie 90

## 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ą?

### f - całkowita
#### 1. Jeśli A jest rekurencyjny, to $f(A)$ też - NIE

Kontrprzykład
$A = \mathbb{N}$
$f(\mathbb{N}) = K$
wiemy, że takie f istnieje, bo wtedy istniałoby $\varphi_k$
Zadanie 89

#### 2. Jeśli A jest rekurencyjny, to $f^{-1}(A)$ też - TAK

$f^{-1}(A) = \{n : f(n) \in A\}$

Napiszemy program rozstrzygający $f(A)$.

$\phi_f(n)$

1. Policz $f(n)$
2. Uruchom $\varphi_A(f(n))$ i zwróć wynik

#### 3. Jeśli A jest r.e., to $f(A) = B$ też - TAK

Napiszemy program semi-rozstrzygający $f(A) = B$.

$\varphi_f(n)$ zatrzymuje się dla $x \in B$, zapętla się jeżeli $x \notin B$

$\phi_f(n)$
1. Uruchom $\varphi_A(a)$ dla każdego $a \in \mathbb{N}$ jednocześnie - komentarz: po tym punkcie w punkcie 2 zostaną użyte tylko $a \in A$
2. Jeżeli $\varphi_A$ się zatrzyma policz $f(a)$
2.1 Jeżeli $f(a) = n$ zwróć 1
2.2 w.p.p zapętl się

#### 4. Jeśli A jest r.e., to $f^{-1}(A)$ też - TAK
$f^{-1}(A) = \{n : f(n) \in A\}$

Napiszemy program semi-rozstrzygający A.

$\phi_f(n)$

1. Policz $f(n)$
2. Uruchom $\varphi_A(f(n))$ i zwróć wynik

### f - częściowa
#### 1. Jeśli A jest rekurencyjny, to $f(A)$ też - NIE
Każda funkcja całkowita jest częściowa - więc ten sam kontrprzykład
#### 2. Jeśli A jest rekurencyjny, to $f^{-1}(A)$ też - NIE
$f^{-1}(A) = \{n : f(n) \in A\}$

Z zadania 87:
$f(n) = n$ oraz $dom(f) = K$

#### 3. Jeśli A jest r.e., to $f(A)$ też - TAK
Napiszemy program semi-rozstrzygający A.

$\psi_f(n)$
#### 4. Jeśli A jest r.e., to $f^{-1}(A)$ też - TAK
$f^{-1}(A) = \{n : f(n) \in A\}$

Napiszemy program semi-rozstrzygający A.

### Zadanie 95.
### Niech $A,B⊆\mathbb{N}$ . Mówimy, że $A \le_{rek} B$ jeśli istnieje całkowita funkcja rekurencyjna $f$ (zwana redukcją), taka że $f(x)∈B$ wtedy i tylko wtedy gdy $x∈A$. Pokaż, że dla każdych dwóch zbiorów $A,B⊆\mathbb{N}$ istnieje ich najmniejsze ograniczenie górne w sensie $\le_{rek}$,to znaczy taki zbiór $C$, że:
### 1)$A\le_{rek}C$ i $B\le_{rek}C$,
### 2) jeśli $D$ jest taki, że $A\le_{rek}D$ i $B\le_{rek}D$ to $C\le_{rek}D$.

## 1
> $C= \{2a | a∈A\} \cup \{2b+1 | b∈B\}$
> $f_{A→C}(n) = 2n$
> $f_{B→C}(n) = 2n+1$
> $A\le_{rek}C$ i $B\le_{rek}C$

## 2
> Mamy $D$, że $A\le_{rek}D$ i $B\le_{rek}D$.
> Znamy więc $f_{A→D}$ i $f_{B→D}$
> Pokażemy, że $C\le_{rek}D$
> Weźmy dowolne $x \in C$
>
> #### i) $x = 2k , k\in \mathbb{N}$
>> $x \in C \Longleftrightarrow k \in A \Longleftrightarrow f_{A→D}(k) \in D \Longleftrightarrow f_{A→D}(x/2) \in D$
>
>#### ii) $x = 2k +1 , k\in \mathbb{N}$
>> $x \in C \Longleftrightarrow k \in B \Longleftrightarrow f_{B→D}(k) \in D \Longleftrightarrow f_{B→D}((x-1)/2) \in D$
>
> więc
> $$f_{C→D}(n) = \begin{cases}
> f_{A→D}(n/2), & \text{if $n$ is even} \\
> f_{B→D}((n-1)/2) & \text{if $n$ is odd}
> \end{cases}$$
> więc $C\le_{rek}D$