summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2018-01-15 22:48:05 +0100
committerDavid A. Madore <david+git@madore.org>2018-01-15 22:48:05 +0100
commit4431fe6dae0fa2d6b516476a4d5d35f0c7731611 (patch)
tree4f771bd45926fcd85a71b7f5eb2522ec5546b610
parentd0203c57f781358178c3c238d6f4df5381bd52ad (diff)
downloadinf105-4431fe6dae0fa2d6b516476a4d5d35f0c7731611.tar.gz
inf105-4431fe6dae0fa2d6b516476a4d5d35f0c7731611.tar.bz2
inf105-4431fe6dae0fa2d6b516476a4d5d35f0c7731611.zip
Take into account Antoine's remarks.
-rw-r--r--notes-inf105.tex6
1 files 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