summaryrefslogtreecommitdiffstats
path: root/exercices-inf110.tex
blob: 6a910721e6437b1864d77fbf69ac40acb7b63a08 (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
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[french]{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}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}[section]
\newcommand\thingy{%
\refstepcounter{comcnt}\medskip\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}}
%
\newcommand{\dbllangle}{\mathopen{\langle\!\langle}}
\newcommand{\dblrangle}{\mathclose{\rangle\!\rangle}}
%
\DeclareUnicodeCharacter{00A0}{~}
%
\newif\ifcorrige
\corrigetrue
\newenvironment{corrige}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\footnotesize\noindent{\underbar{\textit{Corrigé.}}\quad}}
{{\hbox{}\nobreak\hfill\checkmark}%
\ifcorrige\relax\else\egroup\fi\par}
%
%
%
\begin{document}
\title{Logique et Fondements de l'Informatique\\Exercices}
\author{David A. Madore}
\maketitle

\centerline{\textbf{INF1110}}

\vskip2cm

{\footnotesize
\immediate\write18{sh ./vc > vcline.tex}
\begin{center}
Git: \input{vcline.tex}
\\
(Recopier la ligne ci-dessus dans tout commentaire sur ce document)
\end{center}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pretolerance=8000
\tolerance=50000


%
%
%

\section{Calculabilité}


\exercice\ (${\star}$)

On considère la fonction $f\colon \mathbb{N} \to \mathbb{N}$ qui à $n
\in \mathbb{N}$ associe le $n$-ième chiffre de l'écriture décimale de
$\sqrt{2} \approx 1.41421356237309504880\ldots$, c'est-à-dire $f(0) =
1$, $f(1) = 4$, $f(2) = 1$, $f(3) = 4$, etc.

La fonction $f$ est-elle calculable ?  Est-elle primitive récursive ?
On expliquera précisément pourquoi.

\begin{corrige}
On peut calculer $f(n)$ selon l'algorithme suivant : calculer $N =
10^n$, puis pour $i$ allant de $0$ à $2N$, tester si $i^2 \leq 2 N^2 <
(i+1)^2$ : lorsque c'est le cas (et ce sera le cas pour exactement un
$i$ dans l'intervalle), renvoyer le reste $i\% 10$ de la division
euclidienne de $i$ par $10$.

Cet algorithme est correct car l'inégalité $i^2 \leq 2 N^2 < (i+1)^2$
testé équivaut à $\frac{i}{N} \leq \sqrt{2} < \frac{i+1}{N}$, ce qui
se produit pour exactement un $i$, à savoir $\lfloor \sqrt{2}\times
10^n \rfloor$ (on peut arrêter la boucle à $2N$ car $\sqrt{2} < 2$),
et que le dernier chiffre décimal $i\% 10$ de ce $i$ est le $n$-ième
chiffre de l'écriture décimale de $\sqrt{2}$.

D'autre part, comme on a donné un algorithme explicite, $f$ est
calculable.  Mieux : comme la boucle utilisée est bornée \textit{a
  priori}, $f$ est primitive récursive.
\end{corrige}

%

\exercice\ (${\star}$)

Supposons que $A \subseteq B \subseteq \mathbb{N}$.  \textbf{(1)} Si
$B$ est décidable, peut-on conclure que $A$ est décidable ?
\textbf{(2)} Si $A$ est décidable, peut-on conclure que $B$ est
décidable ?

\begin{corrige}
La réponse est non dans les deux cas : pour le voir appelons $H := \{e
\in \mathbb{N} : \varphi_e(0)\downarrow\}$ (disons) : il est
indécidable par une des variations du problème de l'arrêt (ou par le
théorème de Rice).  Le fait que $H \subseteq \mathbb{N}$ avec
$\mathbb{N}$ décidable réfute (1), et le fait que $\varnothing
\subseteq H$ avec $\varnothing$ décidable réfute (2).
\end{corrige}

%

\exercice\label{exercice-image-calculable-est-semi-decidable}\ (${\star}$)

\textbf{(1)} Soit $f\colon \mathbb{N} \to \mathbb{N}$ totale
calculable.  Montrer que l'image $f(\mathbb{N})$ (c'est-à-dire $\{f(i)
: i\in\mathbb{N}\}$) est semi-décidable.

\textbf{(2)} Soit $f\colon \mathbb{N} \to \mathbb{N}$ totale
calculable et strictement croissante.  Montrer que l'image
$f(\mathbb{N})$ (c'est-à-dire $\{f(i) : i\in\mathbb{N}\}$) est
décidable.

\begin{corrige}
\textbf{(1)} L'algorithme évident suivant semi-décide $\{f(i) :
i\in\mathbb{N}\}$ : donné $m \in \mathbb{N}$ l'entier à tester, faire
une boucle infinie sur $i$ parcourant les entiers naturels et pour
chacun, tester si $f(i) = m$ : si c'est le cas, terminer et répondre
« oui », sinon, continuer la boucle.

\textbf{(2)} L'algorithme évident suivant décide $\{f(i) :
i\in\mathbb{N}\}$ : donné $m \in \mathbb{N}$ l'entier à tester, faire
une boucle pour $i$ parcourant les entiers naturels, et pour chacun,
tester si $f(i) = m$ : si c'est le cas, terminer et répondre « oui »,
tandis que si $f(i) > m$, terminer et répondre « non », sinon,
continuer la boucle.  La boucle termine en temps fini car $f(i) \geq
i$ (inégalité claire pour une fonction $\mathbb{N} \to \mathbb{N}$
strictement croissante) et notamment la boucle s'arrêtera au pire
lorsque $i$ vaut $m+1$.  (Du coup, si on préfère, on peut réécrire la
boucle potentiellement infinie comme une boucle pour $i$ allant de $0$
à $m$.)
\end{corrige}

%

\exercice\ (${\star}$)

Montrer que l'ensemble des $e\in \mathbb{N}$ tels que
$\varphi^{(1)}_e(0) = \varphi^{(1)}_e(1)$ (rappel : ceci signifie que
\emph{soit} $\varphi^{(1)}_e(0) \downarrow$ et $\varphi^{(1)}_e(1)
\downarrow$ et $\varphi^{(1)}_e(0) = \varphi^{(1)}_e(1)$, \emph{soit}
$\varphi^{(1)}_e(0) \uparrow$ et $\varphi^{(1)}_e(1) \uparrow$) n'est
pas décidable.

