diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 14 |
1 files changed, 7 insertions, 7 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 8401188..737ff57 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -6256,8 +6256,8 @@ fonction indicatrice $\mathbf{1}_A \colon \mathbb{N} \to \mathbb{N}$ (valant $1$ sur $A$ et $0$ sur son complémentaire) est calculable. Autrement dit : lorsqu'il existe un algorithme qui prend en entrée $n\in\mathbb{N}$, termine toujours en temps fini, et renvoie -« oui » ($1$) si $n\in A$, « non » ($0$) si $n\not\in A$ (on dira que -l'algorithme « décide » $A$). +« oui » ($1$) si $n\in A$, et « non » ($0$) si $n\not\in A$ (on dira +que l'algorithme « décide » $A$). \smallskip @@ -6582,11 +6582,11 @@ S'il l'était, on pourrait définir un algorithme qui, donné un entier $e$, effectue les calculs suivants : (1º) utiliser le problème de l'arrêt (supposé décidable !) pour savoir, algorithmiquement en temps fini, si le $e$-ième algorithme termine quand on lui passe son propre -numéro $e$ en entrée, i.e., si $\varphi_e(e)\downarrow$, (2º) si oui, -effectuer une boucle infinie, et si non, terminer, en renvoyant, -disons, $42$. L'algorithme qui vient d'être décrit aurait un certain -numéro, disons, $p$, et la description de l'algorithme fait que, -quel que soit $e$, la valeur $\varphi_p(e)$ est indéfinie si +numéro $e$ en entrée, i.e., si $\varphi_e(e)\downarrow$, et ensuite +(2º) si oui, effectuer une boucle infinie, et si non, terminer, en +renvoyant, disons, $42$. L'algorithme qui vient d'être décrit aurait +un certain numéro, disons, $p$, et la description de l'algorithme fait +que, quel que soit $e$, la valeur $\varphi_p(e)$ est indéfinie si $\varphi_e(e)$ est définie tandis que $\varphi_p(e)$ est définie (de valeur $42$) si $\varphi_e(e)$ est indéfinie. En particulier, en prenant $e=p$, on voit que $\varphi_p(p)$ devrait être défini si et |