diff options
| author | David A. Madore <david+git@madore.org> | 2025-10-31 20:24:07 +0100 |
|---|---|---|
| committer | David A. Madore <david+git@madore.org> | 2025-10-31 20:24:07 +0100 |
| commit | f709406faf2a26919879db1e9a8fb52f3f490fdc (patch) | |
| tree | 86a8f672196b92dc3a5d4d099616336ab59d1588 /transp-inf110-01-calc.tex | |
| parent | 50ef48a59e85eb4155ad1cf45b73b432cb9a40ab (diff) | |
| download | inf110-lfi-f709406faf2a26919879db1e9a8fb52f3f490fdc.tar.gz inf110-lfi-f709406faf2a26919879db1e9a8fb52f3f490fdc.tar.bz2 inf110-lfi-f709406faf2a26919879db1e9a8fb52f3f490fdc.zip | |
Historically, Turing did not actually prove the undecidability of the halting problem.
Diffstat (limited to 'transp-inf110-01-calc.tex')
| -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 |