diff options
| -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 |