\begin{corrige}
L'ensemble $F$ des fonctions partielles calculables $f\colon
\mathbb{N} \dasharrow \mathbb{N}$ telles que $f(0) = f(1)$ n'est ni
vide (la fonction totale constante de valeur $0$ est dans $F$) ni
plein (la fonction totale identité n'est pas dans $F$).  D'après le
théorème de Rice, l'ensemble des $e$ tels que $\varphi^{(1)}_e \in F$
est indécidable : c'est exactement ce qui était demandé.
\end{corrige}

%

\exercice\label{exercice-image-fonction-partielle-calculable}\ (${\star}{\star}$)

\textbf{(1)} Soit $B \subseteq \mathbb{N}$ semi-décidable et non-vide.
Montrer qu'il existe $f\colon \mathbb{N} \to \mathbb{N}$ totale
calculable telle que $f(\mathbb{N}) = B$.

(\emph{Indication :} si $m_0 \in B$ et si $B$ est semi-décidé par le
$e$-ième programme, i.e., $B = \{m : \varphi_e(m)\downarrow\}$, on
définira $\tilde f\colon \mathbb{N}^2 \to \mathbb{N}$ par $\tilde
f(n,m) = m$ si $T(n,e,\dbllangle m\dblrangle)$, où $T(n,e,v)$ est
comme dans le théorème de la forme normale de Kleene\footnote{Rappel :
  c'est-à-dire que $T(n,e,\dbllangle \underline{x}\dblrangle)$
  signifie : « $n$ est le code d'un arbre de calcul de
  $\varphi_e(\underline{x})$ termine » (le résultat
  $\varphi_e(\underline{x})$ du calcul étant alors noté $U(n)$).}, et
$\tilde f(n,m) = m_0$ sinon.  Alternativement, si on préfère raisonner
sur les machines de Turing : si $B$ est semi-décidé par la machine de
Turing $\mathscr{M}$, on définit $\tilde f(n,m) = m$ si $\mathscr{M}$
termine sur l'entrée $m$ en $\leq n$ étapes d'exécution, et $\tilde
f(n,m) = m_0$ sinon.)

\textbf{(2)} Soit $f\colon \mathbb{N} \dasharrow \mathbb{N}$ partielle
calculable.  Montrer que l'image $f(\mathbb{N})$ (c'est-à-dire $\{f(i)
: i\in\mathbb{N} \text{~et~} f(i){\downarrow}\}$) est semi-décidable.
(\emph{Indication :} chercher à formaliser l'idée de lancer les
calculs des différents $f(i)$ « en parallèle ».)

