summaryrefslogtreecommitdiffstats
path: root/exercices3.tex
blob: 2d3d5a5aea0ad0109099e8706892b3dfd7a768f9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{ucs}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\usepackage{url}
%
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,positioning}
\usepackage[hyperindex=false]{hyperref}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
\renewcommand{\qedsymbol}{\smiley}
%
\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
%
\DeclareUnicodeCharacter{00A0}{~}
\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
%
\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
%
%
\DeclareFontFamily{U}{manual}{} 
\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
\newcommand{\manfntsymbol}[1]{%
    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
%
\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
\newif\ifcorrige
\corrigetrue
\newenvironment{corrige}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
{{\hbox{}\nobreak\hfill\checkmark}%
\ifcorrige\relax\else\egroup\fi\par}
%
%
% NOTE: compile dot files with
% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
\tikzstyle{state}=[]
\tikzstyle{final}=[accepting by arrow]
%
%
%
\begin{document}
\ifcorrige
\title{Exercices divers — Corrigé}
\else
\title{Exercices divers}
\fi
\author{David A. Madore}
\maketitle

\centerline{\textbf{INF105}}

{\footnotesize
\immediate\write18{sh ./vc > vcline.tex}
\begin{center}
Git: \input{vcline.tex}
\end{center}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pretolerance=8000
\tolerance=50000



%
%
%

\exercice

(1) Soit $\Sigma$ un alphabet (i.e., un ensemble fini).  L'ensemble $L
= \{u^k : u\in\Sigma^*, k\geq 2\}$ des mots qui sont une puissance
$k$-ième pour un $k\geq 2$ est-il décidable ?  Semi-décidable ?

(2) L'ensemble des $e \in \mathbb{N}$ tels que l'exécution du $e$-ième
programme (ou, si on préfère, de la $e$-ième machine de Turing),
exécuté sur l'entrée $42$, termine en au plus $10^{1000+e}$ étapes
est-il décidable ?  Semi-décidable ?

(3) L'ensemble des $e \in \mathbb{N}$ tels que l'exécution du $e$-ième
programme (ou, si on préfère, de la $e$-ième machine de Turing),
exécuté sur l'entrée $42$, termine en temps fini est-il décidable ?
Semi-décidable ?  (On pourra montrer qu'on peut y ramener le problème
de l'arrêt.)

\begin{corrige}
(1) Si $w = u^k$ pour un certain $u\neq\varepsilon$, alors
  nécessairement $k\leq |w|$ puisque $|w|=k\cdot|u|$.  On dispose donc
  de l'algorithme suivant pour décider si $w\in L$ : si
  $w=\varepsilon$, retourner vrai immédiatement ; sinon, pour $k$
  allant de $2$ à $|w|$ et qui divise $|w|$, considérer les $k$
  facteurs successifs de $w$ de longueur $|w|/k$ (c'est-à-dire, pour
  $0\leq i<k$, le facteur de $w$ de longueur $\ell := |w|/k$
  commençant à la position $\ell i$) : s'ils sont tous égaux, renvoyer
  vrai ; si la boucle termine sans avoir trouvé de $k$ qui convienne,
  renvoyer faux.  Le langage proposé est donc décidable (et \textit{a
    fortiori} semi-décidable).

(2) Donné un $e \in \mathbb{N}$, la fonction $10^{1000+e}$ est
  évidemment calculable.  On peut ensuite lancer l'exécution du
  $e$-ième programme, sur l'entrée $42$, pour au plus ce nombre
  d'étapes (en utilisant la machine universelle, c'est-à-dire, par
  exemple, en simulant la $e$-ième machine de Turing sur une machine
  de Turing).  Si l'exécution termine en le temps imparti, on renvoie
  vrai, sinon, on renvoie faux : ceci montre que l'ensemble proposé
  est bien décidable (et \textit{a fortiori} semi-décidable).

(3) L'ensemble $A$ proposé est « presque » le problème de l'arrêt.  La
  différence est que le problème de l'arrêt est l'ensemble des couples
  $(e,n)$ tels que le $e$-ième programme termine sur l'entrée $n$
  alors qu'ici on a fixé l'entrée à $42$.  Il s'agit donc de montrer
  que cette limitation ne rend pas pour autant calculable l'ensemble
  considéré.  Or donnés deux entiers $(e,n)$, on peut fabriquer un
  programme $e'$ qui prend en entrée une valeur, \emph{ignore} cette
  valeur, et exécute le $e$-ième programme sur l'entrée $n$ ; de plus
  un tel $e'$ se calcule algorithmiquement à partir de $e$ et $n$.
  L'exécution du programme $e'$ sur l'entrée $42$ (ou n'importe quelle
  autre entrée) se comporte donc comme l'exécution du programme $e$
  sur l'entrée $n$, et notamment, termine si et seulement si elle
  termine.  Autrement dit, $e'$ appartient à l'ensemble $A$ considéré
  dans cette question si et seulement si $(e,n)$ appartient au
  problème de l'arrêt.  Comme on vient de dire qu'on peut calculer
  $e'$ algorithmiquement à partir de $(e,n)$, si l'ensemble $A$ était
  décidable, le problème de l'arrêt le serait, ce qui n'est pas le
  cas.  Donc $A$ n'est pas décidable.  En revanche, $A$ est
  semi-décidable : il suffit de lancer l'exécution du programme $e$
  sur l'entrée $42$ et renvoyer vrai si ele termine (si elle ne
  termine pas, on ne termine pas).
