Mercurial > 13ss.theoinf

comparison notes/tex/ue10_notes.tex @ 36:1098749b5645

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ue10 notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Tue, 02 Jul 2013 00:59:43 +0200
parents
children 27fedbbdab6d
comparison
equal deleted inserted replaced
35:844698060e1c 36:1098749b5645
1 \input{preamble.tex}
2
3 \title{Übung 10: $\mu$Rekursion, Entscheidbarkeit}
4 \subtitle{Theoretische Informatik Sommersemester 2013}
5 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
6
7 \begin{document}
8
9 \begin{frame}
10 \titlepage
11 \end{frame}
12
13 \begin{frame}
14 \frametitle{LOOP-Programme}
15 \setbeamercovered{dynamic}
16
17 \begin{definition}[LOOP-Programm]
18 Syntax von \alert{LOOP-Programmen}.\\
19 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$.
20 \begin{align*}
21 P &\rightarrow X := X + C \\
22 &\mid X := X - C \\
23 &\mid P; P \\
24 &\mid \mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END} \\
25 &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}}
26 \end{align*}
27 \end{definition}
28
29 \begin{itemize}
30 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0.
31 \item $\mathbf{LOOP}\ x_i \ \mathbf{DO}\ P \ \mathbf{END}$ führt $P$ genau $n$ mal aus, wobei $n$ der Anfangswert von $x_i$ ist. \alert{Zuweisungen an $x_i$ in $P$ ändern die Anzahl der Durchläufe nicht.}
32 \end{itemize}
33 \end{frame}
34
35 \begin{frame}
36 \frametitle{Erweitertes PR-Schema}
37 \setbeamercovered{dynamic}
38
39 \begin{definition}[Erweitertes PR-Schema]
40 Das \alert{erweiterte Schema der primitiven Rekursion} erlaubt
41 \begin{align*}
42 f(0, \bar{x}) &= t_0 \\
43 f(m + 1, \bar{x}) &= t
44 \end{align*}
45 wobei
46 \begin{itemize}
47 \item $t_0$ enthält nur PR-Funktionen und die $x_i$
48 \item $t$ enthält nur \alert{$f(m, \bar{x})$}, PR Funktionen, \alert{$m$} und die $x_i$.
49 \end{itemize}
50 \end{definition}
51
52 \begin{theorem}
53 Das erweiterte Schema der primitiven Rekursion führt nicht aus \alert{PR} heraus.
54 \end{theorem}
55 \end{frame}
56
57 \begin{frame}
58 \frametitle{Beschränkte Operationen}
59 \setbeamercovered{dynamic}
60 \begin{definition}
61 Ein Prädikat $P$ ist \alert{PR}, wenn es eine PR Funktion $\hat{P}$ gibt mit
62 \[\hat{P}(x) = 1 \Longleftrightarrow P(x)\]
63 \end{definition}
64
65 \begin{definition}[Beschränkte Operationen]
66 Ist $P$ PR, dann auch
67 \begin{itemize}
68 \item der \alert{beschränkte max-Operator}
69 \[\max \left\{ x \alert{\leq n} \mid P(x) \right\}, \quad \max \left\{ \emptyset \right\} = 0\]
70 \item der \alert{beschränkte Existenzquantor}
71 \[\exists x \alert{\leq n}. P(x)\]
72 \end{itemize}
73 \end{definition}
74 \end{frame}
75
76 \begin{frame}
77 \frametitle{$\mu$-Rekursion}
78 \setbeamercovered{dynamic}
79
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$:
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}
84
85 \vfill
86
87 \begin{itemize}
88 \item \alert{$^*$}Für alle \alert{$m \leq n$} muss $f$ definiert sein: $f(m, \bar{x}) \neq \perp$
89 \item PR + $\mu$ = $\mu$-Rekursion
90 \item In Pseudocode:
91 \begin{align*}
92 \mu f(\bar{x}) &= find(0, \bar{x}) \\
93 find(n, \bar{x}) &= \mathbf{if}\ f(n, \bar{x}) = 0 \ \mathbf{then}\ n \ \mathbf{else}\ find(n+1, \bar{x})
94 \end{align*}
95 \end{itemize}
96 \end{frame}
97
98 \begin{frame}
99 \frametitle{Übersetzungen}
100 \setbeamercovered{dynamic}
101
102 \begin{center}
103 \begin{tikzpicture}[node distance=2.5cm]
104 \node (WH) {WHILE};
105 \node (GO) [above left of = WH] {GOTO};
106 \node (TM) [above right of = WH] {TM};
107 \node (LO) [below of = WH] {LOOP};
108 \node (PR) [left of = LO] {PR};
109 \node (MR) [left of = WH] {$\mu$R};
110
111 \draw [every edge, ->] (LO) -- (WH);
112 \draw [every edge, ->] (PR) -- (MR);
113 \draw [every edge, tumgreen, <->] (LO) -- (PR);
114 \draw [every edge, tumgreen, <->] (WH) -- (MR);
115 \draw [every edge, <->] (WH) -- (GO);
116 \draw [every edge, ->] (WH) -- (TM);
117 \draw [every edge, ->] (TM) -- (GO);
118 \end{tikzpicture}
119 \end{center}
120
121 \vfill
122
123 LOOP kann in WHILE \alert{übersetzt} werden, WHILE ist also \alert{mindestens so mächtig} wie LOOP (sogar mächtiger).
124 \end{frame}
125
126 \begin{frame}
127 \frametitle{Berechenbarkeit}
128 \setbeamercovered{dynamic}
129
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$
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,
134 \item und \alert{nicht terminiert}, falls $f(\ldots)$ nicht definiert ist.
135 \end{itemize}
136 \end{definition}
137
138 \vfill
139
140 \begin{block}{Churchsche These (nicht beweisbar)}
141 Turing-Maschinen können genau \alert{alle} intuitiv berechenbaren Funktionen berechnen.
142 \end{block}
143 \end{frame}
144
145 \begin{frame}
146 \frametitle{Entscheidbarkeit}
147 \setbeamercovered{dynamic}
148
149 \begin{definition}[Entscheidbarkeit]
150 Eine Menge $A$ heißt \alert{entscheidbar} gdw ihre \alert{charakteristische Funktion}
151 \[ \chi_A(x) := \begin{cases}1 & \text{falls } x \in A \\ 0 & \text{falls } x \not \in A \end{cases} \]
152 berechenbar ist.
153 \end{definition}
154
155 \begin{definition}[Semi-Entscheidbarkeit]
156 Eine Menge $A$ heißt \alert{semi-entscheidbar} gdw
157 \[ \chi'_A(x) := \begin{cases}1 & \text{falls } x \in A \\ \perp & \text{falls } x \not \in A \end{cases} \]
158 berechenbar ist.
159 \end{definition}
160 \end{frame}
161
162 \begin{frame}
163 \frametitle{Reduzierbarkeit}
164 \setbeamercovered{dynamic}
165
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
168 \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\]
169 Wir schreiben dann \alert{$A \leq B$}.
170 \end{definition}
171
172 \vfill
173
174 \structure{Intuition}:
175 \begin{itemize}
176 \item $B$ ist \alert{mindestens so schwer} zu lösen wie $A$
177 \item Ist $A$ unlösbar, dann auch $B$.
178 \item Ist $B$ unlösbar, dann erst recht $A$.
179 \end{itemize}
180 \end{frame}
181
182 \end{document}