diff options
| -rw-r--r-- | transp-inf110-01-calc.tex | 13 |
1 files changed, 7 insertions, 6 deletions
diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex index bdd8306..7a57f27 100644 --- a/transp-inf110-01-calc.tex +++ b/transp-inf110-01-calc.tex @@ -1721,9 +1721,9 @@ Quine !), et faire le contraire, ce qui conduit à un paradoxe. \label{undecidability-halting-problem} \frametitle{L'indécidabilité du problème de l'arrêt} -\itempoint\textbf{Théorème} (Turing) : il n'existe pas de fonction -récursive $h\colon \mathbb{N}^2 \to \mathbb{N}$ telle que $h(e,x) = 1$ -si $\varphi^{(1)}_e(x)\downarrow$ et $h(e,x) = 0$ si +\itempoint\textbf{Théorème} ([essentiellement] Turing) : il n'existe +pas de fonction récursive $h\colon \mathbb{N}^2 \to \mathbb{N}$ telle +que $h(e,x) = 1$ si $\varphi^{(1)}_e(x)\downarrow$ et $h(e,x) = 0$ si $\varphi^{(1)}_e(x)\uparrow$. \bigskip @@ -1765,9 +1765,10 @@ contradiction.\qed \smallskip -\itempoint\textbf{Théorème} (Turing) : il n'existe pas de fonction -récursive $h\colon \mathbb{N}^2 \to \mathbb{N}$ telle que $h(e,x) = 1$ -si $\varphi_e(x)\downarrow$ et $h(e,x) = 0$ si $\varphi_e(x)\uparrow$. +\itempoint\textbf{Théorème} ([essentiellement] Turing) : il n'existe +pas de fonction récursive $h\colon \mathbb{N}^2 \to \mathbb{N}$ telle +que $h(e,x) = 1$ si $\varphi_e(x)\downarrow$ et $h(e,x) = 0$ si +$\varphi_e(x)\uparrow$. \bigskip |