\end{corrige}


%
%
%

\exercice

Soit $\Sigma$ un alphabet (i.e., un ensemble fini).  On s'intéresse à
des langages sur $\Sigma$.

(A) Montrer que si deux langages $L_1$ et $L_2$ sont décidables, alors
$L_1\cup L_2$ et $L_1\cap L_2$ et $L_1 L_2$ sont décidables ; montrer
que si un langage $L$ est décidable alors $L^*$ est décidable (pour ce
dernier, on pourra commencer par chercher, si $w \in \Sigma^*$ est un
mot de longueur $n$, comment énumérer toutes les façons de le
factoriser en mots de longueur non nulle).

(B) Montrer que si deux langages $L_1$ et $L_2$ sont semi-décidables,
alors $L_1\cup L_2$ et $L_1\cap L_2$ et $L_1 L_2$ sont
semi-décidables ; montrer que si un langage $L$ est décidable alors
$L^*$ est semi-décidable.

\begin{corrige}
(A) Supposons qu'on dispose d'algorithmes $T_1$ et $T_2$ qui décident
  $L_1$ et $L_2$ respectivement (i.e., donné $w \in \Sigma^*$,
  l'algorithme $T_i$ termine toujours en temps fini, en répondant oui
  si $w\in L_i$ et non si $w\not\in L_i$).

Pour faire un algorithme qui décide $L_1\cup L_2$, donné un mot
$w\in\Sigma^*$, il suffit de lancer successivement $T_1$ et $T_2$ : si
l'un des deux répond oui, on répond oui, sinon on répond non
(autrement dit, on calcule les valeurs de vérité de $w\in L_1$ et
$w\in L_2$ au moyen de $T_1$ et $T_2$, et on calcule ensuite leur
« ou » logique).  De même pour décider $L_1\cap L_2$, il suffit de
lancer successivement $T_1$ et $T_2$, si les deux répondent oui on
répond oui, sinon on répond non (i.e., on calcule les valeurs de
vérité de $w\in L_1$ et $w\in L_2$ au moyen de $T_1$ et $T_2$, et on
calcule ensuite leur « et » logique).

Pour décider $L_1 L_2$, on effectue une boucle sur toutes les
factorisation $w = uv$ de $w$, c'est-à-dire, une boucle sur toutes les
longueurs $0\leq i\leq |w|$ en appelant à chaque fois $u$ le préfixe
de $w$ de longueur $i$ et $v$ le suffixe de $w$ de longueur $|w|-i$,
et pour chaque paire $(u,v)$ ainsi trouvée, on utilise $T_1$ et $T_2$
pour tester si $u\in L_1$ et $v\in L_2$ : si c'est le cas, on termine
l'algorithme en répondant oui (on a $w = uv \in L_1 L_2$) ; si aucune
paire ne convient, on répond non.