\begin{corrige}
\textbf{(1)} La fonction $\tilde f \colon \mathbb{N}^2 \to \mathbb{N}$
définie dans l'indication est calculable (et d'ailleurs même primitive
récursive) : si on a pris la définition avec $T$ le fait que $T$ soit
p.r. fait partie du théorème de la forme normale ; si on préfère les
machines de Turing, c'est le fait qu'on peut simuler l'exécution de
$\mathscr{M}$ pour $n$ étapes (de façon p.r.).  Et on voit qu'on a
$\tilde f(n,m) \in B$ dans tous les cas : donc $\tilde f(\mathbb{N}^2)
\subseteq B$.  Mais réciproquement, si $m \in B$, alors
$\varphi_e(m)\downarrow$ (si on préfère les machines de Turing,
$\mathscr{M}$ termine sur l'entrée $m$), et ceci dit précisément qu'il
existe $n$ tel que $\tilde f(n,m) = m$, donc $m \in \tilde
f(\mathbb{N}^2)$ ; bref, $B \subseteq \tilde f(\mathbb{N}^2)$.  On a
donc $\tilde f(\mathbb{N}^2) = B$ par double inclusion.  Quitte à
remplacer $\tilde f \colon \mathbb{N}^2 \to \mathbb{N}, (n,m) \mapsto
\tilde f(n,m)$ par $f \colon \mathbb{N} \to \mathbb{N}, \langle
n,m\rangle \mapsto \tilde f(n,m)$, on a $f(\mathbb{N}) = B$.

\textbf{(2)} Ici on ne peut pas appliquer bêtement l'algorithme exposé
dans l'exercice \ref{exercice-image-calculable-est-semi-decidable}
question (1) car si le calcul de $f(i)$ ne termine pas, il bloquera
tous les suivants.  Il faut donc mener le calcul des $f(i)$ « en
parallèle ».  On va procéder par énumération des couples $(n,i)$ et
lancer le calcul de $f(i)$ sur $n$ étapes.

Plus précisément : considérons l'algorithme suivant : il prend en
entrée un entier $m$ dont il s'agit de semi-décider s'il appartient à
$f(\mathbb{N})$.  L'algorithme fait une boucle infinie sur $p$
parcourant les entiers naturels : chaque $p$ est d'abord décodé comme
le code $\langle n,i\rangle$ d'un couple d'entiers naturels (ceci est
bien sûr calculable).  On teste si l'exécution de $f(i)$ termine en
$\leq n$ étapes (ou, si on préfère le théorème de la forme de normale,
on teste si $T(n,e,\dbllangle i\dblrangle)$, où $e$ est un code de la
fonction $f = \varphi^{(1)}_e$) : si oui, et si la valeur $f(i)$
calculée est égale à l'entier $m$ considéré, on termine en renvoyant
« oui », sinon on continue la boucle.

Cet algorithme semi-décide bien $f(\mathbb{N})$ : en effet, dire que
$m \in f(\mathbb{N})$, équivaut à l'existence de $i$ tel que
$f(i){\downarrow} = m$, c'est-à-dire à l'existence de $n,i$ tel que
l'algorithme renverra « oui » en testant $\langle n,i\rangle$.

(\emph{Variante :} plutôt qu'utiliser le codage des couples $\langle
n,i\rangle$, on peut aussi faire ainsi : on parcourt les entiers
naturels $p$ en une boucle infini et pour chacun on effectue deux
boucles bornées pour $0\leq n\leq p$ et $0\leq i\leq p$ : peu
importent les bornes précises, l'important est que pour $p$ assez
grand on va finir par tester le couple $(n,i)$.)
\end{corrige}

%

\exercice\label{exercice-indices-fonctions-totales}\ (${\star}$)

Soit
\[
T := \{e \in \mathbb{N} : \varphi^{(1)}_e\text{~est~totale}\}
\]
l'ensemble des codes des fonctions générales récursives totales
(c'est-à-dire telles que $\forall
n\in\mathbb{N}.\,(\varphi^{(1)}_e(n)\downarrow)$).  On se propose de
montrer que ni $T$ ni son complémentaire $\complement T$ ne sont
semi-décidables.

\textbf{(1)} Montrer en guise d'échauffement que $T$ n'est pas
décidable.

\textbf{(2)} Soit $H := \{d \in \mathbb{N} :
\varphi^{(1)}_d(0)\downarrow\}$ (variante du problème de l'arrêt).
Rappeler brièvement pourquoi $H$ est semi-décidable mais non
décidable, et pourquoi son complémentair $\complement H$ n'est pas
semi-décidable.

\textbf{(3)} Montrer qu'il existe une fonction $\rho \colon \mathbb{N}
\to \mathbb{N}$ (totale) calculable (d'ailleurs même p.r.) telle que
$\varphi^{(1)}_d(0)\downarrow$ si et seulement si
$\varphi^{(1)}_{\rho(d)}$ est totale (\emph{indication :} on pourra
par exemple construire un programme $e$ qui ignore son argument et qui
simule $d$ sur l'entrée $0$).  Reformuler cette affirmation comme une
réduction.  En déduire que le complémentaire $\complement T$ de $T$
n'est pas semi-décidable.

\textbf{(4)} Montrer qu'il existe une fonction $\sigma \colon
\mathbb{N} \to \mathbb{N}$ (totale) calculable (d'ailleurs même p.r.)
telle que $\varphi^{(1)}_d(0)\downarrow$ si et seulement si
$\varphi^{(1)}_{\sigma(d)}$ \emph{n'est pas} totale
(\emph{indication :} on pourra par exemple construire un programme $e$
qui lance $d$ sur l'entrée $0$ pour un nombre d'étapes donné en
argument, et fait une boucle infinie si cette exécution termine avant
le temps imparti).  Reformuler cette affirmation comme une réduction.
En déduire que $T$ n'est pas semi-décidable.

\begin{corrige}
On notera « $\varphi$ » pour « $\varphi^{(1)}$ » de manière à alléger
les notations.

\textbf{(1)} L'ensemble des fonctions calculables $\mathbb{N}
\dasharrow \mathbb{N}$ qui sont en fait totales ($\mathbb{N} \to
\mathbb{N}$) n'est ni vide (la fonction totale constante de valeur $0$
est dedans) ni plein (la fonction nulle part définie n'est pas
dedans).  D'après le théorème de Rice, l'ensemble $T$ des $e$ tels que
$\varphi_e$ soit totale est indécidable : c'est exactement ce qui
était demandé.

\textbf{(2)} Toujours d'après le théorème de Rice, ou comme variante
du problème de l'arrêt (qui s'y ramène par le théorème s-m-n),
l'ensemble $H$ n'est pas décidable.  Il est cependant semi-décidable
par universalité (on peut lancer l'exécution de $e$ sur l'entrée $0$
et, si elle termine, renvoyer « oui »).  On en déduit que $\complement
H$ n'est pas semi-décidable (car si $H$ et $\complement H$ étaient
semi-décidables, $H$ serait décidable, ce qu'il n'est pas).

\textbf{(3)} Considérons la fonction $\rho$ qui prend en entrée un
programme $d$ (supposé d'un argument) et renvoie le programme $e =:
\rho(d)$ (toujours d'un argument) qui ignore son argument et exécute
$d$ sur l'entrée $0$ : essentiellement par le théorème s-m-n, cette
fonction $\rho$ est totale calculable (d'ailleurs même p.r.).  Par
définition, on a $\varphi_{\rho(d)}(n) = \varphi_d(0)$ (rappelons que
ceci signifie que chacun est défini ssi l'autre l'est et, le cas
échéant, que ces valeurs sont égales).  Notamment, si
$\varphi_d(0)\downarrow$, alors $\varphi_{\rho(d)}$ est totale (et
constante !), tandis que si $\varphi_d(0)\uparrow$, alors
$\varphi_{\rho(d)}$ n'est nulle part définie (donc certainement pas
totale).

Bref, on a construit $\rho\colon\mathbb{N}\to\mathbb{N}$ totale
calculable telle que $d \in H$ si et seulement si $\rho(d) \in T$, ou,
ce qui revient au même, $d \in \complement H$ si et seulement si
$\rho(d) \in \complement T$.  En termes de réductions, ceci signifie
$H \mathrel{\leq_\mathrm{m}} T$, ou, ce qui revient au même,
$\complement H \mathrel{\leq_\mathrm{m}} \complement T$ (le symbole
« $\mathrel{\leq_\mathrm{m}}$ » désignant la réduction many-to-one).
Comme $\complement H$ n'est pas semi-décidable, $\complement T$ ne
l'est pas non plus.

\emph{Remarque :} On n'est pas obligé d'utiliser le terme de
« réduction many-to-one » pour argumenter que $\complement T$ n'est
pas semi-décidable : on peut simplement dire « supposant par l'absurde
que $\complement T$ soit semi-décidable, on pourrait semi-décider
$\complement H$ de la façon suivante : donné $d$, on calcule
$\rho(d)$, on semi-décide si $\rho(d) \in \complement T$ et, si c'est
le cas, on termine en renvoyant “oui” ; or ce n'est pas possible, d'où
une contradiction ».

\textbf{(4)} Considérons la fonction $\sigma$ qui prend en entrée un
programme $d$ (supposé d'un argument) et renvoie le programme $e :=
\sigma(d)$ (toujours d'un argument) défini ainsi : le programme $e$
prend en entrée un nombre $n$ et exécute le programme $d$ sur l'entrée
$0$ pendant $\leq n$ étapes (mettons que ce soient des machines de
Turing, sinon remplacer cet argument par une recherche d'arbre de
calcul parmi les entiers naturels de $0$ à $n$) : si cette exécution a
terminé en $\leq n$ étapes, alors $d$ effectue une boucle infinie,
sinon $d$ termine (et renvoie, disons, $1729$).

Il n'y a pas de difficulté à coder ce programme $e$ (on rappelle
qu'exécuter un programme donné sur $\leq n$ étapes est calculable,
d'ailleurs même primitif récursif), et de plus la fonction $\sigma$
transformant $d$ en $e$ est elle-même calculable (et d'ailleurs elle
aussi primitive récursive).

Par définition de $e := \sigma(d)$, la fonction $\varphi_e$ est :
\begin{itemize}
\item soit définie pour tout $n$ (et de valeur $1729$), ce qui se
  produit exatement lorsque l'exécution de $d$ ne termine jamais,
  i.e. $\varphi_d(0) \uparrow$,
\item soit définie jusqu'en un certain $n$ et non définie après, ce
  qui se produit exactement lorsque l'exécution de $d$ termine en un
  certain nombre d'étapes, i.e. $\varphi_d(0) \downarrow$.
\end{itemize}
En particulier, si $\varphi_d(0)\uparrow$, alors $\varphi_{\sigma(d)}$
est totale (et constante !), tandis que si $\varphi_d(0)\downarrow$,
alors $\varphi_{\sigma(d)}$ n'est pas totale.

Bref, on a construit $\sigma\colon\mathbb{N}\to\mathbb{N}$ totale
calculable telle que $d \in H$ si et seulement si $\sigma(d) \not\in
T$, ou, ce qui revient au même, $d \in \complement H$ si et seulement
si $\sigma(d) \in T$.  En termes de réductions, ceci signifie
$\complement H \mathrel{\leq_\mathrm{m}} T$.  Comme $\complement H$
n'est pas semi-décidable, $T$ ne l'est pas non plus.

\emph{Remarque :} Comme dans la question précédente, on n'est pas
obligé d'utiliser le terme de « réduction many-to-one » pour
argumenter que $T$ n'est pas semi-décidable : on peut simplement dire
« supposant par l'absurde que $T$ soit semi-décidable, on pourrait
semi-décider $\complement H$ de la façon suivante : donné $d$, on
calcule $\sigma(d)$, on semi-décide si $\sigma(d) \in T$ et, si c'est
le cas, on termine en renvoyant “oui” ; or ce n'est pas possible, d'où
une contradiction ».
\end{corrige}

%

\exercice\label{exercice-graphe-calculable}\ (${\star}{\star}$)

Soit $f\colon \mathbb{N} \to \mathbb{N}$ une fonction totale : montrer
qu'il y a équivalence entre les affirmations suivantes :
\begin{enumerate}
\item la fonction $f$ est calculable,
\item le graphe $\Gamma_f := \{(i,f(i)) : i\in\mathbb{N}\} =
  \{(i,q)\in\mathbb{N}^2 : q=f(i)\}$ 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 (1), on pourra chercher une façon de tester
en parallèle un nombre croissant de valeurs de $q$ de manière à
s'arrêter si l'une quelconque convient.  On peut s'inspirer de
l'exercice \ref{exercice-image-fonction-partielle-calculable}
question (2).)

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

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

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

Reste à montrer que (3) implique (1) : supposons maintenant qu'on ait
un algorithme $\mathscr{S}$ qui « semi-décide » $\Gamma_f$ (i.e.,
donnés $(i,q)$, termine en temps fini et répond « oui » si $q=f(i)$,
et ne termine pas sinon), et on cherche à écrire un algorithme qui,
donné $i$ en entrée, calcule $f(i)$.  Notre algorithme
(appelons-le $\mathscr{F}$) fait une boucle infinie sur $p$ parcourant
les entiers naturels : chaque $p$ est d'abord décodé comme le code
$\langle n,q\rangle$ d'un couple d'entiers naturels.  On teste si
l'exécution de $\mathscr{S}$ sur l'entrée $(i,q)$ termine en $\leq n$
étapes (ce qui est bien faisable algorithmiquement) : si oui, on
renvoie la valeur $q$ ; sinon, on continue la boucle.

Cet algorithme $\mathscr{F}$ termine toujours : en effet, pour chaque
$i$ donné, il existe $q$ tel que $(i,q) \in \Gamma_f$, à savoir $q =
f(i)$ ; et alors l'algorithme $\mathscr{S}$ doit terminer sur l'entrée
$(i,q)$, c'est-à-dire que pour $n$ assez grand, il termine en $\leq n$
étapes, donc $\mathscr{F}$ terminera lorsqu'il arrivera à $p = \langle
n,q\rangle$, et il renverra bien $q$ comme annoncé.  On a donc montré
que $f$ était calculable puisqu'on a exhibé un algorithme qui la
calcule.

(Comme dans
l'exercice \ref{exercice-image-fonction-partielle-calculable}, on peut
utiliser le $T$ de la forme normale de Kleene au lieu de parler
d'« étapes » d'exécution d'une machine de Turing.  Aussi, plutôt
qu'utiliser le codage des couples $\langle n,i\rangle$, on peut
préférer faire ainsi : on parcourt les entiers naturels $p$ en une
boucle infini et pour chacun on effectue deux boucles bornées pour
$0\leq n\leq p$ et $0\leq q\leq p$ : peu importent les bornes
précises, l'important est que pour $p$ assez grand on va finir par
tester le couple $(n,q)$.)
\end{corrige}

%

\exercice\label{exercice-reconnaitre-fonctions-p-r}\ (${\star}{\star}$)

Si $e \mapsto \psi^{(1)}_e$ est la numérotation standard des fonctions
primitives récursives en une variable (= d'arité $1$) et $e \mapsto
\varphi^{(1)}_e$ celle des fonctions générales récursives en une
variable, on considère les ensembles
\[
M := \{e \in \mathbb{N} : \psi^{(1)}_e\text{~définie}\}
\]
\[
N := \{e \in \mathbb{N} : \exists
e'\in\mathbb{N}.(\psi^{(1)}_{e'}\text{~définie~et~}\varphi^{(1)}_e =
\psi^{(1)}_{e'})\}
\]
Expliquer informellement ce que signifient ces deux ensembles (en
insistant sur le rapport entre eux), dire s'il y a une inclusion de
l'un dans l'autre, et dire si l'un ou l'autre est décidable.

\begin{corrige}
L'ensemble $M$ est l'ensemble des codes valables de fonction
primitives récursives, c'est-à-dire de codes légitimes dans le langage
primitif récursif ; l'ensemble $N$ qui est $\{e \in \mathbb{N} :
\varphi^{(1)}_e \text{~est~p.r.}\}$ est l'ensemble des codes de
fonctions générales récursives qui s'avèrent être primitives
récursives (même si ce n'est pas forcément manifeste sur le
programme).  Si on préfère, $M$ est l'ensemble des \emph{intentions}
primitives récursives, alors que $N$ est l'ensemble des intentions
dont l'\emph{extension} est primitive récursive ; \textit{grosso
  modo}, l'appartenance à $M$ se lit sur le code de la fonction, celle
à $N$ se lit sur les valeurs de la fonction.

Manifestement, $M \subseteq N$, car si $\psi^{(1)}_e$ est définie, on
a $\varphi^{(1)}_e = \psi^{(1)}_e$ (la définition des fonctions
générales récursives \emph{étend} celle des fonctions p.r.).
L'inclusion dans l'autre sens ne vaut pas : on peut calculer la
fonction constante nulle en faisant une boucle infinie, ce qui fournit
un code $e$ tel que $\varphi^{(1)}_e$ est primitive récursive (donc
$e\in N$) et pourtant $\psi^{(1)}_e$ n'est pas définie (donc $e\not\in
M$).

L'ensemble $M$ est décidable : on peut décider de façon algorithmique
si $e$ est un numéro valable de fonction primitive récursive (i.e., si
$\psi^{(1)}_e$ est définie), il s'agit pour cela simplement de
« décoder » $e$ et de vérifier qu'il suit les conventions utilisées
pour numéroter les fonctions primitives récursives (pour être très
précis, le décodage termine parce que le code d'une liste est
supérieur à tout élément de cette liste).

L'ensemble $N$ n'est pas décidable : si $F$ désigne l'ensemble des
fonctions p.r. $\mathbb{N} \to \mathbb{N}$ (c'est-à-dire l'image de
$M$ par $e \mapsto \psi^{(1)}_e$), alors $N$ est $\{e\in\mathbb{N} :
\varphi^{(1)}_e \in F\}$, et comme $F$ n'est ni vide ni l'ensemble de
toutes les fonctions générales récursives, le théorème de Rice dit
exactement que $N$ est indécidable.
\end{corrige}

%

\exercice\label{exercice-diagonalisation-0-1-fonctions-p-r}\ (${\star}{\star}{\star}$)

On considère la fonction $f\colon \mathbb{N}^2 \to \mathbb{N}$ qui à
$(e,x)$ associe $1$ si $\psi^{(1)}_e(x) = 0$ et $0$ sinon (y compris
si $\psi^{(1)}_e$ n'est pas définie), où $e \mapsto \psi^{(1)}_e$ est
la numérotation standard des fonctions primitives récursives en une
variable (= d'arité $1$).

La fonction $f$ est-elle calculable ?  Est-elle primitive récursive ?
On expliquera précisément pourquoi.  (On s'inspirera de résultats vus
en cours.)  Cela changerait-il si on inversait les valeurs $0$ et $1$
dans $f$ ?

\begin{corrige}
La fonction $f$ est calculable.  En effet,
\begin{itemize}
\item on peut décider de façon algorithmique si $e$ est un numéro
  valable de fonction primitive récursive (i.e., si $\psi^{(1)}_e$ est
  définie), il s'agit pour cela simplement de « décoder » $e$ et de
  vérifier qu'il suit les conventions utilisées pour numéroter les
  fonctions primitives récursives (pour être très précis, le décodage
  termine parce que le code d'une liste est supérieur à tout élément
  de cette liste) ;
\item lorsque c'est le cas, on peut calculer $\psi^{(1)}_e(x)$ car
  quand elle est définie elle coïncide avec $\varphi^{(1)}_e(x)$
  (numérotation des fonctions générales récursives), dont on sait
  qu'il est calculable (universalité) ;
\item calculer $f$ ne pose ensuite aucune difficulté.
\end{itemize}

Montrons que $f$ n'est pas primitive récursive (on a vu en cours que
$(e,x) \mapsto \psi^{(1)}_e(x)$ ne l'est pas, mais cela ne suffit
pas : on pourrait imaginer que le fait qu'il soit égal à $0$ soit plus
facile à tester).  Pour cela, supposons par l'absurde que $f$ soit
primitive récursive.  Par le théorème de récursion de Kleene, il
existe $e$ tel que $\psi^{(1)}_e(x) = f(e,x)$.  Or la définition même
de $f$ fait que $f(e,x) \neq \psi^{(1)}_e(x)$ dans tous les cas : ceci
est une contradiction.  Donc $f$ n'est pas primitive récursive.

Cela ne change bien sûr rien d'échanger $0$ et $1$, c'est-à-dire de
remplacer $f$ par $1 - f$ (l'une est récursive, resp. p.r., ssi
l'autre l'est), mais la démonstration ne se serait pas appliquée telle
quelle.
\end{corrige}

%

\exercice\ (${\star}{\star}{\star}$)

Soit
\[
Z := \{e \in \mathbb{N} : \exists n \in \mathbb{N}.\, (\psi^{(1)}_e(n) = 0)\}
\]
l'ensemble des codes $e$ des fonctions p.r. $\mathbb{N} \to
\mathbb{N}$ qui prennent (au moins une fois) la valeur $0$ (ici, $e
\mapsto \psi^{(1)}_e$ est la numérotation standard des fonctions
primitives récursives en une variable).

Montrer que $Z$ est semi-décidable.  Montrer qu'il n'est pas
décidable.

\begin{corrige}
Comme dans le début du corrigé de
l'exercice \ref{exercice-diagonalisation-0-1-fonctions-p-r}, on
explique qu'on peut décider si $\psi^{(1)}_e(n)\downarrow$ (il s'agit
juste de vérifier si $e$ est un code valable de fonction p.r.) et, une
fois ce point vérifié, si $\psi^{(1)}_e(n) = 0$ (on peut calculer
$\psi^{(1)}_e(n) = \varphi^{(1)}_e(n)$ par universalité des fonctions
générales récursives).

Dès lors, pour semi-décider si $e \in Z$, il suffit de faire une
boucle infinie pour $n$ parcourant les entiers naturels, décider si
$\psi^{(1)}_e(n) = 0$ pour chacun, et si l'un d'eux est effectivement
nul, terminer et renvoyer « oui », sinon on continue la boucle.  Ceci
montre que $Z$ est semi-décidable.

Montrons qu'il n'est pas décidable : pour cela, on va ramener le
problème de l'arrêt à $Z$.  C'est en fait essentiellement ce que fait
le théorème de la forme normale de Kleene : en effet, considérons
$(p,x)$ dont il s'agit de décider si $\varphi^{(1)}_p(x)\downarrow$ :
d'après le théorème de la forme normale, ceci se produit si et
seulement si il existe un (entier codant un) arbre de calcul $n$
attestant que $\varphi^{(1)}_p(x)\downarrow$, ce qu'on écrit
$T(n,p,\dbllangle x\dblrangle)$, où $T$ est un prédicat p.r.,
c'est-à-dire qu'il s'écrit $t(n,p,\dbllangle x\dblrangle) = 0$ pour
une certaine fonction p.r. $t$ (qui teste si $n$ code un arbre de
calcul valable pour $\varphi^{(1)}_p(x)$ et renvoie $0$ si c'est le
cas, $1$ sinon).  On a ainsi $\varphi^{(1)}_p(x)\downarrow$ ssi
$\exists n\in\mathbb{N}.\, (t(n,p,\dbllangle x\dblrangle) = 0)$.
Maintenant, d'après le théorème s-m-n, on peut calculer de façon
p.r. en $p$ et $x$ le code $\rho(p,x)$ d'une fonction p.r. telle que
$\psi^{(1)}_{\rho(p,x)}(n) = t(n,p,\dbllangle x\dblrangle)$, et
d'après ce qui a été dit juste avant, on a $\rho(p,x) \in Z$,
c'est-à-dire $\exists n\in\mathbb{N}.\, (t(n,p,\dbllangle x\dblrangle)
= 0)$, se produit si et seulement si $\varphi^{(1)}_p(x)\downarrow$,
c'est-à-dire $(p,x) \in \mathscr{H}$ (où $\mathscr{H} := \{(p,x) \in
\mathbb{N}^2 : \varphi^{(1)}_p(x)\downarrow\}$ désigne le problème de
l'arrêt).  Ceci constitue une réduction \textit{many-to-one} de
$\mathscr{H}$ à $Z$, donc $Z$ ne peut pas être décidable : en effet,
si $Z$ était décidable, pour tester si $(p,x) \in \mathscr{H}$ il
suffirait de tester si $\rho(p,x) \in Z$, donc le problème de l'arrêt
serait décidable, ce qui n'est pas le cas.

(De nouveau, si on n'aime pas le théorème de la forme normale de
Kleene, on peut faire ça avec des étapes de machine de Turing :
appeler $t(n,p,x)$ la fonction qui renvoie $0$ si la machine de Turing
codée par $p$ termine en $\leq n$ étapes à partir de la configuration
initiale codée par $x$, et $1$ sinon : le reste du raisonnement est
essentiellement identique.)
\end{corrige}

%

%% \exercice\ (${\star}$)

%% Montrer qu'il existe une machine de Turing qui, quand on la lance sur
%% la configuration vierge (c'est-à-dire un ruban vierge et dans
%% l'état $1$), termine après avoir écrit son propre programme sur sa
%% bande\footnote{Par exemple avec la convention suivante : les
%% instructions du programme $\delta \colon \{1,\ldots,m\} \times \{0,1\}
%% \to \{0,\ldots,m\} \times \{0,1\} \times \{\texttt{L},\texttt{R}\}$
%% sont écrites de la gauche vers la droite dans l'ordre $\delta(1,0)$,
%% $\delta(1,1)$, $\delta(2,0)$, $\delta(2,1)$, etc., chacune étant
%% écrite sous forme du nouvel état, du nouveau symbole, et de la
%% direction codée par $\texttt{L}\mapsto 0, \texttt{R}\mapsto 1$, tous
%% les trois en unaire séparés par des $0$.}

%

\exercice\ (${\star}{\star}$)

Soit $f \colon\mathbb{N} \to \mathbb{N}$ une fonction calculable par
une machine de Turing en \emph{complexité d'espace} primitive
récursive : cela signifie qu'il existe $p \colon\mathbb{N} \to
\mathbb{N}$ primitive récursive et une machine de Turing $\mathscr{M}$
telle que si on lui présente $n \in \mathbb{N}$ en entrée (écrit avec
les conventions usuelles, c'est-à-dire en unaire sur la bande), la
machine s'arrête en temps fini en ayant écrit $f(n)$ sur la bande, et
de plus le nombre de cases de la bande que la tête de lecture a
parcourues est $\leq p(n)$ (c'est-à-dire que $\mathscr{M}$ a utilisé
$\leq p(n)$ cellules mémoire pour faire le calcul).

On veut montrer que $f$ elle-même est primitive récursive
(c'est-à-dire qu'une fonction calculable en complexité d'espace
p.r. est elle-même p.r., de la même manière qu'une fonction calculable
en complexité en temps p.r. est elle-même p.r.).

\textbf{(1)} Si $\mathscr{M}$ a $\leq m$ états, montrer que le calcul
de $f(n)$ par $\mathscr{M}$ ne peut faire intervenir qu'au plus
$m\times p(n)\times 2^{p(n)+n}$ configurations différentes (on rappelle
qu'une \emph{configuration} est la donnée d'un état, d'une position de
la tête, et de la valeur de chaque cellule du ruban).

\textbf{(2)} En déduire que le calcul de $f(n)$ par $\mathscr{M}$
termine en au plus $m\times p(n)\times 2^{p(n)+n}$ étapes
(\textit{indication :} sinon le calcul bouclerait indéfiniment, et on
a supposé que ce n'était pas le cas).

\textbf{(3)} En déduire que $f$ est primitive récursive.

\begin{corrige}
\textbf{(1)} Une configuration de l'exécution de $\mathscr{M}$ est la
donnée d'un état parmi au plus $m$, d'une position de la tête parmi au
plus $p(n)$ (puisque la tête visite au plus ce nombre de cellules), et
de la valeur de chaque cellule du ruban ; or au plus $p(n)+n$ cellules
peuvent contenir un $1$ (à n'importe quel moment de l'exécution), car
la tête n'en viiste qu'au plus $p(n)$ et au plus $n$ portent un $1$
initialement : il y a donc au plus $2^{p(n)+n}$ configurations
possibles du ruban, et au plus $m\times p(n)\times 2^{p(n)+n}$
configurations de l'ensemble de la machine.

\textbf{(2)} Si $\mathscr{M}$ retombe sur une configuration exacte
qu'elle a déjà exécutée, elle exécutera de nouveau exactement les
mêmes instructions et ne retombera indéfiniment sur cette
configuration sans jamais finir.  Comme on a supposé que le calcul
terminait, c'est qu'il doit parcourir des configurations toutes
distinctes, donc termine en au plus $m\times p(n)\times 2^{p(n)+n}$
étapes.

\textbf{(3)} On vient de montrer que le calcul de $f$ par
$\mathscr{M}$ es fait en temps au plus $m\times p(n)\times
2^{p(n)+n}$.  Mais ceci est une fonction p.r. de $n$ (car $p$ l'est,
et que $k \mapsto 2^k$ l'est, et que $m$ est une constante ici).  Donc
$f$ est calculée en complexité en temps p.r., donc elle est elle-même
p.r.
\end{corrige}

%

\exercice\label{exercice-tableaux-fonctions-p-r}\ (${\star}{\star}$)

On s'intéresse à des tableaux d'entiers naturels, indicés par les
entiers naturels, dont toutes les valeurs valent $0$ sauf un nombre
fini (i.e., des fonctions $\tau \colon \mathbb{N} \to \mathbb{N}$ dont
le support $\{i \in \mathbb{N} : \tau(i) \neq 0\}$ est fini).  Un tel
tableau $\tau$ sera Gödel-codé comme un entier naturel sous la forme
(disons) de la liste $\dbllangle \langle i_1,\tau(i_1)\rangle, \ldots,
\langle i_k,\tau(i_k)\rangle \dblrangle$ où $i_1 < i_2 < \cdots < i_k$
sont les indices tels que la valeur $\tau(i)$ dans le tableau à cet
indice soit $\neq 0$.

\textbf{(1)} Sans rentrer dans énormément de détails, expliquer
pourquoi la fonction $(\tau,i) \mapsto \tau(i)$ (« lecture du tableau
$\tau$ à l'indice $i$ ») et $(\tau,i,v) \mapsto \tau'$ où $\tau'(j) =
\tau(j)$ sauf $\tau'(i) = v$ (« modification du tableau $\tau$ à
l'indice $i$ pour y mettre la valeur $v$ ») sont primitives
récursives.

\textbf{(2)} Sans rentrer dans énormément de détails, en déduire
pourquoi, du coup, un algorithme primitif récursif peut utiliser un
tableau dans une boucle où elle lit et écrit des valeurs arbitraires
du tableau.

\begin{corrige}
\textbf{(1)} La fonction de lecture $(\tau,i) \mapsto \tau(i)$
consiste à parcourir tous les couples de la liste $\dbllangle \langle
i_1,\tau(i_1)\rangle, \ldots, \langle i_k,\tau(i_k)\rangle \dblrangle$
qui représente le tableau et, pour chacune, comparer $i$ à la première
composante et, s'il y a égalité, renvoyer la seconde composante, sinon
renvoyer $0$.  La boucle est bornée a priori car elle parcourt une
liste connue (dont la longueur est majorée par le numéro qui la code).
Comme le décodage des couples (et donc des listes) est primitif
récursif, tout ceci est primitif récursif.

La fonction d'écriture $(\tau,i,v) \mapsto \tau'$ consiste à parcourir
la liste qui représente le tableau, et si on a $i = i_r$, modifier la
seconde composante du couple correspondant, tandis que si on a $i_r <
i < i_{r+1}$ (ou $i < i_0$ ou $i > i_k$) on insère un nouveau couple :
comme l'encodage et le décodage des couples (et notamment l'insertion
d'un élément dans une liste) sont primitifs récursifs, tout ceci est
primitif récursif.

\textbf{(2)} Le tableau est codé sous forme d'entier naturel comme on
l'a dit, donc il devient une simple variable de boucle, sur laquelle
on peut effectuer des lectures et modifications par les fonctions
qu'on a expliquées (et qui sont primitives récursives).  Le fait de
disposer d'une variable dans une boucle (bornée !) pour un algorithme
primitif récursif est bien permis (essentiellement par la récursion
primitive, qui permet précisément la modification d'une variable à
chaque tour de boucle).
\end{corrige}

%

\exercice\ (${\star}{\star}{\star}$)

On rappelle la définition de la fonction d'Ackermann $A\colon
\mathbb{N}^3 \to \mathbb{N}$ :
\[
\begin{aligned}
A(m,n,0) &= m+n \\
A(m,0,1) &= 0 \\
A(m,0,k) &= 1\text{~si~}k\geq 2 \\
A(m,n+1,k+1) &= A(m,\,A(m,n,k+1),\,k)
\end{aligned}
\]
On a vu en cours que cette fonction est calculable mais non primitive
récursive.  On admettra sans discussion que $A(m,n,k)$ est croissante
en chaque variable dès que $m\geq 2$ et $n\geq 2$.  On pourra aussi
utiliser sans discussion les faits suivants :
\[
\begin{aligned}
A(m,n,1) &= mn \\
A(m,n,2) &= m^n \\
A(0,n,k) &= ((n+1)\%2)\text{~si~}k\geq 3 \\
A(1,n,k) &= 1\text{~si~}k\geq 2 \\
A(m,1,k) &= m\text{~si~}k\geq 1 \\
A(2,2,k) &= 4 \\
\end{aligned}
\]

On considérera aussi la \emph{fonction indicatrice du graphe} de $A$,
c'est-à-dire la fonction $B\colon \mathbb{N}^4 \to \mathbb{N}$ :
\[
\begin{array}{ll}
B(m,n,k,v) = 1 &\text{~si~}v = A(m,n,k) \\
B(m,n,k,v) = 0 &\text{~sinon} \\
\end{array}
\]

\textbf{(1)} Écrire un algorithme qui calcule $A(m,n,k)$ à partir de
$m$, $n$, $k$ et d'un \emph{majorant} $b$ de $A(m,n,k)$ selon le
principe suivant : si $m\geq 2$ et $n\geq 2$, pour chaque $\ell$
allant de $0$ à $k$ et chaque $i$ allant de $0$ à $b$ (bien noter :
c'est $b$ et pas $n$ ici), on calcule $A(m,i,\ell)$, et on la stocke
dans la case $(i,\ell)$ d'un tableau, à condition que les valeurs déjà
calculées et contenues dans le tableau permettent de la calculer (pour
les petites valeurs $m\leq 1$ ou $n\leq 1$ on utilise les formules
données ci-dessus ; sinon, on essaye d'utiliser la formule de
récurrence en consultant le tableau).  Expliquer pourquoi la valeur
$A(m,n,k)$ est bien calculée par cet algorithme.

\textbf{(2)} Expliquer pourquoi l'algorithme qu'on a écrit en (1) est
primitif récursif (on pourra prendre connaissance des conclusions de
l'exercice \ref{exercice-tableaux-fonctions-p-r}).

\textbf{(3)} En déduire que la fonction $B$ est primitive récursive.

(Autrement dit, on ne peut pas calculer $A$ par un algorithme p.r.,
mais on peut \emph{vérifier} sa valeur, si elle est donnée en entrée,
par un tel algorithme.)

\begin{corrige}
\textbf{(1)} On commence par remarquer que les « petites valeurs »
$m\leq 1$ ou $n\leq 1$ de la fonction d'Ackermann, se calculent
facilement par des formules de l'énoncé.

L'algorithme calculant $A(m,n,k)$ est alors le suivant.  Si $m\leq 1$
ou $n\leq 1$ on peut facilement calculer la valeur comme on vient de
l'expliquer, donc on se place dans le cas $m \geq 2$ et $n \geq 2$.
(Notons aussi que toute valeur de la fonction d'Ackermann pour $m\geq
1$ est non nulle, ce qui nous permet d'utiliser $0$ pour représenter
« non calculé » dans le tableau.)

On initialise un tableau $\tau$ de deux indices, $i,\ell$,
initialement rempli de $0$, qui servira à stocker les valeurs de la
fonction d'Ackermann $A(m,i,\ell)$.  Pour chaque $\ell$ allant de $0$
à $k$ et chaque $i$ allant de $0$ à $b$, on calcule $A(m,i,\ell)$ de
la manière suivante : si $i\leq 1$ ou $\ell=0$ on utilise la formule
évoquée ci-dessus et stocke la valeur dans le tableau ; sinon, on
consulte le tableau en $(i-1,\ell)$ et, si cette valeur $u$ est
définie (c'est-à-dire non nulle), on consulte le tableau en
$(u,\ell-1)$ et, si cette valeur $w$ est définie, on la stocke dans le
tableau en $(i,\ell)$.

Autrement dit :
\begin{itemize}
\item si $m\leq 1$ ou $n\leq 1$, calculer facilement $A(m,n,k)$ et
  renvoyer sa valeur ; sinon :
\item initialiser un tableau $\tau$ (d'indices $i$ allant de $0$ à $b$
  et $\ell$ allant de $0$ à $k$, et initialement rempli de $0$),
\item pour $\ell$ allant de $0$ à $k$,
\begin{itemize}
\item pour $i$ allant de $0$ à $b$,
\begin{itemize}
\item si $i\leq 1$ ou $\ell=0$, calculer facilement $w := A(m,i,\ell)$
  et stocker $\tau(i,\ell) \leftarrow w$,
\item sinon, consulter $u := \tau(i-1,\ell)$,
\item si $u \neq 0$, consulter $w := \tau(u,\ell-1)$,
\item si $w \neq 0$, stocker $\tau(i,\ell) \leftarrow w$.
\end{itemize}
\end{itemize}
\item finalement : renvoyer $\tau(k,n)$ si elle est $>0$, sinon
  « échec ».
\end{itemize}

En Python, avec de petites variations :

{\tt
\noindent
def ackermann\_small(m,n,k):\\
\strut\quad \# Returns A(m,n,k) value if m<=1 or n<=1 or k<=2\\
\strut\quad if k==0: return m+n\\
\strut\quad if k==1: return m*n\\
\strut\quad if k==2: return m**n\\
\strut\quad if n==0: return 1\\
\strut\quad if n==1: return m\\
\strut\quad if m==0: return (n+1)\%2\\
\strut\quad if m==1: return 1\\
\\
def ackermann\_bounded(m,n,k,b):\\
\strut\quad \# Returns A(m,n,k) (at least) if its value is <=b\\
\strut\quad if m<=1 or n<=1: return ackermann\_small(m,n,k)\\
\strut\quad tab = \{\}\\
\strut\quad for l in range(k+1):\\
\strut\quad \strut\quad for i in range(b+1):\\
\strut\quad \strut\quad \strut\quad if l==0 or i<=1:\\
\strut\quad \strut\quad \strut\quad \strut\quad w = ackermann\_small(m,i,l)\\
\strut\quad \strut\quad \strut\quad \strut\quad tab[(i,l)] = w\\
\strut\quad \strut\quad \strut\quad else:\\
\strut\quad \strut\quad \strut\quad \strut\quad if (i-1,l) in tab:\\
\strut\quad \strut\quad \strut\quad \strut\quad \strut\quad u = tab[(i-1,l)]\\
\strut\quad \strut\quad \strut\quad \strut\quad \strut\quad if (u,l-1) in tab:\\
\strut\quad \strut\quad \strut\quad \strut\quad \strut\quad \strut\quad w = tab[(u,l-1)]\\
\strut\quad \strut\quad \strut\quad \strut\quad \strut\quad \strut\quad tab[(i,l)] = w\\
\strut\quad if (n,k) in tab:\\
\strut\quad \strut\quad return tab[(n,k)]
}

L'algorithme repose sur la formule $A(m,i,\ell) =
A(m,A(m,i-1,\ell),\ell-1)$ (qui est une simple réécriture de la
troisième ligne de la définition), où on a appelé $u = A(m,i-1,\ell)$
et $w = A(m,u,\ell-1)$ : cete formule montre que si les valeurs
$(i-1,\ell)$ et $(u,\ell-1)$ sont trouvées dans le tableau, la valeur
$A(m,i,\ell)$ sera correctement calculée.

Or on montre par récurrence sur $\ell$ et $i$ que toutes les valeurs
pour lesquelles $A(m,i,\ell) \leq b$ (ou bien $i\leq 1$ ou $\ell=0$)
seront effectivement calculées par l'algorithme : en effet, si
$A(m,i,\ell) \leq b$, alors par la croissance en la deuxième variable
de la fonction d'Ackermann, $u := A(m,i-1,\ell)$ est lui-même $\leq b$
(ou alors $i=1$), donc aura été correctement calculé avant
$A(m,i,\ell)$, et $A(m,u,\ell-1)$ aura été calculé et stocké dans le
tableau puisque la boucle sur $\ell$ est extérieure à celle sur $i$ et
que la valeur $u$ est dans les bornes de la boucle sur $i$.

En particulier, si $b$ est un majorant de la valeur $A(m,n,k)$ qu'on
cherchait, alors l'algorithme renvoie $A(m,n,k)$.

\textbf{(2)} L'algorithme qu'on a décrit ci-dessus ne fait aucun appel
récursif et n'utilise que des boucles bornées (deux boucles
imbriquées).  L'utilisation d'un tableau est justifiée par
l'exercice \ref{exercice-tableaux-fonctions-p-r}.  On a donc bien
défini une fonction primitive récursive.

\textbf{(3)} L'algorithme qu'on a décrit calcule de façon primitive
récursive en $m,n,k,b$ la valeur $A(m,n,k)$ si tant est que celle-ci
est $\leq b$.  En particulier, pour calculer $B(m,n,k,v)$ il suffit
d'appliquer cet algorithme à $m,n,k,v$ (c'est-à-dire avec $v$ lui-même
comme borne) et, s'il renvoie une valeur $w$, tester si $v=w$ : si
c'est le cas on renvoie « oui » (enfin, $1$), sinon, ou si
l'algorithme n'a pas réussi à caluler $A(m,n,k)$ on renvoie « non »
(enfin, $0$).  La fonction $B$ est donc primitive récursive.

(On dit parfois abusivement que la fonction d'Ackermann a un graphe
primitif récursif pour dire que la fonction indicatrice de son graphe
est primitive récursive.  On comparera à
l'exercice \ref{exercice-graphe-calculable} d'après lequel une
fonction dont la fonction indicatrice du graphe est calculable, i.e.,
générale récursive, est elle-même calculable, i.e., générale
récursive.)
\end{corrige}


%
%
%
\end{document}