diff options
| -rw-r--r-- | controle-20180206.tex | 4 |
1 files changed, 2 insertions, 2 deletions
diff --git a/controle-20180206.tex b/controle-20180206.tex index 76d150c..f9a66b9 100644 --- a/controle-20180206.tex +++ b/controle-20180206.tex @@ -603,7 +603,7 @@ Pour cela, on appelle $L$ l'ensemble des couples\footnote{Pour être programme $e$ sur l'entrée $x$ termine en temps fini et renvoie la valeur $1$ (ce qui peut se noter $\varphi_e(x) = 1$) ; et $M$ le langage défini de la même manière mais avec la valeur $2$, -i.e., $\varphi_e(x) = 2$. (Ici, $1$ et $2$ peuvent être remplacés +i.e., $\varphi_e(x) = 2$. (Ici, $1$ et $2$ peuvent être remplacés par deux éléments distincts quelconques de $\mathbb{N}$ : si on a souhaité remplacer $\mathbb{N}$ par $\Sigma^*$, on peut prendre deux mots distincts quelconques, par exemple $a$ et $aa$.) @@ -626,7 +626,7 @@ termine en retournant $1$, renvoyer « vrai », tandis que si elle termine en renvoyant n'importe quelle autre valeur, faire une boucle infinie (bien sûr, si le programme $e$ ne termine jamais sur l'entrée $x$, on ne termine pas non plus). Ceci montre que $L$ est -semi-décidable. Le même raisonnement s'appliquer pour $M$. +semi-décidable. Le même raisonnement s'applique pour $M$. \end{corrige} (5) En imitant la démonstration du théorème de Turing sur |