L'algorithme pour décider $L^*$ est semblable : il s'agit de tester
toutes les manières de factoriser un mot $w \in \Sigma^*$ en facteurs
de longueur non nulle.  (On peut d'ores et déjà exclure
$w=\varepsilon$ car le mot vide appartient de toute façon à $L^*$.)
Si $n=|w| > 0$, on peut effectuer une boucle pour un nombre de
facteurs $k$ allant de $1$ à $n$, et, pour chaque $k$, effectuer $k$
boucles emboîtées pour déterminer les limites des facteurs
$u_1,\ldots,u_k \in \Sigma^+$ tels que $w = u_1\cdots u_k$ (il suffit
par exemple de faire boucler $i_1,\ldots,i_k$ chacun de $1$ à $n$, et
lorsque $i_1+\cdots+i_k = n$, appaler $u_j$ le facteur de $w$ de
longueur $i_j$ commençant à la position $i_1+\cdots+i_{j-1}$).  Pour
chaque factorisation comme on vient de le dire, on teste si tous les
$u_i$ appartiennent à $L$, et si c'est le cas on renvoie vrai (le mot
$w$ appartient à $L^*$) ; si aucune factorisation ne convient, on
renvoie faux.

(Dans l'algorithme qui précède, on a écarté les factorisations faisant
intervenir le mot vide, car si $w$ est factorisable en mots de $L$ en
faisant intervenir le mot vide, quitte à retirer celui-ci, il est
encore factorisable en mots non vides de $L$.)

(B) Les algorithmes sont très semblables à ceux de la partie (A) si ce
n'est qu'il faut tenir compte de la possibilité qu'ils puissent ne pas
terminer.  On doit donc les lancer « en parallèle » et pas « en
  série » : lorsqu'on dira qu'on lance deux algorithmes $T$ et $T'$
« en parallèle », cela signifie qu'on exécute une étape du calcul de
$T$, puis une étape de $T'$, puis de nouveau une de $T$, et ainsi de
suite en alternant entre les deux, jusqu'à ce que l'un termine et
renvoie vrai.

Si $L_1$ et $L_2$ sont semi-dédicables et si $T_1$ et $T_2$ sont des
algorithmes qui les « semi-décident » (i.e., $T_i$ termine en temps
fini et répond oui si $w\in L_i$, et ne termine pas sinon), pour
semi-décider $L_1\cup L_2$, on lance les deux algorithmes $T_1$ et
$T_2$ en parallèle sur le même mot $w$ : si l'un d'eux termine, on
termine en renvoyant vrai (sinon, bien sûr, on ne termine pas).

Pour semi-décider $L_1\cap L_2$, en revanche, il n'y a pas de raison
de procéder en parallèle : on lance d'abord $T_1$ sur le mot $w$ à
tester : si $T_1$ termine, on lance ensuite $T_1$ sur le même mot : si
$T_2$ termine et renvoie vrai, on renvoie vrai ; si l'un des deux
algorithmes $T_i$ lancés séquentiellement ne termine pas, bien sûr, le
calcul dans son ensemble ne terminera pas.

Pour semi-décider $L_1 L_2$ ou $L^*$, on procède comme dans le cas (A)
en lançant en parallèle les algorithmes pour tester toutes les
différentes factorisations possibles $w = uv$ ou bien $w = u_1\cdots
u_k$ (en mots non vides) du mot $w$.
\end{corrige}

%
%
%

\exercice

