equal
deleted
inserted
replaced
339 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
339 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
340 |
340 |
341 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
341 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
342 \mode<presentation>{ |
342 \mode<presentation>{ |
343 \begin{frame}[c] |
343 \begin{frame}[c] |
344 \frametitle{Halting Problem} |
|
345 |
|
346 \large |
|
347 Given such a program \bl{$H$} define the following program \bl{$C$}: |
|
348 for all programs \bl{$A$}\bigskip |
|
349 |
|
350 \begin{itemize} |
|
351 \item \bl{$C(A) \dn 0$} iff \bl{$H(A, A) = 0$} |
|
352 \item \bl{$C(A) \dn 1$} otherwise |
|
353 \end{itemize} |
|
354 |
|
355 \end{frame}} |
|
356 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
357 |
|
358 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
359 \mode<presentation>{ |
|
360 \begin{frame}[c] |
|
361 \frametitle{Halting Problem (2)} |
344 \frametitle{Halting Problem (2)} |
362 |
345 |
363 \large |
346 \large |
364 Given such a program \bl{$H$} define the following program \bl{$C$}: |
347 Given such a program \bl{$H$} define the following program \bl{$C$}: |
365 for all programs \bl{$A$}\bigskip |
348 for all programs \bl{$A$}\bigskip |