Mercurial > 13ss.theoinf

comparison notes/tex/ue10_notes.tex @ 37:27fedbbdab6d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
change mapsto to to arrows
author Markus Kaiser <markus.kaiser@in.tum.de>
date Tue, 02 Jul 2013 14:16:16 +0200
parents 1098749b5645
children 15351d87ce76
comparison
equal deleted inserted replaced
36:1098749b5645 37:27fedbbdab6d
76 \begin{frame} 76 \begin{frame}
77 \frametitle{$\mu$-Rekursion} 77 \frametitle{$\mu$-Rekursion}
78 \setbeamercovered{dynamic} 78 \setbeamercovered{dynamic}
79 79
80 \begin{definition}[$\mu$-Operator] 80 \begin{definition}[$\mu$-Operator]
81 Sei $f: \N^{k+1} \mapsto \N$ eine Funktion.\\Der \alert{$\mu$-Operator} definiert eine neue Funktion $\mu f : \N^k \mapsto \N$: 81 Sei $f: \N^{k+1} \to \N$ eine Funktion.\\Der \alert{$\mu$-Operator} definiert eine neue Funktion $\mu f : \N^k \to \N$:
82 \[(\mu f)(\bar{x}) := \begin{cases} \min \left\{ n \in \N \mid \alert{f (n, \bar{x}) = 0}\right\} & \text{falls } n \text{ existent\alert{$^*$}} \\ \perp & \text{sonst}\end{cases}\] 82 \[(\mu f)(\bar{x}) := \begin{cases} \min \left\{ n \in \N \mid \alert{f (n, \bar{x}) = 0}\right\} & \text{falls } n \text{ existent\alert{$^*$}} \\ \perp & \text{sonst}\end{cases}\]
83 \end{definition} 83 \end{definition}
84 84
85 \vfill 85 \vfill
86 86
126 \begin{frame} 126 \begin{frame}
127 \frametitle{Berechenbarkeit} 127 \frametitle{Berechenbarkeit}
128 \setbeamercovered{dynamic} 128 \setbeamercovered{dynamic}
129 129
130 \begin{definition}[Intuitive Berechenbarkeit] 130 \begin{definition}[Intuitive Berechenbarkeit]
131 Eine Funktion $f : \N^k \mapsto \N$ heißt \alert{intuitiv berechenbar}, wenn es einen Algorithmus gibt, der bei Eingabe $(n_1, \ldots, n_k) \in \N^k$ 131 Eine Funktion $f : \N^k \to \N$ heißt \alert{intuitiv berechenbar}, wenn es einen Algorithmus gibt, der bei Eingabe $(n_1, \ldots, n_k) \in \N^k$
132 \begin{itemize} 132 \begin{itemize}
133 \item nach \alert{endlich vielen Schritten} mit Ergebnis $f(n_1, \ldots, n_k)$ hält, falls $f(\ldots)$ definiert ist, 133 \item nach \alert{endlich vielen Schritten} mit Ergebnis $f(n_1, \ldots, n_k)$ hält, falls $f(\ldots)$ definiert ist,
134 \item und \alert{nicht terminiert}, falls $f(\ldots)$ nicht definiert ist. 134 \item und \alert{nicht terminiert}, falls $f(\ldots)$ nicht definiert ist.
135 \end{itemize} 135 \end{itemize}
136 \end{definition} 136 \end{definition}
162 \begin{frame} 162 \begin{frame}
163 \frametitle{Reduzierbarkeit} 163 \frametitle{Reduzierbarkeit}
164 \setbeamercovered{dynamic} 164 \setbeamercovered{dynamic}
165 165
166 \begin{definition}[Reduzierbarkeit] 166 \begin{definition}[Reduzierbarkeit]
167 Eine Menge $A \subseteq \Sigma^*$ ist \alert{reduzierbar} auf eine Menge $B \subseteq \Gamma^*$ gdw es eine totale und berechenbare Funktion $f:\Sigma^* \mapsto \Gamma^*$ gibt mit 167 Eine Menge $A \subseteq \Sigma^*$ ist \alert{reduzierbar} auf eine Menge $B \subseteq \Gamma^*$ gdw es eine totale und berechenbare Funktion $f:\Sigma^* \to \Gamma^*$ gibt mit
168 \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\] 168 \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\]
169 Wir schreiben dann \alert{$A \leq B$}. 169 Wir schreiben dann \alert{$A \leq B$}.
170 \end{definition} 170 \end{definition}
171 171
172 \vfill 172 \vfill