|
36
|
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} |
