\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[TS1,T2A]{fontenc}
\usepackage[russian]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}

\hoffset=-3cm
\textwidth=18cm
\voffset=-3cm
\textheight=26cm

\date{2010-03-30}
\title{Лекции по матлогу}
\author{Зайцев Вадим}

\begin{document}
\maketitle

\subsubsection{Предложение (ПВТ - правильно вычислимые на Тьюринге)}
\begin{enumerate}
	\item $O(x) = 0$
	\item $S(x) = x +1$
	\item $J_n^m(x_1,...,x_m) = x_m$
\end{enumerate}

\subsubsection{Предложение}
$\left. \begin{array}{l}
	f(x_1,...,x_m) \\ g_1(x_1,...,x_m) \\ g_n(x_1, ..., x_m)
  \end{array} \right\}$ ПВТ\\
	$h(x_1,...,x_m) = f(g_1(x_1,...,x_m), ..., g_n(x_1,...,x_m))$ - ПВТ.\\
	$F, G_1, ..., G_n$ - ПВТ $f, g_1,...,g_n$\\
	$0q_11^{x_1+1}01^{x_2+1}0...1^{x_m+1}0 \overset{K_m}{ \Rrightarrow } 0q_2q^{x_1+1}$...\\
	В общем:\\
	$ (K_m \cdot \text{Б}_m^+\cdot G_1 \cdot \text{Б}_m^- \cdot \text{Ц} \cdot \text{Б}^+)$\\
	$ (K_m \cdot \text{Б}_m^+\cdot G_2 \cdot \text{Б}_m^- \cdot \text{Ц} \cdot \text{Б}^+)$\\
	$\vdots$\\
	$ (K_m \cdot \text{Б}_m^+\cdot G_{n-1} \cdot \text{Б}_m^- \cdot \text{Ц} \cdot \text{Б}^+)$\\
	$G_n \cdot \text{Б}_{n-1}^- \cdot F$
	
\subsubsection{Предложение}
	$\left. \begin{array}{l} g(x_1,...,x_n) \\ h(x_1,...,x_n, y, z) \end{array} \right\{$ ПВТ
	
\subsubsection{Предложение}
	Если $g(x_1,...,x_n)$ - ПВТ, то $f(x_1, ..., x_n) = \mu y[g(x_1,...,x_n)=0]$ - ПВТ.
	
\subsubsection{Теорема}
	Мно-ва ЧРФ $\subseteq$ ПВТ.
	
\subsubsection{Теорема}
	$\forall n \in \mathbb{N} \quad \exists! n = p_1^{\alpha_1}p_2^{\alpha_2} \ldots p_k^{\alpha_k}$, где $p_i$ - $i$-е простое число.
	
\subsubsection{Определение}
	Пусть $(a_1,...,a_n) \in \{ 0, 1\}^n$, тогда $\gamma(a_1, ..., a_n) = 2\cdot p_2^{a_1} \cdot ... \cdot p_n^{a_n} \quad p_2=3, \, p_3=5 \ldots $
	
\subsubsection{Предложение}
	$A \leftrightharpoons \{ \gamma(s) \mid s \in \{0,1\}^n \}$, тогда $X_A$ - ПРФ. $X_A(x) = \begin{cases}1, \quad x\in A \\ 0, \quad x \not\in A \end{cases}$.
	
\subsubsection{Предложение}
	Следующие ф-ии являются ПРФ:
	\begin{enumerate}
		\item $L(n,a) = \begin{cases} \gamma(a\alpha), \quad n=\gamma(\alpha),\,a= \in \{0,1\} \\ 0, \quad \text{в пр. случае} \end{cases}$
		\item $R(n,a) = \begin{cases} \gamma(\alpha a), \quad n=\gamma(\alpha),\, a\in \{0,1\} \\ 0, \quad \text{в пр. случае} \end{cases}$
		\item $L(n) = \begin{cases} 2, \quad n=2=\gamma(\varnothing) \\ \gamma(\alpha), \quad n=\gamma(a\alpha) \\ 0, \quad \text{в пр. случае} \end{cases}$
		\item $R(n) = \begin{cases} 2, \quad n=2=\gamma(\varnothing) \\ \gamma(\alpha), \quad n=\gamma(\alpha a) \\ 0, \quad \text{в пр. случае} \end{cases}$
		\item $xy = \begin{cases} \gamma(\alpha \beta), \quad x=\gamma(\alpha),\, y = \gamma(\beta) \\ 0, \quad \text{в пр. случае} \end{cases}$
		
		\item $M(x) = \begin{cases} a+1, \quad x=\gamma(a\alpha)\\0, \text{в пр. случае} \end{cases}$
		\item $K(x) = \begin{cases} a+1, \quad x=\gamma(\alpha a)\\0, \text{в пр. случае} \end{cases}$
	\end{enumerate}

\subsubsection{Определение}
	$\alpha q_i j \beta$ - машинное слово, $\alpha, \beta \in \{0,1\}^k, \quad j \in \{0,1\}$.\\
	$\gamma(\alpha q_i j \beta) = 2^2 \cdot 3^i \cdot 5^j \cdot 7^{\gamma(\alpha)} \cdot 11^{\gamma(\beta)}$

\subsubsection{Предложение}
	$B \leftrightharpoons \{ \gamma(s) \mid s - \text{машинне слово} \}, \quad X_B$ - ПРФ.
	
\subsubsection{Замечание}
	$A \cap B = \varnothing$.
	
\subsubsection{некоторая важная теорема}

\subsubsection{Следствие}
	ВТ $\subseteq$ ЧРФ
	
\subsubsection{Следствие (основаня теорема о вычислимых функциях)}
	ЧРФ = ВТ = ПВТ
	
\subsubsection{Тезис Ч...}
	Каждая интуитивно-вычислимая функция является ЧРФ и каждая ЧРФ является интуитивно-вычислимой (т.е. существует некоторая формализованная запись фукции).
	

\end{document}
