Mercurial > 13ss.theoinf

comparison notes/tex/computation.tex @ 41:5d10471f5585

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
move frame-definitions out of presentations
author Markus Kaiser <markus.kaiser@in.tum.de>
date Thu, 11 Jul 2013 20:42:36 +0200
parents
children c14b92bfa07f
comparison
equal deleted inserted replaced
40:3175d3871752 41:5d10471f5585
1 \defineUnit{tmdefinition}{%
2 \begin{frame}
3 \frametitle{Turingmaschinen}
4 \setbeamercovered{dynamic}
5
6 \begin{definition}[Turingmaschine]
7 Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
8 \begin{itemize}
9 \item endlichen Menge von \alert{Zuständen} $Q$
10 \item endlichen \alert{Eingabealphabet} $\Sigma$
11 \item endlichen \alert{Bandalphabet} $\Gamma$ mit $\Sigma \subset \Gamma$
12 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
13 \item \alert{Startzustand} $q_0 \in Q$
14 \item \alert{Leerzeichen} $\square \in \Gamma \setminus \Sigma$
15 \item Menge von \alert{Endzuständen} $F \subseteq Q$
16 \end{itemize}
17 \end{definition}
18 \end{frame}
19 }
20
21 \defineUnit{tmvisualisierung}{%
22 \begin{frame}
23 \frametitle{Turingmaschinen}
24 \setbeamercovered{dynamic}
25
26 \begin{definition}[Turingmaschine]
27 Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
28 \begin{itemize}
29 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
30 \end{itemize}
31 \end{definition}
32
33 \vfill
34
35 \begin{center}
36 \begin{tikzpicture}
37 % Tape
38 \begin{scope}[start chain, node distance=0]
39 \node[on chain] {\ldots};
40 \node[tape] {$\square$};
41 \node[tape] (l) {$\square$};
42 \node[tape] {$0$};
43 \node[tape] {$1$};
44 \node<1>[tape, active] (a){$0$};
45 \node<2>[tape] (a){$1$};
46 \node<1>[tape] (b){$0$};
47 \node<2>[tape, active] (b){$0$};
48 \node[tape] {$\square$};
49 \node[on chain] {\ldots};
50 \end{scope}
51
52 % Head
53 \node<1> [head,yshift=-4mm] at (a.south) (head) {$q_0$};
54 \node<2> [head,yshift=-4mm] at (b.south) (head) {$q_1$};
55
56 % Machine
57 \node[machine, below=1.5cm of l] (machine) {Programm};
58 \draw[every edge] (machine) .. controls (3.5, -2) .. (head.south);
59
60 % Example-Transition
61 \node[yshift=5mm] at (current bounding box.north) {$\delta(q_0, 0) = (q_1, 1, R)$};
62 \end{tikzpicture}
63 \end{center}
64 \end{frame}
65 }
66
67 \defineUnit{tmkonfiguration}{%
68 \begin{frame}
69 \frametitle{Turingmaschinen}
70 \setbeamercovered{dynamic}
71
72 \begin{definition}[Konfiguration]
73 Eine \alert{Konfiguration} ist ein Tripel $(\alpha, q, \beta) \in \Gamma^* \times Q \times \Gamma^*$. \\
74 Dies modelliert eine TM mit:
75 \begin{itemize}
76 \item \alert{Bandinhalt} $\ldots\square\alpha\beta\square\ldots$
77 \item \alert{Zustand} $q$
78 \item Kopf auf dem \alert{ersten Zeichen} von $\beta\square$
79 \end{itemize}
80 Die \alert{Startkonfiguration} bei Eingabe $w \in \Sigma^*$ ist $(\epsilon, q_0, w)$.
81 \end{definition}
82
83 \vfill
84
85 \only<1> {
86 \begin{center}
87 \begin{tikzpicture}
88 % Tape
89 \begin{scope}[start chain, node distance=0]
90 \node[on chain] {\ldots};
91 \node[tape] {$\square$};
92 \node[tape] (l) {$\square$};
93 \node[tape] {$0$};
94 \node[tape] {$1$};
95 \node[tape] (a){$1$};
96 \node[tape, active] (b){$0$};
97 \node[tape] {$\square$};
98 \node[on chain] {\ldots};
99 \end{scope}
100
101 % Head
102 \node [head,yshift=-4mm] at (b.south) (head) {$q_1$};
103
104 % Machine
105 \node[below=1.5cm of l] (machine) {};
106 \draw[every edge, dashed] (machine) .. controls (3.5, -2) .. (head.south);
107
108 % Example-Transition
109 \node[yshift=5mm] at (current bounding box.north) {$(011,q_1,0)$};
110 \end{tikzpicture}
111 \end{center}
112 }
113
114 \only<2> {
115 \begin{definition}[Akzeptanz]
116 Eine TM $M$ \alert{akzeptiert} die Sprache
117 \[ L(M) = \left\{ w \in \Sigma^* \mid \exists \alert{f \in F}, \alpha, \beta \in \Gamma^* . (\epsilon, q_0, w) \rightarrow_M^* (\alpha, \alert{f}, \beta) \right\} \]
118 \end{definition}
119 }
120 \end{frame}
121 }
122
123 \defineUnit{chomsky}{%
124 \begin{frame}[c]
125 \frametitle{Chomsky-Hierarchie}
126 \setbeamercovered{dynamic}
127
128 \begin{center}
129 \begin{tikzpicture}[auto]
130 \tikzstyle{rect} = [thick];
131 \tikzstyle{caption} = [align=left, anchor=north west];
132
133 \draw[rect, tumblue, fill=tumblue!10] (5.5, 0) rectangle (-5.5, 7) node[caption] {Berechenbare Funktionen};
134 \draw[rect, dashed, tumred, fill=tumred!10] (4.5, 0.3) rectangle (-4.5, 6) node[caption] {Typ 0 - Rekursiv aufzählbar\\Turingmaschinen, $\lambda$-Kalkül};
135 \draw[rect, tumivory, fill=tumivory!10] (3.5, 0.6) rectangle (-3.5, 4.8) node[caption] {Typ 1 - Kontextsensitiv\\CSG};
136 \draw[rect, tumorange, fill=tumorange!10] (2.5, 0.9) rectangle (-2.5, 3.6) node[caption] {Typ 2 - Kontextfrei\\PDA, CFG};
137 \draw[rect, tumgreen, fill=tumgreen!10] (1.5, 1.2) rectangle (-1.5, 2.4) node[caption] {Typ 3 - Regulär\\DFA, RE};
138 \end{tikzpicture}
139 \end{center}
140 \end{frame}
141 }
142
143 \defineUnit{berechenbarkeit}{%
144 \begin{frame}
145 \frametitle{Berechenbarkeit}
146 \setbeamercovered{dynamic}
147
148 \begin{definition}[Intuitive Berechenbarkeit]
149 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$
150 \begin{itemize}
151 \item nach \alert{endlich vielen Schritten} mit Ergebnis $f(n_1, \ldots, n_k)$ hält, falls $f(\ldots)$ definiert ist,
152 \item und \alert{nicht terminiert}, falls $f(\ldots)$ nicht definiert ist.
153 \end{itemize}
154 \end{definition}
155
156 \vfill
157
158 \begin{block}{Churchsche These (nicht beweisbar)}
159 Turing-Maschinen können genau \alert{alle} intuitiv berechenbaren Funktionen berechnen.
160 \end{block}
161 \end{frame}
162 }
163
164 \defineUnit{berechenbarkeitbeispiel}{%
165 \begin{frame}[c]
166 \frametitle{Berechenbarkeit}
167 \setbeamercovered{dynamic}
168
169 \begin{example}[Berechenbarkeit]
170 Sind die folgenden Funktionen intuitiv berechenbar?
171
172 \begin{align*}
173 f_1(n) &= \begin{cases}
174 1 & \text{falls $n$ prim}\\
175 0 & \text{sonst}
176 \end{cases} \\
177 f_2(n) &= \begin{cases}
178 1 & \text{falls $n$ die ersten $n$ Ziffern von $\pi$ darstellt}\\
179 0 & \text{sonst}
180 \end{cases} \\
181 f_3(n) &= \begin{cases}
182 1 & \text{falls in $\pi$ $n$ Nullen am Stück vorkommen}\\
183 0 & \text{sonst}
184 \end{cases}
185 \end{align*}
186 \end{example}
187 \end{frame}
188 }
189
190 \defineUnit{pr}{%
191 \begin{frame}
192 \frametitle{Primitive Rekursion}
193 \setbeamercovered{dynamic}
194
195 \begin{definition}[Basisfunktionen]
196 \alert{Primitiv Rekursiv} sind:
197 \begin{itemize}
198 \item Die konstante Funktion \alert{0}
199 \item Die \alert{Nachfolgerfunktion} $s(n) = n + 1$
200 \item Die \alert{Projektionsfunktion} $\pi_i^k : \N^k \to \N, i \in [k]$
201 \[ \pi_i^k(x_1, \ldots, x_k) = x_i \]
202 \end{itemize}
203 \end{definition}
204
205 \begin{definition}[Komposition]
206 Sind $g$ und $h_i$ PR und $\bar{x} = (x_1, \ldots, x_n)$, dann ist auch \alert{$f$} PR:
207 \[ f(\bar{x}) = \alert{g(h_1(\bar{x}), \ldots, h_k(\bar{x}))} \]
208 \end{definition}
209 \end{frame}
210 }
211
212 \defineUnit{prrekursion}{%
213 \begin{frame}
214 \frametitle{Primitive Rekursion}
215 \setbeamercovered{dynamic}
216 \begin{block}{Basisfunktionen und Komposition}
217 Schon \alert{PR} sind:
218 \begin{itemize}
219 \item Konstante: $0$
220 \item Nachfolger: $s(n) = n + 1$
221 \item Projektion: $\pi_i^k : \N^k \to \N$
222 \item Komposition: $f(\bar{x}) = g(h_1(\bar{x}), \ldots, h_k(\bar{x}))$
223 \end{itemize}
224 \end{block}
225 \begin{definition}[Primitive Rekursion] Das Schema der \alert{primitiven Rekursion} erzeugt aus $g$ und $h$ die Funktion \alert{$f$}: \begin{align*} f(0, \bar{x}) &= g(\bar{x}) \\ f(\alert{m + 1}, \bar{x}) &= h(f(\alert{m}, \bar{x}), \alert{m}, \bar{x}) \end{align*} \end{definition} \end{frame}
226 }
227
228 \defineUnit{prprogramme}{%
229 \begin{frame}
230 \frametitle{PR-Programme}
231 \setbeamercovered{dynamic}
232
233 U.a. diese Programme sind laut Vorlesung oder Übung PR:
234 \begin{itemize}
235 \item \alert{$add(x, y) = x + y$}
236 \item \alert{$mult(x, y) = x \cdot y$}
237 \item $pred(x) = \max \left\{ 0, x - 1 \right\}$
238 \item \alert{$x \dot{-} y = \max \left\{ 0, x - y \right\}$}
239 \item $div(x, y) = x \div y$ (Ganzzahldivision)
240 \item $mod(x, y) = x \mod y$
241 \vspace{1.5em}
242 \item $tower(n) = 2^{2^{2^{\iddots}}}$ mit $tower(4) = 2^{16}$
243 \item $sqr(x) = x^2$
244 \item $twopow(n) = 2^n$
245 \item $ifthen(n, a, b) = \begin{cases} a & n \neq 0 \\ b & n = 0 \end{cases}$
246 \end{itemize}
247 \end{frame}
248 }
249
250 \defineUnit{prerweitert}{%
251 \begin{frame}
252 \frametitle{Erweitertes PR-Schema}
253 \setbeamercovered{dynamic}
254
255 \begin{definition}[Erweitertes PR-Schema]
256 Das \alert{erweiterte Schema der primitiven Rekursion} erlaubt
257 \begin{align*}
258 f(0, \bar{x}) &= t_0 \\
259 f(m + 1, \bar{x}) &= t
260 \end{align*}
261 wobei
262 \begin{itemize}
263 \item $t_0$ enthält nur PR-Funktionen und die $x_i$
264 \item $t$ enthält nur \alert{$f(m, \bar{x})$}, PR Funktionen, \alert{$m$} und die $x_i$.
265 \end{itemize}
266 \end{definition}
267
268 \begin{theorem}
269 Das erweiterte Schema der primitiven Rekursion führt nicht aus \alert{PR} heraus.
270 \end{theorem}
271 \end{frame}
272 }
273
274 \defineUnit{tmif}{%
275 \begin{frame}
276 \frametitle{Programmieren mit TMs}
277 \setbeamercovered{dynamic}
278
279 Sind $f_1$ und $f_2$ Endzustände von $M$, so bezeichnet
280 \begin{center}
281 \begin{tikzpicture}
282 \node (M) at (0, 0) {$M$};
283 \node[above right=0.2cm and 1cm of M] (M1) {$M_1$};
284 \node[below right=0.2cm and 1cm of M] (M2) {$M_2$};
285 \coordinate[right of=M1] (M1s);
286 \coordinate[right of=M2] (M2s);
287
288 \draw[every edge] (-1, 0) -- (M);
289 \draw[every edge] (M) -- node[above left] {$f_1$} (M1);
290 \draw[every edge] (M) -- node[below left] {$f_2$} (M2);
291 \draw[every edge] (M1) -- (M1s);
292 \draw[every edge] (M2) -- (M2s);
293 \end{tikzpicture}
294 \end{center}
295 eine \alert{Fallunterscheidung}.\\
296 \begin{example}[Band=0?]
297 \begin{align*}
298 \delta(q_0, 0) &= (q_0, 0, R) \\
299 \delta(q_0, \square) &= (ja, \square, L) \\
300 \delta(q_0, a) &= (nein, a, N) \qquad \text{für} a \neq 0, \square
301 \end{align*}
302 \end{example}
303 \end{frame}
304 }
305
306 \defineUnit{while}{%
307 \begin{frame}
308 \frametitle{WHILE-Programme}
309 \setbeamercovered{dynamic}
310
311 \begin{definition}[WHILE-Programm]
312 Syntax von \alert{WHILE-Programmen}.\\
313 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$.
314 \begin{align*}
315 P &\rightarrow X := X + C \\
316 &\mid X := X - C \\
317 &\mid P; P \\
318 &\mid \alert{\mathbf{WHILE}\ X \neq 0 \ \mathbf{DO}\ P \ \mathbf{END}} \\
319 &\mid \textcolor{gray}{\mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END}} \\
320 &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}}
321 \end{align*}
322 \end{definition}
323
324 \begin{itemize}
325 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0.
326 \item Semantik wie erwartet.
327 \end{itemize}
328 \end{frame}
329 }
330
331 \defineUnit{goto}{%
332 \begin{frame}
333 \frametitle{GOTO-Programme}
334 \setbeamercovered{dynamic}
335
336 \begin{definition}[GOTO-Programm]
337 Syntax von \alert{GOTO-Programmen}.\\
338 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. \\
339 Alle Anweisungen haben eine Markierung \alert{$M_1 : A_1; M_2 : A_2$}.
340 \begin{align*}
341 P &\rightarrow X := X + C \\
342 &\mid X := X - C \\
343 &\mid P; P \\
344 &\mid \mathbf{GOTO}\ M_i \\
345 &\mid \mathbf{IF}\ X = 0 \ \mathbf{GOTO}\ M_i \\
346 &\mid \mathbf{HALT}
347 \end{align*}
348 \end{definition}
349
350 \begin{itemize}
351 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0.
352 \end{itemize}
353 \end{frame}
354 }
355
356 \defineUnit{loop}{%
357 \begin{frame}
358 \frametitle{LOOP-Programme}
359 \setbeamercovered{dynamic}
360
361 \begin{definition}[LOOP-Programm]
362 Syntax von \alert{LOOP-Programmen}.\\
363 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$.
364 \begin{align*}
365 P &\rightarrow X := X + C \\
366 &\mid X := X - C \\
367 &\mid P; P \\
368 &\mid \mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END} \\
369 &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}}
370 \end{align*}
371 \end{definition}
372
373 \begin{itemize}
374 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0.
375 \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.}
376 \end{itemize}
377 \end{frame}
378 }
379
380 \defineUnit{prmax}{%
381 \begin{frame}
382 \frametitle{Beschränkte Operationen}
383 \setbeamercovered{dynamic}
384 \begin{definition}
385 Ein Prädikat $P$ ist \alert{PR}, wenn es eine PR Funktion $\hat{P}$ gibt mit
386 \[\hat{P}(x) = 1 \Longleftrightarrow P(x)\]
387 \end{definition}
388
389 \begin{definition}[Beschränkte Operationen]
390 Ist $P$ PR, dann auch
391 \begin{itemize}
392 \item der \alert{beschränkte max-Operator}
393 \[\max \left\{ x \alert{\leq n} \mid P(x) \right\}, \quad \max \left\{ \emptyset \right\} = 0\]
394 \item der \alert{beschränkte Existenzquantor}
395 \[\exists x \alert{\leq n}. P(x)\]
396 \end{itemize}
397 \end{definition}
398 \end{frame}
399 }
400
401 \defineUnit{murekursion}{%
402 \begin{frame}
403 \frametitle{$\mu$-Rekursion}
404 \setbeamercovered{dynamic}
405
406 \begin{definition}[$\mu$-Operator]
407 Sei $f: \N^{k+1} \to \N$ eine Funktion.\\Der \alert{$\mu$-Operator} definiert eine neue Funktion $\mu f : \N^k \to \N$:
408 \[(\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}\]
409 \end{definition}
410
411 \vfill
412
413 \begin{itemize}
414 \item \alert{$^*$}Für alle \alert{$m \leq n$} muss $f$ definiert sein: $f(m, \bar{x}) \neq \perp$
415 \item PR + $\mu$ = $\mu$-Rekursion
416 \item In Pseudocode:
417 \begin{align*}
418 \mu f(\bar{x}) &= find(0, \bar{x}) \\
419 find(n, \bar{x}) &= \mathbf{if}\ f(n, \bar{x}) = 0 \ \mathbf{then}\ n \ \mathbf{else}\ find(n+1, \bar{x})
420 \end{align*}
421 \end{itemize}
422 \end{frame}
423 }
424
425 \defineUnit{modelluebersetzungen}{%
426 \begin{frame}
427 \frametitle{Übersetzungen}
428 \setbeamercovered{dynamic}
429
430 \begin{center}
431 \begin{tikzpicture}[node distance=2.5cm]
432 \node (WH) {WHILE};
433 \node (GO) [above left of = WH] {GOTO};
434 \node (TM) [above right of = WH] {TM};
435 \node (LO) [below of = WH] {LOOP};
436 \node (PR) [left of = LO] {PR};
437 \node (MR) [left of = WH] {$\mu$R};
438
439 \draw [every edge, ->] (LO) -- (WH);
440 \draw [every edge, ->] (PR) -- (MR);
441 \draw [every edge, tumgreen, <->] (LO) -- (PR);
442 \draw [every edge, tumgreen, <->] (WH) -- (MR);
443 \draw [every edge, <->] (WH) -- (GO);
444 \draw [every edge, ->] (WH) -- (TM);
445 \draw [every edge, ->] (TM) -- (GO);
446 \end{tikzpicture}
447 \end{center}
448
449 \vfill
450
451 LOOP kann in WHILE \alert{übersetzt} werden, WHILE ist also \alert{mindestens so mächtig} wie LOOP (sogar mächtiger).
452 \end{frame}
453 }
454
455 \defineUnit{entscheidbarkeit}{%
456 \begin{frame}
457 \frametitle{Entscheidbarkeit}
458 \setbeamercovered{dynamic}
459
460 \begin{definition}[Entscheidbarkeit]
461 Eine Menge $A$ heißt \alert{entscheidbar} gdw ihre \alert{charakteristische Funktion}
462 \[ \chi_A(x) := \begin{cases}1 & \text{falls } x \in A \\ 0 & \text{falls } x \not \in A \end{cases} \]
463 berechenbar ist.
464 \end{definition}
465
466 \begin{definition}[Semi-Entscheidbarkeit]
467 Eine Menge $A$ heißt \alert{semi-entscheidbar} gdw
468 \[ \chi'_A(x) := \begin{cases}1 & \text{falls } x \in A \\ \perp & \text{falls } x \not \in A \end{cases} \]
469 berechenbar ist.
470 \end{definition}
471 \end{frame}
472 }
473
474 \defineUnit{spezielleshalteproblem}{%
475 \begin{frame}
476 \frametitle{Spezielles Halteproblem}
477 \setbeamercovered{dynamic}
478
479 \begin{definition}[Spezielles Halteproblem]
480 Gegeben ein \structure{Wort} $w \in \left\{ 0, 1 \right\}^*$.\\
481 Hält \alert{$M_w$} bei Eingabe \alert{$w$}?
482 \[\alert{K} := \left\{ w \mid M_w[w]\downarrow \right\}\]
483 \end{definition}
484
485 \begin{theorem}[]
486 Das spezielle Halteproblem ist \alert{nicht entscheidbar}.
487 \end{theorem}
488
489 \vfill
490
491 \begin{itemize}
492 \item Hält eine Turingmaschine mit sich selbst als Eingabe?
493 \item $w$ ist die \structure{Gödelisierung} von $M_w$.
494 \item $K$ ist semi-entscheidbar, $\overline{K}$ \alert{nicht}.
495 \end{itemize}
496 \end{frame}
497 }
498
499 \defineUnit{halteproblem}{%
500 \begin{frame}
501 \frametitle{Allgemeines Halteproblem}
502 \setbeamercovered{dynamic}
503
504 \begin{definition}[Allgemeines Halteproblem]
505 Gegeben \structure{Wörter} $w, x \in \left\{ 0, 1 \right\}^*$.\\
506 Hält \alert{$M_w$} bei Eingabe \alert{$x$}?
507 \[\alert{H} := \left\{ w\#x \mid M_w[x]\downarrow \right\}\]
508 \end{definition}
509
510 \begin{theorem}[]
511 Das allgemeine Halteproblem ist \alert{nicht entscheidbar}.
512 \end{theorem}
513
514 \vfill
515
516 \begin{itemize}
517 \item Es ist $K \leq H$. Warum?
518 \end{itemize}
519 \end{frame}
520 }
521
522 \defineUnit{aufzaehlbarkeit}{%
523 \begin{frame}
524 \frametitle{Rekursive Aufzählbarkeit}
525 \setbeamercovered{dynamic}
526
527 \begin{definition}[Rekursiv aufzählbar]
528 Eine Menge $A$ heißt \alert{rekursiv aufzählbar} wenn $A = \emptyset$ oder es eine \alert{berechenbare} totale Funktion $f : \N \to A$ gibt, so dass
529 \[A = \left\{ f(0), f(1), \ldots \right\} = \bigcup_{n \in \N} \left\{ f(n) \right\}\]
530 \end{definition}
531
532 \vfill
533
534 \structure{Äquivalent:}
535 \begin{itemize}
536 \item $A$ rekursiv aufzählbar
537 \item $A$ semi-entscheidbar, also $\chi'_A$ berechenbar
538 \item $A=L(M)$ für eine TM $M$
539 \item $A$ ist Bild oder Urbild einer berechenbaren Funktion
540 \end{itemize}
541 \end{frame}
542 }
543
544 \defineUnit{rice}{%
545 \begin{frame}
546 \frametitle{Satz von Rice}
547 \setbeamercovered{dynamic}
548
549 \begin{theorem}[Rice]
550 Sei $F$ eine Menge berechenbarer Funktionen.\\
551 Sei weder $F = \emptyset$ noch $F = \text{alle ber. Funktionen}$ (\alert{$F$ nicht trivial}).\\
552 Dann ist \alert{unentscheidbar}, ob die von einer gegebenen TM $M_w$ berechnete Funktion in $F$ ist, also ob \alert{$\varphi_w \in F$}.
553 \end{theorem}
554
555 \begin{itemize}
556 \item Nicht-triviale \alert{semantische} Eigenschaften von Programmen sind unentscheidbar.
557 \item \alert{Termination} ist unentscheidbar.
558 \end{itemize}
559
560 \vfill
561
562 \structure{Rice-Shapiro:}
563 \begin{itemize}
564 \item Termination ist nicht semi-entscheidbar.
565 \item Nicht-Termination ist nicht semi-entscheidbar.
566 \end{itemize}
567 \end{frame}
568 }
569
570 \defineUnit{pcp}{%
571 \begin{frame}
572 \frametitle{PCP}
573 \setbeamercovered{dynamic}
574
575 \begin{definition}[Postsches Korrespondenzproblem]
576 Gegeben \structure{endliche Folge} $(x_1, y_1), \ldots, (x_k, y_k)$ mit $x_i, y_i \in \Sigma^+$.\\
577 Gibt es eine \alert{Folge von Indizes} $i_1, \ldots, i_n \in \left\{ 1, \ldots, k \right\}$ mit \alert{\[x_{i_1}, \ldots, x_{i_n} = y_{i_1}, \ldots, y_{i_n}\]}
578 \end{definition}
579
580 \vfill
581
582 \begin{center}
583 \begin{tikzpicture}
584 \begin{scope}[start chain, node distance=2em]
585 \node[tape, active] {\pcp{$x_i$}{$y_i$}};
586 \node[tape] (a) {\pcp{$001$}{$00$}};
587 \node[tape] (b) {\pcp{$10$}{$11$}};
588 \node[tape] (c) {\pcp{$1$}{$01$}};
589 \end{scope}
590 \node[below of=a] {$1$};
591 \node[below of=b] {$2$};
592 \node[below of=c] {$3$};
593 \end{tikzpicture}
594 \end{center}
595
596 \vfill
597
598 \begin{theorem}[]
599 Das PCP ist \alert{unentscheidbar}, aber semi-entscheidbar.
600 \end{theorem}
601 \end{frame}
602 }
603
604 \defineUnit{pcpbeispiel}{%
605 \begin{frame}
606 \frametitle{PCP lösen}
607 \setbeamercovered{dynamic}
608
609 \begin{block}{Idee}
610 \alert{Mögliche Lösungen} aufzählen, richtige Lösungen identifizieren
611 \end{block}
612
613 \begin{center}
614 \begin{tikzpicture}
615 \begin{scope}[start chain, node distance=2em]
616 \node[tape, active] {\pcp{$x_i$}{$y_i$}};
617 \node[tape] (a) {\pcp{$001$}{$00$}};
618 \node[tape] (b) {\pcp{$01$}{$10$}};
619 \node[tape] (c) {\pcp{$1$}{$11$}};
620 \end{scope}
621 \node[below of=a] {$1$};
622 \node[below of=b] {$2$};
623 \node[below of=c] {$3$};
624 \end{tikzpicture}
625
626 \vspace{2em}
627
628 \begin{tikzpicture}[grow=right, level distance = 2cm]
629 \tikzstyle{every node} = []
630 \tikzstyle{residual} = [rectangular, thin, fill=tumgreen!10, font=\scriptsize]
631 \tikzstyle{edge from parent} = [every edge]
632
633 \tikzstyle{level 1} = [sibling distance = 1.7cm]
634 \tikzstyle{level 2} = [sibling distance = 1.1cm]
635
636 \node[residual] {}
637 child {
638 node[residual] {\pcp{$1$}{}}
639 child {
640 node[residual] {\pcp{$1$}{}}
641 child {
642 node[residual] {\pcp{$1$}{}}
643 child {
644 node[residual]{$\ldots$}
645 edge from parent
646 }
647 edge from parent
648 node[below] {$2$}
649 }
650 child {
651 node[residual, active] {\pcp{}{}}
652 edge from parent
653 node[above] {$3$}
654 }
655 edge from parent
656 node[below] {$2$}
657 }
658 child {
659 node[residual, active] {\pcp{}{}}
660 edge from parent
661 node[above] {$3$}
662 }
663 edge from parent
664 node[below] {$1$}
665 }
666 child {
667 node[residual]{\pcp{}{$1$}}
668 child {
669 node[residual]{\pcp{}{$11$}}
670 child {
671 node[residual]{$\ldots$}
672 edge from parent
673 node[above] {$3$}
674 }
675 edge from parent
676 node[above] {$3$}
677 }
678 edge from parent
679 node[above] {$3$}
680 };
681
682 \uncover<2>{\node at (10cm, 0) {$L = \left\{ (12^*3)^+ \right\}$};}
683 \end{tikzpicture}
684 \end{center}
685 \end{frame}
686 }