L'usage de calculatrices électroniques de poche à alimentation autonome, non imprimantes et sans document d'accompagnement, est autorisé. Cependant, une seule calculatrice à la fois est admise sur la table ou le poste de travail, et aucun échange n'est autorisé entre les candidats.

Ordres pour la terminaison des programmes et suites de Goodstein

Les différentes parties du problème sont largement indépendantes les unes des autres. Plus précisément, la partie 1 introduit les concepts; à l'exception des questions 8 et 9 , la partie 3 est indépendante de la partie 2 . Les premières questions ( 1 à 5 ) de la partie 4 ne font référence ni à la partie 2 , ni à la partie 3 . La partie 5 peut être résolue indépendamment des autres.

1 Introduction

En informatique, la terminaison des programmes (c'est-à-dire le fait qu'un programme se termine pour tout valeur d'entrée qu'il peut prendre) est une propriété fondamentale que l'on cherche à démontrer. Dans ce problème, nous allons étudier des relations que l'on appelle «bien fondées» et qui permettent de garantir la terminaison des programmes. En fait, les relations bien fondées que nous examinerons sont puissantes et nous permettront d'aborder un problème de logique intéressant : les suites de Goodstein. Pour cela nous avons besoin de représenter les naturels par des arbres, ce qui nous conduira à de l'arithmétique sur ces représentations.
Ordres Une relation

sur

est irréflexive si elle vérifie

. Un ordre strict est une relation irréflexive et transitive.

est un ordre strict,

est la relation

, c'est-à-dire la relation telle que

si et seulement si

. Un ordre strict est total si pour tout

on a

.
Une suite

d'éléments de

telle que

est dite

-décroissante. Une relation

est bien fondée sur

(on dit aussi que (

) est bien fondé) s'il n'existe pas de suite infinie

-décroissante d'éléments de

.
S'il existe, le minimum d'un ensemble

pour un ordre strict

est l'élément

tel que

Si elle existe, la borne supérieure d'un ensemble

pour un ordre

est

Le successeur

d'un élément

est

si ce minimum existe.

Listes Une liste de

est une structure de données informatique qui implante une suite finie d'éléments de

. Si ses éléments sont dans l'ordre

, elle s'écrit

. On construit les listes à partir de la liste vide [ ] par ajout d'éléments en tête de liste. Le premier élément d'une liste non vide

s'écrit hd(

), la liste obtenue à partir de

par suppression de son premier élément s'écrit

. L'ajout en tête de

de l'élément

s'écrit

. On a les relations suivantes :

tandis que

ne sont pas définis.
Arbres binaires Un arbre binaire est soit

, soit

où

sont eux-mêmes des arbres binaires. Dans la suite du problème, nous dirons simplement «arbre». Un arbre peut aussi être dessiné

Ainsi l'arbre

se dessine :

Les arbres forment l'ensemble

. La taille d'un arbre est le nombre d'occurrences de l'opérateur

qu'il contient. Nous admettrons le principe d'induction structurelle sur

qui permet de prouver par récurrence une propriété

pour tous les arbres.
La relation sur-arbre strict

est définie par

si et seulement si ou ou ou .

On admettra que

est un ordre strict.
Nous généralisons le principe d'induction structurelle aux triplets d'arbres en définissant sur

l'ordre

qui dit que

si et seulement si

et l'une au moins des inégalités est stricte. Ce principe s'énonce :

Remarque: Si dans une preuve par induction structurelle, le prédicat

contient plusieurs occurrences d'arbres, le candidat veillera à indiquer clairement sur quelle variable il fait son induction.

Présentation des algorithmes Quand un algorithme est demandé, le candidat n'est pas supposé produire un programme complet, mais un texte suffisamment et clairement documenté pour qu'un programme puisse être extrait sans difficulté. Le candidat pourra aussi bien utiliser un style proche de celui de la figure 1 qu'un style proche du langage de programmation CAML. Les correcteurs attacheront de l'importance au fait que les candidats aient abordé les questions algorithmiques.

Montrer qu'un ordre strict est antisymétrique.
On considère la fonction qui prend un arbre et une liste d'arbres et qui retourne

si la liste est vide
et si la liste n'est pas vide.

Formellement,

Dans la suite, nous utiliserons la fonction renv(l) définie par

.
Donner un algorithme qui calcule la fonction

2 Décomposition complète d'un nombre dans une base et suites de Goodstein

Étant donné un naturel

appelé base, l'exposant maximal d'un naturel

est le nombre

tel que

tandis que la décomposition complète de

dans la base

est

soit 0 si ,
soit la somme de et de , où est la décomposition complète de l'exposant maximal de dans la base , et où est la décomposition complète de .
Ainsi la décomposition complète de 83 dans la base 3 est obtenue à partir de

où

est la décomposition complète de 4 .

Donner la décomposition complète de 4 et celle de 83 .
Étant donné une base , montrer que la décomposition complète d'un naturel permet d'exprimer ce naturel à l'aide de l'addition, de l'exponentiation et de 0 et des ces opérations seulement.
On associe un arbre à la décomposition complète d'un naturel de la façon suivante :

Pour le naturel 83 et la base 3 , on obtient

Quel est l'arbre associé respectivement à 1 , à

, à

et à

dans toutes les bases? Soit decl la fonction qui prend un couple de naturels

(une base) et

(un naturel) et retourne un couple de naturels (

) tel que

Donner la définition formelle (à la manière de la fonction

de la question 1.1) de la fonction arbre qui associe directement à (

) l'arbre donné par

.
4. Dans l'algorithme de la figure 1 qui calcule la fonction arbre quelle est la nature (ou le

