Université BORDEAUX 1 | U.F.R. Mathématiques et Informatique |
Epreuve de J.Bétréma | 19 décembre 2005 |
Durée: 3 heures
Tous documents interdits.
Un corrigé est disponible ci-dessous.
A tout entier x on associe sa racine carrée entière, notée r ( x ) , c'est-à-dire le plus grand entier t tel que t2 ≤ x ; on pose :
φ ( x ) = x - t2 , avec t = r ( x ) .
A tout ensemble d'entiers A on associe l'ensemble B = φ ( A ) défini par :
B = { φ ( x ) | x ∈ A } .
Soit B un ensemble récursivement énumérable, énuméré par une fonction calculable totale g. Construire un ensemble A récursivement énumérable tel que B = φ ( A ) ; donner la fonction f qui énumère A.
Note : il y a beaucoup (et même une infinité) de réponses possibles à cette question (expliquer pourquoi) ; donner une réponse aussi simple que possible.
Un corrigé est disponible ci-dessous.
Une machine de Turing ne dispose pas de mémoire à accès direct (RAM); l'objet de cet exercice est de construire des machines de Turing qui simulent les instructions LOAD et STORE d'un processeur classique. Pour cela on suppose la bande divisée en trois parties :
Les trois parties de la bande sont consécutives, et séparées par le symbole '#'. Pour simplifier les notations, on suppose que l'alphabet utilisé dans le registre de transfert et dans la RAM est constitué des cinq symboles 0, 1, a, b et c. La machine qui simule l'instruction LOAD doit copier les k cellules de la RAM d'adresse de base n (c'est-à-dire les cellules numérotées n, n + 1, … , n + k - 1) dans le registre de transfert ; la machine qui simule l'instruction STORE doit copier le contenu du registre de transfert dans les k cellules de la RAM d'adresse de base n. Les autres cellules doivent être inchangées lorsque la machine s'arrête, à l'exception de l'adresse (dont on autorise la destruction).
Attention : les règles des machines doivent être écrites et commentées très clairement ; une réponse qui ne respecte pas cette consigne risque de ne rapporter aucun point. La position de la tête de lecture en début de programme peut être choisie librement, mais doit être indiquée sur la copie en début de réponse.
Un corrigé est disponible ci-dessous.
Certains langages de programmation comportent une instruction de filtrage qui permet de raisonner sur un objet selon sa structure. Appliquée à un entier n qui soit vaut 0, soit est le successeur d'un entier m, cette instruction peut s'écrire :
match n with 0 => t | succ m => f ( m ) end
où t désigne une expression quelconque, et f une procédure. Attention : ne pas confondre avec une définition récursive — on ne suppose pas que l'expression ci-dessus définit f ( n ). Ecrire un λ-terme match tel que :
match 0 T F
→ … → T
match 1 T F
→ … → F 0
match 2 T F
→ … → F 1
match 3 T F
→ … → F 2
etc.
quels que soient les λ-termes T et F (la flèche → désigne comme d'habitude une β-réduction). Note : on pourra utiliser le λ-terme pred (prédécesseur) sans le redéfinir ; par contre on évitera si possible d'utiliser le λ-terme iszero (il existe une solution élégante sans lui).
Un corrigé est disponible ci-dessous.
On rappelle que le problème de la couverture d'un graphe, appelé traditionnellement VERTEX-COVER, est le suivant :
On cherche à associer à une instance de VERTEX-COVER une formule booléenne Φ satisfiable si et seulement si le graphe G possède une couverture de taille k. Pour cela on représente un ensemble Γ de sommets par n variables booléennes x1 … xn , où xi vaut 1 si le sommet numéro i appartient à Γ, 0 sinon.
Dans la suite on part inversement d'un ensemble Φ de clauses de taille 3, auquel on veut associer une instance de VERTEX-COVER. Pour cela on construit un graphe comme suit :
De façon générale, si la formule Φ comporte m clauses (de taille 3) et n variables, le graphe associé G comporte 3 m + 2 n sommets. Questions :
Corrigé.
Remarque sur le barème : les notes entre 10 et 30 ont été ajustées pour que la note finale soit comprise entre 10 et 18.
Voir l'énoncé ci-dessus.
(2 points) La fonction r est évidemment calculable, donc φ aussi. Si A est décidable, voici une procédure qui énumère les éléments de B :
for (x = 0; ; x++) if (x ∈ A) afficher φ(x);
On peut aussi dire qu'un ensemble décidable est récursivement énumérable, et que donc il existe une fonction calculable f qui énumère A ; B est alors énuméré par g = φ ο f .
Note : le but de l'exercice est de montrer que, paradoxalement, on n'a pas : A décidable ⇒ B décidable ; donc tout argument qui prétend montrer dans cette question que B est décidable, est erroné.
(2 points) φ ( x ) = b ⇔ x = b + t2 , avec x < (t + 1)2 ! D'où la condition sur t :
b < 2 t + 1 , soit : ( b - 1 ) / 2 < t .
Par exemble pour b = 11, la valeur minimale de t est 6, d'où :
{ x | φ ( x ) = 11 } = { 11 + 62 = 47, 11 + 72 = 60, 11 + 82 = 75, … }
L'essentiel est de comprendre qu'on a φ ( b + t2 ) = b, dès que t est suffisamment grand ! Ce résultat peut se voir directement sur l'exemple ci-dessus ; c'est mieux de savoir calculer la valeur minimale de t, mais ce n'est pas indispensable pour la suite. On peut remarquer aussi que la fonction φ est surjective.
Note : ces calculs ne demandent pas de connaissance mathématique exceptionnelle ! Commencer par regarder les premières valeurs de φ n'est pas indispensable, mais c'est une bonne idée, bien meilleure en tout cas qu'une liste de formules ou d'affirmations vagues et souvent fausses.
(2 points) La question précédente montre qu'on a toujours φ ( b + b2 ) = b. Une réponse simple à la question posée est donc :
f (n) = g (n) + g (n)2
Il y a une infinité d'autres réponses, de la forme g (n) + t2 , dès que t est supérieur à g (n) / 2. En utilisant seulement la surjectivité de φ on peut aussi choisir :
f (n) = min { x | φ (x) = g (n) }
Note : certains étudiants ont énuméré l'ensemble φ-1 ( B ) = { x | φ ( x ) ∈ B }, ce qui est possible, à condition de ne pas parler de la fonction inverse de φ (qui n'existe manifestement pas, voir question précédente). Cette interprétation n'est pas dans l'esprit de l'énoncé, qui spécifie construire un ensemble A, et précise qu'il y a beaucoup de réponses possibles ; elle ne permet pas de résoudre la question 6.
(3 points) Exercice classique vu en TD : comme f est croissante, dès que f (n) dépasse x on sait que x n'appartient pas à E = Val ( f ). D'où la procédure qui calcule la fonction caractéristique de E :
int fc (int x) { for (int n = 0; f(n) < x; n++); return f(n) == x; }
qu'on peut écrire aussi :
int fc (int x) { for (int n = 0; ; n++) { if ( f(n) == x) return 1; if ( f(n) > x) return 0; } }
Cette procédure termine toujours, car f est strictement croissante.
(2 points) Le premier exemple d'ensemble récursivement énumérable et indécidable est celui des procédures (sans argument) qui terminent ; ensuite on peut donner des variantes :
{ ( p, x ) | p (x) termine }
{ p | ∃ x : p (x) termine }
On peut citer aussi l'ensemble des propriétés démontrables en arithmétique (théorème de Gödel). Mais les exemples tirés du théorème de Rice (procédures qui calculent l'identité, procédures qui calculent une fonction totale, etc.) sont souvent faux : ce sont bien des ensembles indécidables, mais ils ne sont pas récursivement énumérables. Ce n'est pas un résultat évident à démontrer, mais on voit mal comment énumérer les procédures qui possèdent telle ou telle propriété pour tout argument x.
Note : dire que le problème de l'arrêt est indécidable est correct ; mais dire que le problème de l'arrêt n'est pas récursivement énumérable est absurde, strictement parlant : on peut énumérer un ensemble, pas un problème !
(3 points) Il faut utiliser les questions 2, 3 et 4, c'est-à-dire construire A comme à la question 3, en se débrouillant pour que la fonction f qui énumère A soit croissante (ainsi A sera décidable). Notons :
b0 = g (0) , b1 = g (1) , … , bn = g (n) , …
les élements de B. On commence par choisir le premier élément de A :
a0 = f (0) tel que φ ( a0 ) = b0
Ensuite on choisit a1 = f (1) supérieur à a0 : c'est possible car d'après la question 2 n'importe quel
a1 = b1 + t12
vérifie φ ( a1 ) = b1 dès que t1 est suffisamment grand. Et ainsi de suite :
an = f (n) = bn + tn2
où tn est suffisamment grand pour qu'on ait à la fois φ ( an ) = bn et f (n - 1) < f (n).
Voir l'énoncé ci-dessus.
(5 points) On suppose que l'état initial est numéroté 0, et que la tête de lecture est positionnée en début de RAM (cellule d'adresse 0). Le principe du programme est d'itérer le traitement suivant : décrémenter l'adresse, et déplacer d'une unité vers la droite une marque dans la RAM. Lorsque l'adresse devient nulle, la cellule marquée est celle dont il faut copier la valeur dans le registre.
La réponse ci-dessous est complète, et peut être testée sur un simulateur de machine de Turing, mais dans les conditions de l'examen des "etc." peuvent remplacer des traitements similaires (par exemple les états 112 à 115 sont similaires à l'état 111). De même, la présentation des règles peut différer de celle ci-dessous, pourvu qu'elle soit claire.
Dans ce corrigé, les cinq composants de chaque règle sont codés comme suit :
Beaucoup d'étudiants ont pensé que la RAM ne contient que des 0 et des 1 ; ils ont utilisé les symboles supplémentaires a, b, c pour marquer la position atteinte dans la RAM, et pour mémoriser le symbole à transférer dans le registre (en se demandant à quoi pouvait bien servir le symbole c…) ; cette interprétation est contraire à la lettre de l'énoncé, mais ne change pas l'esprit de l'exercice, et a l'avantage de raccourcir le programme : elle a donc été considérée comme correcte.
// Marquer la position dans la RAM 0 a 10 A G 0 b 10 B G 0 c 10 C G 0 0 10 D G 0 1 10 E G 0 . 99 . = // erreur d'adresse // Retourner en fin d'adresse 10 # 11 # G 10 - 10 - G 11 # 20 # G 11 - 11 - G // Décrémenter l'adresse 20 0 20 1 G 20 1 30 0 D 20 . 100 . D // adresse nulle // Aller en début de RAM 30 # 31 # D 30 - 30 - D 31 # 40 # D 31 - 31 - D // Déplacer la marque dans la RAM 40 A 0 a D 40 B 0 b D 40 C 0 c D 40 D 0 0 D 40 E 0 1 D 40 - 40 - D // Itération terminée : atteindre // et mémoriser le symbole marqué 100 # 101 # D 100 - 100 - D 101 # 110 # D 101 - 101 - D 110 A 111 a G 110 B 112 b G 110 C 113 c G 110 D 114 0 G 110 E 115 1 G 110 - 110 - D // Ecrire dans le registre 111 # 121 # G 111 - 111 - G 121 - 200 a = // succès 112 # 122 # G 112 - 112 - G 122 - 200 b = // succès 113 # 123 # G 113 - 113 - G 123 - 200 c = // succès 114 # 124 # G 114 - 114 - G 124 - 200 0 = // succès 115 # 125 # G 115 - 115 - G 125 - 200 1 = // succès
Variante équivalente : au lieu de marquer par une majuscule seulement la position courante dans la RAM, on peut marquer toutes les positions jusqu'à la position courante, et effacer toutes les marques (en rétablissant les symboles d'origine) en fin de programme.
(2 points) Le principe est le même, jusqu'à ce que l'adresse devienne nulle (état 100) ; il faut alors lire et mémoriser le registre, puis le copier dans la RAM à l'emplacement marqué (par une majuscule). Voici les nouvelles règles pour les états de numéro supérieur à 100 :
// Aller en début de registre 100 # 110 # D 100 - 100 - D // Lire et mémoriser le symbole 110 a 111 - D 110 b 112 - D 110 c 113 - D 110 d 114 - D 110 e 115 - D // Aller en début de RAM 111 # 121 # G 111 - 111 - D 112 # 122 # G 112 - 112 - D 113 # 123 # G 113 - 113 - D 114 # 124 # G 114 - 114 - D 115 # 124 # G 115 - 114 - D // Atteindre la cellule marquée // et copier le registre 121 A 200 a = 121 B 200 a = 121 C 200 a = 121 D 200 a = 121 E 200 a = 121 - 121 - D 122 A 200 b = 122 B 200 b = 122 C 200 b = 122 D 200 b = 122 E 200 b = 122 - 122 - D 123 A 200 c = 123 B 200 c = 123 C 200 c = 123 D 200 c = 123 E 200 c = 123 - 123 - D 124 A 200 0 = 124 B 200 0 = 124 C 200 0 = 124 D 200 0 = 124 E 200 0 = 124 - 124 - D 125 A 200 1 = 125 B 200 1 = 125 C 200 1 = 125 D 200 1 = 125 E 200 1 = 125 - 125 - D
Bien entendu, inutile sur la copie de traiter en détail les cinq cas similaires, mais il doit être clair que le symbole écrit dépend de l'état — qui dépend lui-même du symbole lu dans le registre — et non du symbole marqué (par une majuscule).
Note : on peut se passer des états intermédiaires 111 à 115 si l'on suppose le registre de taille 1.
(3 points) Dans l'état 110, il faut à nouveau déplacer la marque (majuscule) ; on remplit le registre avec une boucle : écrire dans le registre, déplacer la marque, écrire dans le registre, et ainsi de suite jusqu'à atteindre la fin du registre (caractère '#'). Dans les conditions de l'examen, aucun étudiant n'a eu le temps de donner les détails, mais les voici (on suppose le registre blanc, sinon ajouter des instructions en début de programme pour le nettoyer) :
// Atteindre, mémoriser et déplacer // le symbole marqué 110 A 109 A D 110 B 109 B D 110 C 109 C D 110 D 109 D D 110 E 109 E D 110 - 110 - D 109 a 109 A G 109 b 109 B G 109 c 109 C G 109 0 109 D G 109 1 109 E G 109 . 99 . = // erreur adresse 109 A 111 a G 109 B 112 b G 109 C 113 c G 109 D 114 0 G 109 E 115 1 G // Ecrire dans le registre 111 # 121 # G 111 - 111 - G 121 . 121 . G 121 - 131 - D 131 - 140 a D 112 # 122 # G 112 - 112 - G 122 . 122 . G 122 - 132 - D 132 - 140 b D 113 # 123 # G 113 - 113 - G 123 . 123 . G 123 - 133 - D 133 - 140 c D 114 # 124 # G 114 - 114 - G 124 . 124 . G 124 - 134 - D 134 - 140 0 D 115 # 125 # G 115 - 115 - G 125 . 125 . G 125 - 135 - D 135 - 140 1 D 140 # 150 # D // fin écriture 140 . 141 . D 141 . 141 . D 141 # 110 # D // rétablir la cellule marquée 150 A 200 a G 150 B 200 b G 150 C 200 c G 150 D 200 0 G 150 E 200 1 G 150 - 150 - D
Voir l'énoncé ci-dessus.
(3 points) En utilisant iszero la traduction en λ-calcul est directe :
match = λ n t f . iszero n t ( f ( pred n ) )
Attention aux parenthèses ! On a bien :
match 0 T F
→
iszero 0 T ( F ( pred 0 ) )
→ true T ( F ( pred 0 ) )
→ T
match 1 T F
→
iszero 1 T ( F ( pred 1 ) )
→ false T ( F 0 )
→ F 0
match 2 T F
→
iszero 2 T ( F ( pred 2 ) )
→ false T ( F 1 )
→ F 1 , etc.
Note : cette partie de l'exercice est facile, et pour obtenir les trois points il ne suffit pas de donner la valeur de match, il faut aussi écrire quelques réductions comme ci-dessus.
(2 points) En utilisant la définition d'un entier de Church on peut écrire directement :
match = λ n t f . n ( λ x . f ( pred n ) ) t
On a :
match 0 T F → 0 M T → T
avec M = λ x . F ( pred 0 ) ; ensuite :
match 1 T F → 1 M T → M T → ( λ x . F 0 ) T → F 0
avec M = λ x . F ( pred 1 ) → λ x . F 0 ; le terme M représente une fonction constante, qui ignore son argument. De même :
match 2 T F → 2 M T → M ( M T ) → ( λ x . F 1 ) ( M T ) → F 1
avec M = λ x . F ( pred 2 ) → λ x . F 1 (fonction constante, qui ignore son argument).
Note : le terme λ x . f ( pred n ) peut se noter aussi true ( f ( pred n ) ). Plus précisément, pour tout terme G on a :
true G = ( λ x y . x ) G → λ y . G
et ce dernier terme représente la fonction constante égale à G.
Voir l'énoncé ci-dessus.
On représente un ensemble Γ de sommets par n variables booléennes x1 … xn , où xi vaut 1 si le sommet numéro i appartient à Γ, 0 sinon. On construit alors une formule Φ qui exprime que Γ est une couverture de la façon suivante :
(2 points) Il faut aussi exprimer que la taille de Γ est correcte, autrement dit :
Σ xi = k
Il faut donc représenter le résultat de n - 1 additions par un ensemble de clauses ; c'est possible en représentant chaque nombre sur m bits, où m est le logarithme binaire de n (arrondi par excès), et en représentant chaque addition par une cascade d'additionneurs élémentaires (comme les électroniciens le font), qui admettent chacun en entrée trois bits (deux plus la retenue) et en sortie deux bits.
(1 point) Voici comment on peut coder les deux clauses :
( x1 ∨ ¬ x3 ∨ x4 ) , ( ¬ x1 ∨ x2 ∨ x4 )
Note : l'ordre des composantes d'une clause est sans importance (la disjonction est commutative), donc il en est de même pour l'ordre des sommets dans un triangle.
(3 points) Choisissons par exemple x1 = 1, x2 = 0, x3 = 1, x4 = 1 ; la clause :
x1 ∨ ¬ x3 ∨ x4
est satisfaite car x1 = x4 = 1, et la clause :
¬ x1 ∨ x2 ∨ x4
est satisfaite car x4 = 1. La couverture correspondante Γ inclut l'ensemble S des sommets U1 , V2 , U3 , U4 : pour chaque variable booléenne xi on choisit Ui si xi = 1, sinon on choisit Vi . Chaque clause est satisfaite, donc chaque triangle possède au moins un sommet relié à un sommet de S, et on place les deux autres sommets dans Γ : sur la figure de la question 7, A1 est relié à S, donc on place les sommets B1 et C1 dans Γ (on aurait pu choisir A1 et B1 , car C1 est lui aussi relié à S ), ainsi que les sommets A2 et C2 (car B2 est relié à S ). Par construction, l'ensemble :
Γ = { U1 , V2 , U3 , U4 , B1 , C1 , A2 , C2 }
constitue bien une couverture de G.
Inversement, partons par exemple de la couverture :
Γ = { V1 , U2 , V3 , V4 , A1 , C1 , A2 , B2 }
Les valeurs des variables booléennes associées à cette couverture sont : x1 = 0, x2 = 1, x3 = 0, x4 = 0. Comme Γ comporte exactement 2 m + n = 8 sommets, on en déduit que chaque triangle possède un sommet qui n'est pas dans Γ : ici il s'agit respectivement de B1 et C2. Le sommet B1 est relié à V3 ∈ Γ (sinon Γ ne serait pas une couverture) : ceci entraîne que le choix x3 = 0 satisfait la première clause. Le sommet C2 est relié à U2 ∈ Γ : ceci entraîne que le choix x2 = 1 satisfait la seconde clause.