plonk.tex

\documentclass[a4paper]{article}
\usepackage[utf8x]{inputenc}
\usepackage{ucs}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{multicol}

\usepackage[a4paper]{geometry}
\geometry{top=0.2in, bottom=0.2in, left=0.2in, right=0.2in} 

\pagestyle{empty}

\begin{document}
\begin{multicols}{2}

\subsection*{Kodiranje Turingovega stroja}
Imamo nek Turingov stroj: \[T=\langle Q,\Sigma,\Gamma,\delta,q_1,B_1,q_f \rangle \]
Posamezen ukaz programa $\delta$ je: \[ \delta(q_i,a_j)=\langle q_k, a_l, S_m \rangle \]
Ukaz zakodiramo kot: \[ K=0^i 1 0^j 1 0^k 1 0^l 1 0^m \]
Ko zakodiramo vse ukaze, dobimo kode $K_1, K_2, \dots, K_r$,\\ iz katerih sestavimo kodo Turingovega stroja:
	\[ \langle T \rangle = 111 K_1 11 K_2 11 \dots 11 K_r 111\]

\subsection*{Prevedbe -- seznam jezikov}
\begin{itemize}
\item $L_d = \lbrace w_i \ | \ w_i \not\in L(M_i) \rbrace \ \ \not\in TJ $ 
\item $L_{\overline{d}} = \lbrace w \ | \ w_i \in L(M_i) \rbrace \ \ \in TJ $ 
\item $L_u = \lbrace \langle M,w \rangle \ | \ w \in L(M) \rbrace \ \ \in TJ $ 
\item $L_{\overline{u}} = \lbrace \langle M,w \rangle \ | \ w \not\in L(M) \rbrace \ \ \not\in TJ $ 
\item $L_h = \lbrace \langle M \rangle \ | \ M \ \text{se ustavi za vse vhode} \rbrace \ \ \not\in TJ $ 
\item $L_e = \lbrace \langle M \rangle \ | \ L(M) = \emptyset \rbrace \ \ \not\in TJ $ 
\item $L_{ne} = \lbrace \langle M \rangle \ | \ L(M) \neq \emptyset \rbrace \ \ \in TJ $ 
\item $L_{eq} = \lbrace \langle M_1,M_2 \rangle \ | \ L(M_1) = L(M_2) \rbrace \ \ \not\in TJ $ 
\item $L_{|eq|} = \lbrace \langle M_1,M_2 \rangle \ | \ |L(M_1)| = |L(M_2)| \rbrace \ \ \not\in TJ $ 
\item $L_{ \overline{ |eq|}} = \lbrace \langle M_1,M_2 \rangle \ | \ |L(M_1)| \neq |L(M_2)| \rbrace \ \ \not\in TJ $ 
\end{itemize}

\subsection*{Riceov izrek}

Če je jezikovna lastnost Turingovega stroja trivialna, potem je Turingov stroj rekurziven.\\
\ \\
\textbf{Primer:}\\
$M_e$ je Turingov stroj ki opisuje jezik $L_e = \lbrace \langle M \rangle | L(M) \neq \emptyset \rbrace $
Temu turingovemu stroju pripada jezikovna lastnost $ L(M) \neq \emptyset $. 
Jezikovna lastnost je trivialna če velja za bodisi vse Turingove stroje, ali pa za nobenega.\\
\ \\
Za dokaz z Riceovim izrekom poiščemo en Turingov stroj, ki vsebuje lastnost $L(M)$ in drugega ki je ne:
\begin{itemize}
\item $L(M_1) = \Sigma^*$ -- ta stroj ima lastnost $ L(M) \neq \emptyset $
\item $L(M_2) = \emptyset $ -- ta stroj nima lastnosti $ L(M) \neq \emptyset $
\end{itemize}
Če taka Turingova stroja obstajata, vidimo, da lastnost \textbf{ni} trivialna, torej $M_e$ ni rekurziven.

\subsection*{Rekurzivne funkcije}
\begin{enumerate}

\item $Z(n)=0$
\item $N(n)=n+1$
\item $\pi^k_i (n_1, n_2, \dots, n_k)=n_i$
\item Kompozicija: \\
	$ f(x_1, \dots, x_n) = $ \\ $ g(h_1(x_1, \dots, x_n), h_2(x_1,\dots, x_n), \dots, h_m(x_1, \dots, x_n)) $ 
\item Primitivna rekurzija: \\
	$ f(x_1, \dots, x_n, 0) = g(x_1, x_2, \dots, x_n) $ \\
	$ f(x_1, \dots, x_n, y+1) = h(x_1, \dots, x_n, y, f(x_1, \dots, x_n, y)) $
\item Minimizacija: \\
	$ f(x_1, x_2, \dots, x_n) = \mu_y (g(x_1, x_2, \dots, x_n, y)) = z $ \\
	Pri tem je $z$ najmanjše število, za katerega velja $g(x_1, x_2, \dots, x_n, z) = 0$. Če tak $z$ ne obstaja je funkcija $f$ tam nedefinirana.
\end{enumerate}
\textbf{Funkcije ki smo jih definirali na vajah:}
\begin{itemize}
\item $P(n) = n-1$
\item $\ominus(a,b) = a-b$
\item $\oplus(a,b) = a+b$
\item $\otimes(a,b) = a*b$
\item $\oslash(a,b) = a/b$
\item $\text{mod}(a,b) = ab$
\item $\text{divides}(a,b) = \begin{cases} 1 \ ; & a \mod b = 0 \\ 0 \ ; & a \mod b \neq 0 \end{cases}$
\item $\text{IF}(a,b,c) = \begin{cases} b \ ; & a \neq 0 \\ c\ ; & a = 0 \end{cases}$
\item $\text{sqrt}(a) = \sqrt{a} $

\textbf{Primer:} $ \oplus (a,b) $
\begin{align*}
 \oplus(x,0) &= \pi^1_1(x)\\
\oplus(x,y+1) &= N(\pi^3_3(x,y,\oplus(x,y))
\end{align*}

\end{itemize}

\end{multicols}
\end{document}