%
% 02-teoria-vypocitatelnosti.tex
%
% Developed by Ondrej Jombik <nepto@platon.sk>
% Copyright (c) 2006 Platon Group, http://platon.sk/
% Licensed under terms of GNU General Public License.
% All rights reserved.
%
% Changelog:
% 2006-08-17 - created
%

% $Platon: doc/statnica-teoria-prog/02-teoria-vypocitatelnosti.tex,v 1.2 2006-08-17 09:25:30 nepto Exp $

\chapter{Teória vypočítateľnosti}

\section{Primitívna rekurzia} % /*

\begin{defn}[Projekcia]
	$n$-árnu funkciu $f$ nazývame $m$-tá {\it projekcia} na množine $\mathbb{X}$, ak $0 < m \le n$
	a~platí:
	$$
	\forall x_1 ... x_n: \lambda x_1 ... x_n (x_m)
	$$
	Označujeme $I^n_m$, teda $\forall x_1 ... x_n: I^n_m(x_1 ... x_n) = x_m$.
\end{defn}

\begin{defn}[Operácia skladania funkcií]
	Majme $m$-árne (čiastočne) funkcie $g, f_1 ... f_n$. Hovoríme, že (čiastočná) funkcia $g$ vzniká
	{\it operáciou skladania funkcií} ak existuje $n$-árna (čiastočná) funkcia $f$ taká, že platí:
	$$
	g(x_1 ... x_m) = f(f_1(x_1 ... x_m), ..., f_n(x_1 ... x_m))
	$$
	Označujeme $g = \mathcal{S}^{n+1}(f, f_1 ... f_n)$.
\end{defn}

\begin{defn}[Klon]
	Klonom (čiastočných) funkcií nazývame takú množinu (čiastočných) funkcií, ktorá obsahuje všetky
	projekcie a je uzavretá vzhľadom na operáciu skladania (čiastočných) funkcií.
\end{defn}

\begin{defn}[Operácia primitívnej rekurzie]
Majme $n+1$-árnu čiastočnú funkciu~$f$. Ďalej majme $n$-árnu čiastočnú funkciu $h$ a $n+2$-árnu
čiastočnú funkciu $g$. Hovoríme, že čiastočná funkcia~$f$ vzniká z funkcií $g$ a $h$ {\it operáciou
primitívnej rekurzie}, ak platí:
$$
\begin{array}{rcl}
f(0, x_1 ... x_n) & = & h(x_1 ... x_n)\\
f(y+1, x_1 ... x_n) & = & g(y, f(y, x_1 ... x_n), x_1 ... x_n)
\end{array}
$$

Označujeme $f = \mathcal{R}(g, h)$.

\end{defn}

\begin{defn}[Primitívne rekurzívna funkcia]
	Funkciu $f$ nazývame {\it primitívne rekurzívna}, ak vzniká z funkcií
	
	\begin{enumerate}
		\item $0$ (konštnatná nulová funkcia)
		\item $s$ (successor)
		\item $I^n_m$ ($m$-tá projekcia $n$-árnej funkcie)
		\end{enumerate}
	
	konečným počtom týchto operácií:
	
	\begin{enumerate}
		\item operácia skladania funkcií
		\item operácia primitívnej rekurzie
	\end{enumerate}
\end{defn}

% */

\section{Minimalizácia} % /*

\begin{defn}[Operácia minimalizácie]
	
	Majme $n+1$-árnu čiastočnú funkciu~$g$. Ďalej majme $n$-árnu čiastočnú funkciu $f$. Hovoríme, že
	funkcia $f$ vzniká z~funkcie~$g$ {\it operáciou minimalizácie}, ak:
	$$
	\forall x_1 ... x_n: f(x_1 ... x_n) = y \iff \forall z<y: g(z, x_1 ... x_n) > 0 \land g(y, x_1
	... x_n) = 0
	$$
	Označujeme $f = \mathcal{M}(g)$ alebo $f(x_1 ... x_n) = \mu_y(g(y, x_1 ... x_n) = 0)$.
\end{defn}

\begin{defn}[Operácia regulárnej minimalizácie]
	Nech $f = \mathcal{M}(g)$ a nech $f$ a $g$ sú totálne funkcie. Potom hovoríme, že funkcia $f$ vzniká
	z~funkcie $g$ operáciou {\it regulárnej minimalizácie}.
\end{defn}

\begin{defn}[Čiastočne rekurzívna funkcia]
	Čiastočnú funkciu $f$ nazývame {\it čiastočne rekurzívna}, ak vzniká z funkcií
	
	\begin{enumerate}
		\item $0$ (konštnatná nulová funkcia)
		\item $s$ (successor)
		\item $I^n_m$ ($m$-tá projekcia $n$-árnej funkcie)
		\end{enumerate}
	
	konečným počtom týchto operácií:
	
	\begin{enumerate}
		\item operácia skladania funkcií
		\item operácia primitívnej rekurzie
		\item operácia minimalizácie
	\end{enumerate}
\end{defn}

\begin{defn}[Rekurzívna funkcia]
	Funkciu $f$ nazývame {\it rekurzívna}, ak spĺňa všetky podmienky čiastočne rekurzívnej funkcie a
	nie je tvorená operáciou minimalizácie, ale operáciou regulárnej minimalizácie.
\end{defn}

\begin{veta}
	Každá primitívne rekurzívna funkcia je rekurzívna funkcia.
\end{veta}

\begin{veta}
	Každá rekurzívna funkcia je čiastočne rekurzívna funkcia.
\end{veta}

% */

% vim: ts=4 tw=100
% vim600: fdl=0 fdm=marker fdc=0 fmr=/*,*/