On rappelle qu'une fonction $f\colon \mathbb{N} \to \mathbb{N}$ est
dite \emph{calculable} lorsqu'il existe un algorithme (par exemple, un
programme pour une machine de Turing) prenant en entrée un
$n\in\mathbb{N}$ qui termine toujours en temps fini et renvoie la
valeur $f(n)$.  On rappelle qu'une partie $E$ de $\mathbb{N}$ ou de
$\mathbb{N}^2$ est dite \emph{décidable} lorsque sa fonction
indicatrice est calculable, ou, ce qui revient au même, lorsqu'il
existe un algorithme prenant en entrée un élément de $\mathbb{N}$ ou
de $\mathbb{N}^2$ qui termine toujours en temps fini et renvoie
vrai ($1$) ou faux ($0$) selon que l'élément fourni appartient ou non
à $E$.  On rappelle enfin qu'une partie $E$ de $\mathbb{N}$ ou de
$\mathbb{N}^2$ est dite \emph{semi-décidable} lorsqu'il existe un
algorithme prenant en entrée un élément de $\mathbb{N}$ ou de
$\mathbb{N}^2$ qui termine toujours en temps fini et renvoie
vrai ($1$) si l'élément fourni appartient à $E$, et sinon ne termine
pas (on peut aussi accepter qu'il termine en renvoyant faux, cela ne
change rien).

Soit $f\colon \mathbb{N} \to \mathbb{N}$ : montrer qu'il y a
équivalence entre les affirmations suivantes :
\begin{enumerate}
\item la fonction $f$ est calculable,
\item le graphe $\Gamma_f := \{(n,f(n)) : n\in\mathbb{N}^2\} =
  \{(n,p)\in\mathbb{N}^2 : p=f(n)\}$ de $f$ est décidable,
\item le graphe $\Gamma_f$ de $f$ est semi-décidable.
\end{enumerate}

(Montrer que (3) implique (1) est le plus difficile : on pourra
commencer par s'entraîner en montrant que (2) implique (1).  Pour
montrer que (3) implique (2), on pourra chercher une façon de tester
en parallèle un nombre croissant de valeurs de $p$ de manière à
s'arrêter si l'une quelconque convient.)

\begin{corrige}
Montrons que (1) implique (2) : si on dispose d'un algorithme capable
de calculer $f(n)$ en fonction de $n$, alors il est facile d'écrire un
algorithme capable de décider si $p=f(n)$ (il suffit de calculer
$f(n)$ avec l'algorithme supposé exister, de comparer avec la valeur
de $p$ fournie, et de renvoyer vrai/$1$ si elles sont égales, et
faux/$0$ sinon).

Le fait que (2) implique (3) est évident car tout ensemble décidable
est semi-décidable.

Montrons que (2) implique (1) même si ce ne sera au final pas utile :
supposons qu'on ait un algorithme $T$ qui décide $\Gamma_f$ (i.e.,
donnés $(n,p)$, termine toujours en temps fini, en répondant oui si
$p=f(n)$ et non si $p\neq f(n)$), et on cherche à écrire un algorithme
qui calcule $f(n)$.  Pour cela, donné un $n$, il suffit de lancer
l'algorithme $T$ successivement sur les valeurs $(n,0)$ puis $(n,1)$
puis $(n,2)$ et ainsi de suite (c'est-à-dire faire une boucle infinie
sur $p$ et lancer $T$ sur chaque couple $(n,p)$) jusqu'à trouver un
$p$ pour lequel $T$ réponde vrai : on termine alors en renvoyant la
valeur $p$ qu'on a trouvée, qui vérifie $p=f(n)$ par définition
de $T$.

Reste à montrer que (3) implique (1) : supposons qu'on ait un
algorithme $T$ qui « semi-décide » $\Gamma_f$ (i.e., donnés $(n,p)$,
termine en temps fini et répond oui si $p=f(n)$, et ne termine pas
sinon), et on cherche à écrire un algorithme qui calcule $f(n)$.  Pour
cela, on va tester les valeurs $0\leq p\leq M$ chacune pour $M$ étapes
et faire tendre $M$ vers l'infini : plus exactement, on utilise
l'algorithme $U$ suivant :
\begin{itemize}
\item pour $M$ allant de $0$ à l'infini,
\begin{itemize}
\item pour $p$ allant de $0$ à $M$,
\begin{itemize}
\item exécuter l'algorithme $T$ sur l'entrée $(n,p)$ pendant au
  plus $M$ étapes,
\item s'il termine en renvoyant vrai ($1$), terminer et renvoyer $p$
  (sinon, continuer les boucles).
