|
39
|
1 \input{preamble.tex} |
|
|
2 |
|
|
3 \title{Übung 11: Aussagen über TMs und PCP} |
|
|
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{Spezielles Halteproblem} |
|
|
15 \setbeamercovered{dynamic} |
|
|
16 |
|
|
17 \begin{definition}[Spezielles Halteproblem] |
|
|
18 Gegeben ein \structure{Wort} $w \in \left\{ 0, 1 \right\}^*$.\\ |
|
|
19 Hält \alert{$M_w$} bei Eingabe \alert{$w$}? |
|
|
20 \[\alert{K} := \left\{ w \mid M_w[w]\downarrow \right\}\] |
|
|
21 \end{definition} |
|
|
22 |
|
|
23 \begin{theorem}[] |
|
|
24 Das spezielle Halteproblem ist \alert{nicht entscheidbar}. |
|
|
25 \end{theorem} |
|
|
26 |
|
|
27 \vfill |
|
|
28 |
|
|
29 \begin{itemize} |
|
|
30 \item Hält eine Turingmaschine mit sich selbst als Eingabe? |
|
|
31 \item $w$ ist die \structure{Gödelisierung} von $M_w$. |
|
|
32 \item $K$ ist semi-entscheidbar, $\overline{K}$ \alert{nicht}. |
|
|
33 \end{itemize} |
|
|
34 \end{frame} |
|
|
35 |
|
|
36 \begin{frame} |
|
|
37 \frametitle{Allgemeines Halteproblem} |
|
|
38 \setbeamercovered{dynamic} |
|
|
39 |
|
|
40 \begin{definition}[Allgemeines Halteproblem] |
|
|
41 Gegeben \structure{Wörter} $w, x \in \left\{ 0, 1 \right\}^*$.\\ |
|
|
42 Hält \alert{$M_w$} bei Eingabe \alert{$x$}? |
|
|
43 \[\alert{H} := \left\{ w\#x \mid M_w[x]\downarrow \right\}\] |
|
|
44 \end{definition} |
|
|
45 |
|
|
46 \begin{theorem}[] |
|
|
47 Das allgemeine Halteproblem ist \alert{nicht entscheidbar}. |
|
|
48 \end{theorem} |
|
|
49 |
|
|
50 \vfill |
|
|
51 |
|
|
52 \begin{itemize} |
|
|
53 \item Es ist $K \leq H$. Warum? |
|
|
54 \end{itemize} |
|
|
55 \end{frame} |
|
|
56 |
|
|
57 \begin{frame} |
|
|
58 \frametitle{Rekursive Aufzählbarkeit} |
|
|
59 \setbeamercovered{dynamic} |
|
|
60 |
|
|
61 \begin{definition}[Rekursiv aufzählbar] |
|
|
62 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 |
|
|
63 \[A = \left\{ f(0), f(1), \ldots \right\} = \bigcup_{n \in \N} \left\{ f(n) \right\}\] |
|
|
64 \end{definition} |
|
|
65 |
|
|
66 \vfill |
|
|
67 |
|
|
68 \structure{Äquivalent:} |
|
|
69 \begin{itemize} |
|
|
70 \item $A$ rekursiv aufzählbar |
|
|
71 \item $A$ semi-entscheidbar, also $\chi'_A$ berechenbar |
|
|
72 \item $A=L(M)$ für eine TM $M$ |
|
|
73 \item $A$ ist Bild oder Urbild einer berechenbaren Funktion |
|
|
74 \end{itemize} |
|
|
75 \end{frame} |
|
|
76 |
|
|
77 \begin{frame} |
|
|
78 \frametitle{Satz von Rice} |
|
|
79 \setbeamercovered{dynamic} |
|
|
80 |
|
|
81 \begin{theorem}[Rice] |
|
|
82 Sei $F$ eine Menge berechenbarer Funktionen.\\ |
|
|
83 Sei weder $F = \emptyset$ noch $F = \text{alle ber. Funktionen}$ (\alert{$F$ nicht trivial}).\\ |
|
|
84 Dann ist \alert{unentscheidbar}, ob die von einer gegebenen TM $M_w$ berechnete Funktion in $F$ ist, also ob \alert{$\varphi_w \in F$}. |
|
|
85 \end{theorem} |
|
|
86 |
|
|
87 \begin{itemize} |
|
|
88 \item Nicht-triviale \alert{semantische} Eigenschaften von Programmen sind unentscheidbar. |
|
|
89 \item \alert{Termination} ist unentscheidbar. |
|
|
90 \end{itemize} |
|
|
91 |
|
|
92 \vfill |
|
|
93 |
|
|
94 \structure{Rice-Shapiro:} |
|
|
95 \begin{itemize} |
|
|
96 \item Termination ist nicht semi-entscheidbar. |
|
|
97 \item Nicht-Termination ist nicht semi-entscheidbar. |
|
|
98 \end{itemize} |
|
|
99 \end{frame} |
|
|
100 |
|
|
101 \begin{frame} |
|
|
102 \frametitle{PCP} |
|
|
103 \setbeamercovered{dynamic} |
|
|
104 |
|
|
105 \begin{definition}[Postsches Korrespondenzproblem] |
|
|
106 Gegeben \structure{endliche Folge} $(x_1, y_1), \ldots, (x_k, y_k)$ mit $x_i, y_i \in \Sigma^+$.\\ |
|
|
107 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}\]} |
|
|
108 \end{definition} |
|
|
109 |
|
|
110 \vfill |
|
|
111 |
|
|
112 \begin{center} |
|
|
113 \begin{tikzpicture} |
|
|
114 \begin{scope}[start chain, node distance=2em] |
|
|
115 \node[tape, active] {\pcp{$x_i$}{$y_i$}}; |
|
|
116 \node[tape] (a) {\pcp{$001$}{$00$}}; |
|
|
117 \node[tape] (b) {\pcp{$10$}{$11$}}; |
|
|
118 \node[tape] (c) {\pcp{$1$}{$10$}}; |
|
|
119 \end{scope} |
|
|
120 \node[below of=a] {$1$}; |
|
|
121 \node[below of=b] {$2$}; |
|
|
122 \node[below of=c] {$3$}; |
|
|
123 \end{tikzpicture} |
|
|
124 \end{center} |
|
|
125 |
|
|
126 \vfill |
|
|
127 |
|
|
128 \begin{theorem}[] |
|
|
129 Das PCP ist \alert{unentscheidbar}, aber semi-entscheidbar. |
|
|
130 \end{theorem} |
|
|
131 \end{frame} |
|
|
132 |
|
|
133 \begin{frame} |
|
|
134 \frametitle{PCP lösen} |
|
|
135 \setbeamercovered{dynamic} |
|
|
136 |
|
|
137 \begin{block}{Idee} |
|
|
138 \alert{Mögliche Lösungen} aufzählen, richtige Lösungen identifizieren |
|
|
139 \end{block} |
|
|
140 |
|
|
141 \begin{center} |
|
|
142 \begin{tikzpicture} |
|
|
143 \begin{scope}[start chain, node distance=2em] |
|
|
144 \node[tape, active] {\pcp{$x_i$}{$y_i$}}; |
|
|
145 \node[tape] (a) {\pcp{$001$}{$00$}}; |
|
|
146 \node[tape] (b) {\pcp{$01$}{$10$}}; |
|
|
147 \node[tape] (c) {\pcp{$1$}{$11$}}; |
|
|
148 \end{scope} |
|
|
149 \node[below of=a] {$1$}; |
|
|
150 \node[below of=b] {$2$}; |
|
|
151 \node[below of=c] {$3$}; |
|
|
152 \end{tikzpicture} |
|
|
153 |
|
|
154 \vspace{2em} |
|
|
155 |
|
|
156 \begin{tikzpicture}[grow=right, level distance = 2cm] |
|
|
157 \tikzstyle{every node} = [] |
|
|
158 \tikzstyle{residual} = [rectangular, thin, fill=tumgreen!10, font=\scriptsize] |
|
|
159 \tikzstyle{edge from parent} = [every edge] |
|
|
160 |
|
|
161 \tikzstyle{level 1} = [sibling distance = 1.7cm] |
|
|
162 \tikzstyle{level 2} = [sibling distance = 1.1cm] |
|
|
163 |
|
|
164 \node[residual] {} |
|
|
165 child { |
|
|
166 node[residual] {\pcp{$1$}{}} |
|
|
167 child { |
|
|
168 node[residual] {\pcp{$1$}{}} |
|
|
169 child { |
|
|
170 node[residual] {\pcp{$1$}{}} |
|
|
171 child { |
|
|
172 node[residual]{$\ldots$} |
|
|
173 edge from parent |
|
|
174 } |
|
|
175 edge from parent |
|
|
176 node[below] {$2$} |
|
|
177 } |
|
|
178 child { |
|
|
179 node[residual, active] {\pcp{}{}} |
|
|
180 edge from parent |
|
|
181 node[above] {$3$} |
|
|
182 } |
|
|
183 edge from parent |
|
|
184 node[below] {$2$} |
|
|
185 } |
|
|
186 child { |
|
|
187 node[residual, active] {\pcp{}{}} |
|
|
188 edge from parent |
|
|
189 node[above] {$3$} |
|
|
190 } |
|
|
191 edge from parent |
|
|
192 node[below] {$1$} |
|
|
193 } |
|
|
194 child { |
|
|
195 node[residual]{\pcp{}{$1$}} |
|
|
196 child { |
|
|
197 node[residual]{\pcp{}{$11$}} |
|
|
198 child { |
|
|
199 node[residual]{$\ldots$} |
|
|
200 edge from parent |
|
|
201 node[above] {$3$} |
|
|
202 } |
|
|
203 edge from parent |
|
|
204 node[above] {$3$} |
|
|
205 } |
|
|
206 edge from parent |
|
|
207 node[above] {$3$} |
|
|
208 }; |
|
|
209 |
|
|
210 \uncover<2>{\node at (10cm, 0) {$L = \left\{ (12^*3)^+ \right\}$};} |
|
|
211 \end{tikzpicture} |
|
|
212 \end{center} |
|
|
213 \end{frame} |
|
|
214 |
|
|
215 \end{document} |