arbre(b, n) =
    pile := [(0,[])]
    courant := (n,[])
    tant que pile ≠ [] faire
        k, liste_res := courant
        si k\not=0 alors (m,r) := dec1(b,k)
                pile := (r, liste_res) :: pile;
                courant := (m,[]))
        sinon (q,l):= hd(pile)
            pile := tl(pile)
            courant := (q, renv(liste_res) :: l))
    fait
k, liste_res := courant
retourne(hd(liste_res))

Fig. 1 -
type) des objets contenus dans pile, courant et liste_res? Que contient liste_res dans les étapes de l'algorithme et quand l'algorithme se termine?
5. On considère la fonction erbra qui prend un couple formé d'une base

et d'un arbre

et donne le naturel qui correspond à l'arbre

dans la base

; autrement dit on a

. Donner un algorithme récursif qui calcule la fonction erbra. Quelle est la complexité de cet algorithme en fonction de la taille de l'arbre, si l'on suppose que la somme et l'exponentiation se font en temps constant?
6. Les suites de Goodstein commencent au rang 2 . Si

est défini à partir de

ainsi :

, quels sont

? Montrer que pour la suite où

il existe un

tel

.
7. Donner un algorithme directement dérivé des algorithmes précédents qui prend deux

et construit l'arbre arbre

. Cet algorithme pourra utiliser directement l'addition sur les naturels. Nous appellerons l'opération que cet algorithme implante l'addition des arbres en base

. Donner ensuite un algorithme qui permet d'additionner des arbres en base

en n'utilisant que des additions sur des nombres inférieurs à

.
8. Donner un algorithme qui prend deux arbres arbre

et arbre

et construit l'arbre arbre

où

est le produit des naturels

et qui n'utilise que des opérations sur des nombres inférieurs à

3 Un ordre sur les arbres

La relation

est définie par

si et seulement si
ou bien
ou bien et

Montrer que est un ordre strict.
Montrer par un contrexemple que ( ) n'est pas bien fondé.
Si et sont des ordres stricts bien fondés, on définit par

Montrer que

est un ordre strict bien fondé.
4. Soit A un alphabet muni d'une relation d'ordre

. Un mot

sur

est décroissant si pour

on a

. Les mots décroissants forment l'ensemble A

.
L'ordre du dictionnaire sur les mots est défini par

(où

est le mot vide).

si et seulement si

ou bien

.
Montrer que (

) est bien fondé si et seulement si

est bien fondé.
5. Un arbre

est ordonné si

sont ordonnés et si

. De plus,

est ordonné et

est ordonné si

est ordonné. Les arbres ordonnés forment l'ensemble

. Montrer que pour tout arbre

le successeur

existe.
6.

étant un arbre, montrer par induction structurelle que la relation

est bien fondée sur l'ensemble

. Indication : on montrera que l'ensemble ordonné

est isomorphe à un ensemble, ordonné par un ordre du dictionnaire, de mots ordonnés.
7. Conclure de la question 6 que

est bien fondée sur

.
8. Montrer pour tous les naturels

, que d'une part arbre

et que d'autre part,

implique

.
9. Montrer que toute suite de Goodstein atteint 0 , autrement dit pour toute suite de Goodstein

, il existe un naturel

, tel que

4 Un autre ordre sur les arbres

On définit sur

une relation par

ou bien et ,
ou bien et et l'une des trois conditions suivantes est satisfaite:

et ,
et ,
ou .
Montrer que est un ordre strict total sur .
Montrer que implique . Autrement dit que si est un sur-arbre strict de alors .
Donner un algorithme qui étant donnés deux arbres et retourne vrai si et faux sinon.
Montrer que pour tout élément de le successeur existe. Peut-on exprimer à partir de et ?
Pour prouver que est bien fondée sur , on va raisonner par l'absurde. S'il existe une suite infinie -décroissante, il en existe une que nous notons et qui est plus petite que les autres au sens suivant :

est un plus petit arbre par la taille, qui commence une suite infinie décroissante.
Si l'on suppose construits, est un plus petit arbre par la taille en ( )-ème position pour une suite infinie décroissante qui commence par .
Montrer que cette suite ne contient pas . Montrer qu'on peut construire une suite infinie décroissante plus petite que la suite , d'où une contradiction.

Montrer que l'identité est une application croissante de vers .
Déduire de la question précédente que la bonne fondation de implique la bonne fondation de . On a ainsi une nouvelle démonstration de la bonne fondation de ( ).
On considère la fonction croissante qui satisfait les conditions suivantes :

La dernière identité doit se lire
«si sup

existe, alors sup

existe et

sup

.
Que valent les quantités suivantes?
(a)

?
(b)

?
(c)

5 Un ordre sur les mots

Dans cette partie, on va étudier une catégorie d'ordres bien fondés qui possèdent certaines propriétés ainsi qu'un ordre sur les mots.

Une suite

dans laquelle il existe

tels que

est dite bonne.
Une sous-suite de

est donnée par une application

croissante, autrement dit la sous-suite est celle des

. Une suite

est faiblement croissante si

. Une antichaîne de (

) est un sous ensemble

tel que pour tout

on a

Montrer que les quatre propriétés suivantes sur un ordre strict ( ) sont équivalentes.
(a) Tout ordre strict qui satisfait est bien fondé.
(b) est bien fondé et sans antichaîne infinie.
(c) Toute suite est bonne,
(d) De toute suite on peut extraire une sous-suite faiblement croissante.

Un ordre qui satisfait ces conditions équivalentes est dit unbel ordre.
2. On définit l'ordre

sur

qui étend l'ordre

sur

impliquent

implique

.
Montrer que (

) est un bel ordre si et seulement si (

) est un bel ordre. Indication : On pourra utiliser une technique de démonstration qui s'inspire de celle de la question 4.5.