diff options
| author | David A. Madore <david+git@madore.org> | 2023-11-20 20:53:38 +0100 |
|---|---|---|
| committer | David A. Madore <david+git@madore.org> | 2023-11-20 20:53:38 +0100 |
| commit | f011aeba580df41be0fa38ec74b38d109943cfdc (patch) | |
| tree | 077baebe05245782d3f55a0bd1579dc503c01534 /transp-inf110-01-calc.tex | |
| parent | 08bcf42b666adb25e26dc365c456a350cd4445b0 (diff) | |
| download | inf110-lfi-f011aeba580df41be0fa38ec74b38d109943cfdc.tar.gz inf110-lfi-f011aeba580df41be0fa38ec74b38d109943cfdc.tar.bz2 inf110-lfi-f011aeba580df41be0fa38ec74b38d109943cfdc.zip | |
Fix various mistakes (or notational blunders) noted during lecture on 2023-11-20.
Diffstat (limited to 'transp-inf110-01-calc.tex')
| -rw-r--r-- | transp-inf110-01-calc.tex | 10 |
1 files changed, 5 insertions, 5 deletions
diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex index 653dfbb..6dc00b7 100644 --- a/transp-inf110-01-calc.tex +++ b/transp-inf110-01-calc.tex @@ -2497,9 +2497,9 @@ $(e,x)$, on peut exécuter $\varphi_e(x)$, et, s'il termine, renvoyer \itempoint Toutes sortes de variantes possibles, p.ex. : \begin{itemize} -\item $\{e\in \mathbb{N} : \varphi_e(e)\downarrow$ n'est pas décidable +\item $\{e\in \mathbb{N} : \varphi_e(e)\downarrow\}$ n'est pas décidable (preuve dans transp. \ref{undecidability-halting-problem-redux}) -\item $\{e\in \mathbb{N} : \varphi_e(0)\downarrow$ n'est pas décidable +\item $\{e\in \mathbb{N} : \varphi_e(0)\downarrow\}$ n'est pas décidable (théorème s-m-n : $\varphi_e(x) = \varphi_{s(e,x)}(0)$ avec $s$ p.r. ; cf. transp. \ref{undecidability-halting-problem-turing-machines-pristine-start}) @@ -2550,9 +2550,9 @@ f(A)$. \bigskip -\itempoint Variante : $A \subseteq \mathbb{N}$ \emph{non vide} est +\itempoint Variante : $B \subseteq \mathbb{N}$ \emph{non vide} est semi-décidable ssi il existe $f\colon \mathbb{N} \to \mathbb{N}$ -totale calculable telle que $f(\mathbb{N}) = A$. +totale calculable telle que $f(\mathbb{N}) = B$. \textcolor{teal}{D'où le terme « calculablement énumérable ».} \end{frame} @@ -3113,7 +3113,7 @@ xyz.((xz)(yz))$. \smallskip \itempoint On appelle \textbf{$\beta$-réduction} le remplacement en -sous-expression d'une \textcolor{purple}{redex} par son +sous-expression d'un \textcolor{purple}{redex} par son \textcolor{olive}{réduit}.\quad Ex. : $\lambda x. \textcolor{purple}{(\lambda y. y (\lambda z. z)) (\lambda z. x z)} \rightarrow \lambda x. \textcolor{olive}{(\lambda z. x z)(\lambda |