More comments on test.

1 files changed, 60 insertions, 3 deletions

diff --git a/controle-20180206.tex b/controle-20180206.tex
index c4aadc5..e384481 100644
--- a/controle-20180206.tex
+++ b/controle-20180206.tex
@@ -24,9 +24,9 @@
 \theoremstyle{definition}
 \newtheorem{comcnt}{Tout}
 \newcommand\thingy{%
-\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
+\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
 \newcommand\exercice{%
-\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
+\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}}
 \renewcommand{\qedsymbol}{\smiley}
 %
 \DeclareUnicodeCharacter{00A0}{~}
@@ -110,7 +110,7 @@ Durée : 1h30
 Barème \emph{indicatif} : 7 points par exercice
 
 \ifcorrige
-Ce corrigé comporte 9 pages (page de garde incluse)
+Ce corrigé comporte 10 pages (page de garde incluse)
 \else
 Cet énoncé comporte 4 pages (page de garde incluse)
 \fi
@@ -506,6 +506,18 @@ s'associe-t-elle\footnote{On dit qu'une opération binaire $\boxdot$
   que $@$ s'associe à droite.
 \end{corrige}
 
+\begin{commentaire}
+Beaucoup de copies affirment, par exemple, que l'opération $\#$ est
+prioritaire sur $@$ parce que $\#$ est plus haut dans l'arbre ou se
+rencontre en premier dans l'analyse : en réalité, l'opération
+prioritaire est celle qui se calcule en premier, c'est-à-dire de la
+façon la plus \emph{profonde} (on a précisé que $\boxtimes$ est
+prioritaire sur $\boxplus$ lorsque « $u\boxtimes v\boxplus w$ » se
+comprend comme « $(u\boxtimes v)\boxplus w$ » : c'est bien $\boxtimes$
+qui est imbriqué le plus profondément dans les parenthèses, et la
+comparaison avec l'arbre (e) aurait dû lever tout doute).
+\end{commentaire}
+
 \smallskip
 
 (La question (3) est indépendante de (1) et (2).  Par ailleurs, on
@@ -570,6 +582,27 @@ rationnel ?\quad (c) Le langage $L$ est-il rationnel ?
   pas rationnel.
 \end{corrige}
 
+\begin{commentaire}
+Dans la question (a), beaucoup de copies montrent correctement une
+seule implication (que tout mot de la forme « ${(}^i\, x\, {)}^j$ »
+appartient à $L\cap M$, ou bien que tout mot de $L\cap M$ a cette
+forme), mais oublient qu'il est essentiel de traiter les deux.
+
+Pour ce qui est de la question (b), certains se sont rendu la vie
+inutilement compliquée en prenant certes un mot de la forme $a^i x
+b^i$ mais en ne choisissant pas $i=k$ (ou au moins $i\geq k$), ce qui
+oblige à des discussions de cas qui n'avaient pas lieu d'être.  On
+rappelle donc que lorsqu'on applique le lemme de pompage, on choisit
+le mot $t$ auquel on va appliquer la propriété (la seule contrainte
+étant de devoir prendre $|t|\geq k$).
+
+La question (c) a été étonnamment peu traitée eu égard à sa
+simplicité.  Beaucoup ne montrent pas, ne pensent pas à montrer, ou ne
+savent pas montrer, que $M$ est rationnel (ce qui devrait pourtant
+sauter aux yeux...).  Certains arrivent à des conclusions fantaisistes
+comme « $L$ est rationnel ».
+\end{commentaire}
+
 
 %
 %
@@ -660,6 +693,18 @@ 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$.
 \end{corrige}
 
+\begin{commentaire}
+Certains pensent pouvoir déduire la semi-décidabilité de $L$ et $M$ de
+celle du problème de l'arrêt : la situation est effectivement proche,
+mais à moins d'une explication précise sur le fait qu'on peut calculer
+la valeur $\varphi_e(x)$ une fois qu'on s'est assuré qu'elle est bien
+définie, ce n'est pas légitime ; d'ailleurs, la semi-décidabilité du
+problème de l'arrêt est quelque chose de tellement simple (une fois
+acquise l'existence d'une machine universelle) qu'on ne devrait jamais
+l'invoquer, car il sera essentiellement toujours plus simple de dire
+« il suffit de lancer l'exécution du programme... ».
+\end{commentaire}
+
 (5) En imitant la démonstration du théorème de Turing sur
 l'indécidabilité du problème de l'arrêt, montrer qu'il n'existe aucun
 algorithme qui, prenant en entrée un couple $(e,x)$, termine toujours
@@ -685,6 +730,12 @@ $2$ si $\varphi_p(p) = 1$ et $1$ si $\varphi_p(p) = 2$, ce qui est une
 contradiction.
 \end{corrige}
 
+\begin{commentaire}
+Il n'y a eu à peu près qu'une réponse correcte à cette question.
+Quelques points partiels ont été attribués à ceux qui tentaient au
+moins de dire quelque chose et qui avaient un semblant d'idée.
+\end{commentaire}
+
 (6) Conclure.
 
 \begin{corrige}
@@ -695,6 +746,12 @@ disjoints et semi-décidables.  On a donc bien montré l'existence de
 langages semi-décidables disjoints et calculablement inséparables.
 \end{corrige}
 
+\begin{commentaire}
+Bien qu'elle fût essentiellement triviale (il suffisait de redire les
+résultats des questions précédentes), cette question n'a quasiment pas
+été traitée.
+\end{commentaire}
+
 \smallskip
 
 {\footnotesize (Remarque culturelle :\quad La construction de langages