Mercurial > 13ss.theoinf

comparison notes/tex/ue11_notes.tex @ 39:fa8ae3458eb7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ue11 notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Mon, 08 Jul 2013 23:41:59 +0200
parents
children 3175d3871752
comparison
equal deleted inserted replaced
38:c498361ea492 39:fa8ae3458eb7
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}