diff options
| -rw-r--r-- | notes-inf105.tex | 6 |
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 |