equal
deleted
inserted
replaced
364 Given such a program \bl{$H$} define the following program \bl{$C$}: |
364 Given such a program \bl{$H$} define the following program \bl{$C$}: |
365 for all programs \bl{$A$}\bigskip |
365 for all programs \bl{$A$}\bigskip |
366 |
366 |
367 \begin{itemize} |
367 \begin{itemize} |
368 \item \bl{$C(A) \dn 0$} iff \bl{$H(A, A) = 0$} |
368 \item \bl{$C(A) \dn 0$} iff \bl{$H(A, A) = 0$} |
369 \item \bl{$C(A) \dn 1$} otherwise |
369 \item \bl{$C(A) \dn$ loops} otherwise |
370 \end{itemize} |
370 \end{itemize} |
371 |
371 |
372 \end{frame}} |
372 \end{frame}} |
373 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
373 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
374 |
374 |
379 |
379 |
380 |
380 |
381 \bl{$H(C, C)$} is either \bl{$0$} or \bl{$1$}. |
381 \bl{$H(C, C)$} is either \bl{$0$} or \bl{$1$}. |
382 |
382 |
383 \begin{itemize} |
383 \begin{itemize} |
384 \item \bl{$H(C, C) = 1$} $\stackrel{def H}{\Rightarrow}$ \bl{$C(C)\downarrow$} $\stackrel{def C}{\Rightarrow}$ \bl{$H(C, C)=0$} |
384 \item \bl{$H(C, C) = 1$} $\stackrel{\text{def}\,H}{\Rightarrow}$ \bl{$C(C)\downarrow$} $\stackrel{\text{def}\,C}{\Rightarrow}$ \bl{$H(C, C)=0$} |
385 \item \bl{$H(C, C) = 0$} $\stackrel{def H}{\Rightarrow}$ \bl{$C(C)$} loops $\stackrel{def C}{\Rightarrow}$\\ |
385 \item \bl{$H(C, C) = 0$} $\stackrel{\text{def}\,H}{\Rightarrow}$ \bl{$C(C)$} loops $\stackrel{\text{def}\,C}{\Rightarrow}$\\ |
386 \hspace{7cm}\bl{$H(C, C)=1$} |
386 \hspace{7cm}\bl{$H(C, C)=1$} |
387 \end{itemize} |
387 \end{itemize} |
388 |
388 |
389 Contradiction in both cases. So \bl{$H$} cannot exist. |
389 Contradiction in both cases. So \bl{$H$} cannot exist. |
390 |
390 |