Mercurial > 13ss.theoinf

comparison notes/tex/ue09_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 844698060e1c
children 15351d87ce76
comparison
equal deleted inserted replaced
36:1098749b5645 37:27fedbbdab6d
31 \begin{frame} 31 \begin{frame}
32 \frametitle{Berechenbarkeit} 32 \frametitle{Berechenbarkeit}
33 \setbeamercovered{dynamic} 33 \setbeamercovered{dynamic}
34 34
35 \begin{definition}[Intuitive Berechenbarkeit] 35 \begin{definition}[Intuitive Berechenbarkeit]
36 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$ 36 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$
37 \begin{itemize} 37 \begin{itemize}
38 \item nach \alert{endlich vielen Schritten} mit Ergebnis $f(n_1, \ldots, n_k)$ hält, falls $f(\ldots)$ definiert ist, 38 \item nach \alert{endlich vielen Schritten} mit Ergebnis $f(n_1, \ldots, n_k)$ hält, falls $f(\ldots)$ definiert ist,
39 \item und \alert{nicht terminiert}, falls $f(\ldots)$ nicht definiert ist. 39 \item und \alert{nicht terminiert}, falls $f(\ldots)$ nicht definiert ist.
40 \end{itemize} 40 \end{itemize}
41 \end{definition} 41 \end{definition}
100 \begin{definition}[Basisfunktionen] 100 \begin{definition}[Basisfunktionen]
101 \alert{Primitiv Rekursiv} sind: 101 \alert{Primitiv Rekursiv} sind:
102 \begin{itemize} 102 \begin{itemize}
103 \item Die konstante Funktion \alert{0} 103 \item Die konstante Funktion \alert{0}
104 \item Die \alert{Nachfolgerfunktion} $s(n) = n + 1$ 104 \item Die \alert{Nachfolgerfunktion} $s(n) = n + 1$
105 \item Die \alert{Projektionsfunktion} $\pi_i^k : \N^k \mapsto \N, i \in [k]$ 105 \item Die \alert{Projektionsfunktion} $\pi_i^k : \N^k \to \N, i \in [k]$
106 \[ \pi_i^k(x_1, \ldots, x_k) = x_i \] 106 \[ \pi_i^k(x_1, \ldots, x_k) = x_i \]
107 \end{itemize} 107 \end{itemize}
108 \end{definition} 108 \end{definition}
109 109
110 \begin{definition}[Komposition] 110 \begin{definition}[Komposition]
119 \begin{block}{Basisfunktionen und Komposition} 119 \begin{block}{Basisfunktionen und Komposition}
120 Schon \alert{PR} sind: 120 Schon \alert{PR} sind:
121 \begin{itemize} 121 \begin{itemize}
122 \item Konstante: $0$ 122 \item Konstante: $0$
123 \item Nachfolger: $s(n) = n + 1$ 123 \item Nachfolger: $s(n) = n + 1$
124 \item Projektion: $\pi_i^k : \N^k \mapsto \N$ 124 \item Projektion: $\pi_i^k : \N^k \to \N$
125 \item Komposition: $f(\bar{x}) = g(h_1(\bar{x}), \ldots, h_k(\bar{x}))$ 125 \item Komposition: $f(\bar{x}) = g(h_1(\bar{x}), \ldots, h_k(\bar{x}))$
126 \end{itemize} 126 \end{itemize}
127 \end{block} 127 \end{block}
128 128
129 \begin{definition}[Primitive Rekursion] 129 \begin{definition}[Primitive Rekursion]