Věta o parametrizaci

• $m$ - počet argumentů, které chceme zafixovat
• $n$ - zbylý počet argumentů
• přesouvání proměnných odzadu: jinak bychom mohli ty proměnné přemazat

• $\varphi^{(j)}: \mathbb{N} \rarr \mathbb{P}^{(j)}$ - standardní numerace
• $\Phi$ - univerzální funkce
• $\psi$ - nestandardní numerace
• $\Phi_{\psi} = \varphi_{r(x)}(y) = \psi_x (y)$

Programovací systém/jazyk

• není vyžadováno u zkoušky

Vyčíslitelné množiny

Rekurzivní množiny

• příklad:
  • $A = \emptyset \subseteq \mathbb{N}$, $f(x)=2$
  • $A = {1,3,5, … }$, $f(x) = x mod 2$
• $\chi_A$ = charakteristická funkce (tot. vyč. pouze když $A$ je rekurzivní)

begin
    if f(x1, ..., xk) = 1 then x1 := 1 else x:= 0
end

Vlastnosti

• strana 5, char. fce pro A:

begin
    if x1 = a1 ∨ x1 = a2 ∨ ... ∨ x1 = an then x1 := 1
                                         else x1 := 0
end

• Pro doplněk stačí prohodit vracející hodnoty

• strana 6:
• $\chi_{\overline{A}}$

begin
    if 𝜒A(x1, ..., xk) = 1 then x1 := 0 else x1 := 1
end

• $\chi_{A \cup B}$

begin
    if 𝜒A(x1, ..., xk) = 1 ∨ 𝜒B(x1, ..., xk) = 1 then x1 := 0 else x1 := 1
end

Rekurzivně spočetná

• $f(x) = x \Rarr range(f) = \mathbb{N}$ je rek. spoč.
• $f(x) = x \mod 3 \Rarr range(f) = { 0, 1, 2 }$ je rek. spoč.
• r.e. = recursively enumerable