\end{itemize}
\end{itemize}
\end{itemize}

(Intuitivement, $U$ essaie de lancer l'algorithme $T$ sur un nombre de
valeurs de $p$ de plus en plus grand et en attendant de plus en plus
longtemps pour voir si l'une d'elles termine.)

Si l'algorithme $U$ défini ci-dessus termine, il renvoie forcément
$f(n)$ (puisque l'algorithme $T$ a répondu vrai, c'est que $p=f(n)$,
et on renvoie la valeur en question) ; il reste à expliquer pourquoi
$U$ termine toujours.  Mais la valeur $f(n)$ existe (même si on ne la
connaît pas) car la fonction $f$ était supposée définie partout, et
lorsque l'algorithme $T$ est lancé sur $(n,f(n))$ il est donc censé
terminer en un certain nombre (fini !) d'étapes : si $M$ est supérieur
à la fois à $f(n)$ et à ce nombre d'étapes, la valeur $f(n)$ va être
prise par $p$ dans la boucle intérieure, et pour cette valeur,
l'algorithme $T$ va terminer sur l'entrée $(n,p)$ en au plus $M$
étapes, ce qui assure que $U$ termine effectivement.

L'algorithme $U$ calcule donc bien la fonction $f$ demandée, ce qui
prouve (1).
\end{corrige}

%
%
%

\exercice

Soit $A \subseteq \mathbb{N}$ un ensemble infini.  Montrer qu'il y a
équivalence entre :
\begin{itemize}
\item l'ensemble $A$ est décidable,
\item il existe une fonction calculable \emph{strictement croissante}
  $f\colon\mathbb{N}\to\mathbb{N}$ telle que $f(\mathbb{N}) = A$.
\end{itemize}

\begin{corrige}
Supposons $A$ décidable : on va construire $f$ comme indiqué.  Plus
exactement, on va appeler $f(n)$ le $n$-ième élément de $A$ par ordre
croissant (c'est-à-dire que $f(0)$ est le plus petit élément de $A$,
et $f(1)$ le suivant par ordre de taille, et ainsi de suite ; noter
que $A$ est infini donc cette fonction est bien définie).  Montrons
que $f$ est calculable : donné un entier $n$, on teste successivement
si $0\in A$ puis $1\in A$ puis $2\in A$ et ainsi de suite, à chaque
fois en utilisant un algorithme décidant $A$ (qui est censé exister
par hypothèse) jusqu'à obtenir $n$ fois la réponse « oui » ; plus
exactement :
\begin{itemize}
\item initialiser $m \leftarrow 0$,
\item pour $k$ allant de $0$ à l'infini,
\begin{itemize}
\item interroger l'algorithme qui décide si $k\in A$,
\item s'il répond « oui » :
\begin{itemize}
\item si $m=n$, terminer et renvoyer $k$,
\item sinon, incrémenter $m$ (c'est-à-dire faire $m \leftarrow m+1$).
\end{itemize}
\end{itemize}
\end{itemize}
La boucle termine car $A$ est infini.

Réciproquement, supposons $f$ strictement croissante calculable et
posons $A = f(\mathbb{N})$ : on veut montrer que $A$ est décidable.
Or pour décider si $k \in A$, il suffit de calculer successivement
$f(0)$, $f(1)$, $f(2)$ et ainsi de suite, et de terminer si $f(n)$
atteint ou dépasse le $k$ fixé : s'il l'atteint, on renvoie vrai (on a
trouvé $n$ tel que $f(n)=k$), sinon, on renvoie faux (la valeur $k$ a
été sautée par la fonction $f$ et ne sera donc jamais atteinte).
L'algorithme est donc explicitement :
\begin{itemize}
\item pour $n$ allant de $0$ à l'infini,
\begin{itemize}
\item calculer $f(n)$,
\item si $f(n) = k$, renvoyer vrai,
\item si $f(n) > k$, renvoyer faux.
\end{itemize}
\end{itemize}
La boucle termine car toute fonction strictement croissante
$\mathbb{N}\to\mathbb{N}$ est de limite $+\infty$ en l'infini (donc
$f(n)$ finit forcément par atteindre ou dépasser $k$).
\end{corrige}

