From 4431fe6dae0fa2d6b516476a4d5d35f0c7731611 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Mon, 15 Jan 2018 22:48:05 +0100
Subject: Take into account Antoine's remarks.
---
notes-inf105.tex | 6 +++---
1 file changed, 3 insertions(+), 3 deletions(-)
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 1c2dde6..8401188 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -6241,7 +6241,7 @@ suffisamment général dans lequel il est impossible qu'un programme
\begin{defn}\label{definition-computable-function-or-set}
On dit qu'une fonction $f\colon\mathbb{N}\to\mathbb{N}$ est
-\defin{calculable (fonction)} (ou \index{récursive
+\defin[calculable (fonction)]{calculable} (ou \index{récursive
(fonction)|see{calculable}}« récursive ») lorsqu'il existe un
algorithme qui prend en entrée $n\in\mathbb{N}$, termine toujours en
temps fini, et calcule (renvoie) $f(n)$.
@@ -6456,7 +6456,7 @@ ou erroné pour une raison quelconque, la fonction $\varphi_e$ est
simplement non-définie partout). Les détails de cette énumération
dépendent de la formalisation utilisée pour la calculabilité et ne
sont pas importants\footnote{Par exemple, ceux qui aiment le langage
- Java, peuvent considérer que $\varphi_e$ désigne le résultat de
+ Java peuvent considérer que $\varphi_e$ désigne le résultat de
l'exécution du programme Java représenté par le mot codé par $e$, si
ce programme est valable (remplacer Java par tout autre langage
préféré).}.
@@ -6575,7 +6575,7 @@ Le problème de l'arrêt est semi-décidable en vertu de l'existence
d'une machine universelle : donnés $e$ et $n$, on exécute le $e$-ième
algorithme sur l'entrée $n$ (c'est ce que fait la machine
universelle), et s'il termine on renvoie « oui » (et s'il ne termine
-pas, bien sûr, on n'a pas de choix que de ne pas terminer).
+pas, bien sûr, la seule possibilité est de ne pas terminer).
Montrons par l'absurde que le problème de l'arrêt n'est pas décidable.
S'il l'était, on pourrait définir un algorithme qui, donné un entier
--
cgit v1.2.3