# Teoria Obliczeń

[latex math cheatsheet](https://en.wikibooks.org/wiki/LaTeX/Mathematics)

## 1 Wykład

### Symbole

$$\bar{x}=x_1,\dots,x_n$$

### Definicje podstawowe
Def 1. Rekursja Prosta

: Funkcja prowadząca $\mathbb{N}^{n+1} \to \mathbb{N}$ jest rekursją prostą z $h$.

$f: \mathbb{N}^{n+1} \to \mathbb{N}$, $g: \mathbb{N}^{n} \to \mathbb{N}$

$$h(x_1,\dots,x_n,0)=g(x_1,\dots,x_n)$$
$$h(x_1,\dots,x_n,y+1)=f(x_1,\dots,x_n,y,h(x_1,\dots,x_n,y))$$

Def 2. Relacja Regularna

: $R\in\mathbb{N}^{n+1}$ Relacja $R$ jest regularna
$$\forall_{x_1\dots x_n}\exists_y : R(x_1,\dots x_n)$$

Def 3. While

: $f: \mathbb{N}^n \to \mathbb{N}$ jest otrzymana przez $\mu$-rekursję z funkcji
($\mu$ = min)
$$g: \mathbb{N}^n \to \mathbb{N} \iff f(x_1\dots x_n)=\mu(y):(g(x_1\dots x_n,y)=0)$$
jeżeli, $R(x_1\dots x_n,y)=(g(x_1\dots x_n,y)=0)$ jest regularna

Def 4. Iteracja

: $f: \mathbb{N}^2 \to \mathbb{N}$ jest iteracją $g: \mathbb{N} \to \mathbb{N}$ gdy
$$f(x,0)=x$$
$$f(x,y+1)=g(f(x,y))$$

Def 5. Domkniętość na składanie

: Klasa funkcji $\mathscr{K}$ jest domknięta na składanie gdy

$$
f_1: \mathbb{N}^n \to \mathbb{N},
f_2: \mathbb{N}^n \to \mathbb{N},
\dots,
f_k: \mathbb{N}^n \to \mathbb{N},
g: \mathbb{N}^k \to \mathbb{N}
$$ są w klasie $\mathscr{K} \implies h:\mathbb{N}^n \to \mathbb{N} \in \mathscr{K}$
$$
h:(x_1,\dots,x_n) = g(f_1(x_1,\dots,x_n),\dots,f_n(x_1,\dots,x_n))
$$

Def 6. Klasa funkcji prymitywnie rekurencyjnych $\mathsf{PREK}$

:

- zero $O(x)=0 : \mathbb{N} \to \mathbb{N}$

- następnik $S(x)=x+1 :\mathbb{N} \to \mathbb{N}$

- składanie $I_n^k(x_1,\dots,x_n)=x_k :\mathbb{N}^n \to \mathbb{N}$

### Przykłady

Ex. 1. dodawanie $g(x,y)$

: $$g(x,0) = x = I^1_1(x)$$
$$g(x,y+1) = S(g(x,y))$$
$$g(x,y+1) = h(x,y,g(x,y)) = S(I^3_3(x,y,g(x,y))) = S(g(x,y))$$

Ex. 2. mnożenie $m(x,y)$

: $$m(x,0)=0$$
$$m(x,y)=q(m(x,y),x)$$

Ex. 3. odejmowanie $x \dot{-} y$

: $$
x \dot{-} y =
\begin{cases}
x-y& \quad x\leq y \\
0&\quad \text{w.w.p.}\\
&
\end{cases}
$$

$$
x \dot{-} 1 =
\begin{cases}
x-y& \quad x\leq 1\\
0&\quad \text{w.w.p.}\\
&
\end{cases}
$$

$$
0 \dot{-} 1 = 0\\
(y+1) \dot{-} 1 = y
$$

$$
x \dot{-} 0 = x\\
x\dot{-} (y+1) = (x\dot{-}y)\dot{-}1
$$

Ex 4. $\sum$ (suma)

: $$f: \mathbb{N}^n \to \mathbb{N} \in \mathsf{PREK} \text{(z założenia)}$$

$$g(\bar{x},z)=\sum_{x<z}f(\bar{x},y)$$
$$g(\bar{x},0)=0$$
$$g(\bar{x},z+1)=g(\bar(x),z)+f(\bar(x),z)$$

Ex 5. $\prod$ (iloraz)

: $$f: \mathbb{N}^n \to \mathbb{N} \in \mathsf{PREK} \text{(z założenia)}$$

$$h(\bar{x},z)=\prod_{x<z}f(\bar{x},y)$$
$$h(\bar{x},0)=1$$
$$h(\bar{x},z+1)=g(\bar(x),z)\cdot f(\bar(x),z)$$

Def 7. Relacja prymitywnie rekurencyjna

: Relacja $R \in \mathbb{N}^{n+1}$ jest prymiteywnie rekurencyjna gdy $f_R(\bar(x)) \in \mathsf{PREK}$
$$
f_{R}(\bar{X})=\begin{cases}
0& R(\bar{x})\\
1& w.p.p
\end{cases}
$$

Def 8. Relacja Znak

: $$
sg(\bar{X})=\begin{cases}
0& x=0\\
1& x>0
\end{cases}
$$

$$
\bar{sg}(\bar{X})=\begin{cases}
0& x>0\\
1& x=0
\end{cases}
$$

### Operacje Logiczne

Lemat. Relacje $\mathsf{PREK}$ są zamknięte na : $\land,\lor,\neg,\forall,\exists$

: $$
R,S \in \mathsf{PREK}\\
R,S \in \mathbb{N}^n
$$

1. $R(\bar{x})\land S(\bar{x}) \in \mathsf{PREK}$
$$
f_{R\land S}(\bar{x})= f_R(\bar{x})\cdot f_S(\bar{x})
$$

2. $R(\bar{x})\lor S(\bar{x}) \in \mathsf{PREK}$
$$
f_{R\lor S}(\bar{x})= sg(f_R(\bar{x}) + f_S(\bar{x}))
$$
3. $\neg R(\bar{x}) \in \mathsf{PREK}$
$$
f_{\neg R}(\bar{x})= 1 \dot{-} f_R(\bar{x})
$$
4. $\forall R(\bar{x}) \in \mathsf{PREK}$
$$
S(\bar{x},z)= \forall_{y<z}R(\bar{x},y)\\
f_{S}(\bar{x},z)= \prod_{y<z}f_R(\bar{x},y)
$$
5. $\exists R(\bar{x}) \in \mathsf{PREK}$
$$
T(\bar{x},z)= \exists_{y<z}R(\bar{x},y)\\
f_{T}(\bar{x},z)= sg(\sum_{y<z}f_R(\bar{x},y))
$$

Lemat. Relacje: $=,<,\leq,>,\geq \in \mathbb{N^2} $ są $\mathsf{PREK}$

: $$
f(\bar{x},y) = \begin{cases}
1 & x=y\\
0 & w.p.p.
\end{cases}
$$

Def 9. Ograniczony $\mu$ operator

: $$
g(\bar{x},z) = \mu _{y<z} (f(x,y) = 0 ) = \begin{cases}
y & \exists_{y<z}f(\bar{x},y)=0, f(\bar{x},y<z)>0\\
0 & w.p.p.
\end{cases}
$$

Lemat. $\mu$ nie wyprowadza poza $\mathsf{PREK}$

: $$
g(\bar{x},z)=\mu_{y<z}: R(\bar{x},y)
$$

$$
g(\bar{x},y)=\forall_{y^`<y}: \neg R(\bar{x},y^`) \land R(\bar{x},y)
$$

$$
g(\bar{X},y)=\begin{cases}
y& R(\bar{x},y) \land \forall_{y^`<y}: \neg R(\bar{x},y^`) \\
0& w.p.p
\end{cases}
$$

$$
g(\bar{x},yz)=\sum_
{y<z} y + g(\bar{x},y)
$$

####