%
%
%

\exercice

Soit $S(e,n)$ le nombre d'étapes de l'exécution du $e$-ième programme
(ou, si on préfère, de la $e$-ième machine de Turing) quand on lui
fournit le nombre $n$ en entrée, à supposer que cette exécution
termine ; sinon, $S(e,n)$ n'est pas défini.

Soit par ailleurs $M(k)$ le maximum des $S(e,n)$ pour $0\leq e\leq k$
et $0\leq n\leq k$ qui soient définis (et $0$ si aucun d'eux n'est
défini).  Autrement dit, il s'agit du plus petit entier supérieur ou
égal au nombre d'étapes de l'exécution de l'un des programmes $0\leq
e\leq k$ sur l'un des entiers $0\leq n\leq k$ en entrée, lorsqu'ils
terminent.

Montrer que la fonction $M$ n'est pas calculable (i.e., n'est pas
calculable par un algorithme) : on pourra pour cela montrer que la
connaissance de $M$ permet de résoudre le problème de l'arrêt.
Montrer même qu'\emph{aucune} fonction $M'$ telle que $M'(k) \geq
M(k)$ pour tout $k$ n'est calculable.  Montrer que même si $M'$
vérifie simplement $M'(k)\geq M(k)$ pour $k\geq k_0$, alors $M'$ n'est
pas calculable.  Bref, la fonction $M$ croît plus vite que n'importe
quelle fonction calculable.

\emph{Remarque :} La fonction $M$, ou différentes variantes de
celle-ci, s'appelle fonction du « castor affairé ».  On peut montrer
encore plus fort : si $M'(k)\geq M(k)$ pour un nombre infini de
valeurs de $k$, alors $M'$ n'est pas calculable (Radó, 1962,
\textit{On Non-Computable Functions}).

\begin{corrige}
Supposons que $M$ soit calculable.  On peut alors résoudre le problème
de l'arrêt de la manière suivante : donné un algorithme $T$, de
numéro $e$, et une entrée $n$ à fournir à cet algorithme, pour savoir
si $T$ s'arrête, on calcule $M(k)$ où $k = \max(e,n)$, on exécute
ensuite l'algorithme $T$ pendant au plus $M(k)$ étapes : s'il termine
dans le temps imparti, on répond vrai (il a terminé), sinon, on répond
faux (il ne terminera jamais).  Cette résolution du problème de
l'arrêt est correcte, car si $T$ termine sur l'entrée $n$, il prendra
par définition $S(e,n)$ étapes, avec $0\leq e\leq k$ et $0\leq n\leq
k$ par définition de $k$, donc $S(e,n) \leq M(k)$ par définition de
$M(k)$ : ceci signifie précisément que si $T$ n'a pas terminé en
$M(k)$ étapes, il ne terminera jamais.

Exactement le même argument montre que $M'$ n'est pas calculable sous
l'hypothèse que $M'(k) \geq M(k)$ pour tout $k$ : s'il l'était, on
pourrait exécuter l'algorithme $T$ pendant au plus $M'(k)$ étapes, et
comme on a $S(e,n) \leq M(k) \leq M'(k)$, la même démonstration
convient.

Enfin, si on suppose seulement $M'(k)\geq M(k)$ pour $k\geq k_0$, la
fonction $M'$ n'est toujours pas calculable : en effet, si on suppose
par l'absurde qu'elle l'est, la fonction $M''$ qui à $k$ associe
$M'(k)$ si $k\geq k_0$ et $M(k)$ sinon, serait encore calculable
puisqu'elle ne diffère de $M'$ qu'en un nombre fini de valeurs, or
changer la valeur en un point d'une fonction calculable donne toujours
une fonction calculable (même si on « ne connaît pas » la valeur à
changer, elle existe, donc l'algorithme modifié existe).  Mais d'après
le paragraphe précédent, $M''$ n'est pas calculable puisqu'elle est
partout supérieure ou égale à $M$.
\end{corrige}


%
%
%
\end{document}