From f709406faf2a26919879db1e9a8fb52f3f490fdc Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Fri, 31 Oct 2025 20:24:07 +0100 Subject: Historically, Turing did not actually prove the undecidability of the halting problem. --- transp-inf110-01-calc.tex | 13 +++++++------ 1 file changed, 7 insertions(+), 6 deletions(-) (limited to 'transp-inf110-01-calc.tex') 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 -- cgit v1.2.3