Chapitre 2 : Diagonalisation et problème de l'arrêt

TD : Diagonalisation et calculabilité

Exercice 1 (corrigé ci-dessous). On rappelle que la donnée d'un ensemble (fini ou infini) d'entiers naturels E est équivalente à la donnée de sa fonction caractéristique N → {0, 1}. Soit une suite :

E0, E1,E2, … En, …

de tels ensembles. Construire, par diagonalisation, un ensemble qui n'appartient pas à cette suite.

Exercice 2 (corrigé ci-dessous). Soit f : N → {0, 1} une fonction totale non calculable (par exemple celle qui correspond au problème de l'arrêt). Construire à partir de f une fonction g : NN totale, non calculable, et croissante.

Exercice 3 (corrigé ci-dessous). Une fonction NN totale, non calculable, et croissante peut-elle être bornée ? Montrer que toute fonction NN totale et décroissante est calculable.

Exercice 4 (corrigé ci-dessous). Montrer que l'inverse d'une fonction f : NN calculable et bijective, est calculable.

Exercice 5 (corrigé ci-dessous). On considère le tableau infini U (dit universel) dont la ligne i contient la suite de valeurs calculées par la procédure numéro i, notée pi :

pi (0), pi (1), pi (2), … pi ( j ), …

  1. On considère une colonne quelconque de ce tableau (disons de numéro j) : est-il vrai que cette colonne est égale à l'une des lignes du tableau ?
  2. Inversement, est-il vrai que toute ligne du tableau est égale à l'une des colonnes ?

Exercice 6 (corrigé ci-dessous). Montrer qu'une fonction totale f : NN est calculable si et seulement si son graphe :

G = { (x, f (x) ) | x appartient à N }

est décidable.

Exercice 7 (corrigé ci-dessous). Soit E un ensemble d'entiers naturels, et φ la fonction définie par :

φ (n) = # { x | x < n et x appartient à E }

où le signe # signifie cardinal (de l'ensemble qui suit). Montrer que E est décidable si et seulement si φ est calculable.

Exercice 10 (corrigé ci-dessous). On suppose donnée la procédure premier (facile à écrire) qui décide si un entier n est premier ou non. Construire une procédure pj telle que la conjecture "il existe une infinité de nombres premiers jumeaux" soit vraie si et seulement si pj calcule une fonction totale.

Solutions

Exercice 1 (énoncé ci-dessus). L'argument de diagonalisation de Cantor, appliqué aux fonctions caractéristiques des Ei , revient à construire l'ensemble :

D = { n | n n'appartient pas à En }

qui ne peut pas avoir de numéro.

Exercice 2 (énoncé ci-dessus). Une solution est donnée par g (n) = Σ f (i), pour i variant entre 0 et n. g n'est pas calculable, car on a, pour n > 0 :

f (n) = g (n) - g (n - 1)

ce qui permet de calculer f à partir de g.

Autre solution (moins intéressante) : g (n) = f (n) + n, ou bien g (n) = f (n) + 2n, pour obtenir une fonction strictement croissante.

Exercice 3 (énoncé ci-dessus). Non, sinon elle est ultimement constante (on travaille sur les entiers, ce que beaucoup d'étudiants oublient, car pour eux fonction évoque irrésistiblement une fonction à valeurs réelles, comme au lycée), donc calculable ; ce qui signifie qu'une procédure pour la calculer existe, pas forcément qu'on est capable de la fabriquer…

De même une fonction décroissante est ultimement constante, il suffit cette fois de ne pas oublier qu'on travaille sur des entiers naturels.

Exercice 4 (énoncé ci-dessus). Voici le code d'une procédure qui calcule l'inverse g de f :

int f (int x) { … }

int g (int y) {
  int x;
  for (x = 0; ; x++)
    if ( f(x) == y ) return x;
}

On peut remarquer que si f n'est pas surjective (contrairement à l'hypothèse de l'énoncé), cette procédure boucle si y n'appartient pas à l'image de f, et calcule donc une fonction partielle. Si f n'est pas injective (contrairement à l'hypothèse de l'énoncé), cette procédure reste intéressante, elle calcule :

min { x | f (x) = y }

Enfin si f est surjective mais partielle, cette procédure échoue en général à trouver un x tel que f (x) = y, car elle boucle dès qu'elle rencontre une valeur pour laquelle f n'est pas définie.

Exercice 5 (énoncé ci-dessus).

  1. Oui, la fonction universelle U est partielle, mais calculable, donc la procédure suivante calcule la colonne 382 :

    int colonne382 (int i) {return U (i, 382); }
    
  2. Non, car par exemple si la ligne correspondant à la fonction constante 0, était aussi la colonne numéro j, cela signifierait que pour toute procédure p, on aurait p ( j ) = 0.

Exercice 6 (énoncé ci-dessus). Si f est totale et calculable, voici une procédure qui calcule la fonction caractéristique χ du graphe G :

int f (int x) { … }

int χ (int x, int y) {
  return y == f(x);
}

Remarque. Il est essentiel que f soit totale pour que la procédure ci-dessus calcule bien la fonction caractéristique de G.

Réciproquement, si χ est calculable, voici une procédure qui calcule f :

int χ (int x, int y) { … }

int f (int x) { 
  int y;
  for (y = 0; ; y++)
    if ( χ(x, y) ) return y;
}

Remarque. En l'absence d'hypothèse sur G (à part qu'il est décidable), la fonction calculée par cette procédure peut être partielle.

Exercice 7 (énoncé ci-dessus). Si E est décidable, sa fonction caractéristique χ est, par définition, calculable, et voici la procédure (évidente) qui calcule φ :

int χ (int x) { … }

int φ (int n) { 
  int x, k = 0;
  for (x = 0; x < n; x++)
    if ( χ(x) ) k++;
  return k;
}

Inversement, si φ est calculable, voici la procédure qui calcule χ :

int φ (int n) { … }

int χ (int x) { 
  return φ (x + 1) - φ (x);
}

Exercice 10 (énoncé ci-dessus). Ce n'est pas l'objet de l'exercice, mais on écrit aussi la procédure premier pour que le texte soit complet (on suppose n > 1), et justifie ainsi la remarque qui suit :

int premier (int n) {
  int d;
  for (d = 2; d * d <= n; d++)
    if (n % d == 0) return 0;
  return 1;
}

int pj (int n) { 
  int p;
  for (p = n; ; p++)
    if ( premier (p) && premier (p + 2) )
      return p;
}

Remarque. Ceci rend plausible l'indécidabilité du problème de l'arrêt : il serait très surprenant qu'il existe un algorithme universel à qui l'on pourrait fournir en argument le simple texte ci-dessus, et qui répondrait "oui, pj calcule une fonction totale", autrement dit "oui, il existe une infinité de nombres premiers jumeaux", ou au contraire "non, il existe n tel que le calcul de pj(n) boucle", autrement dit "non, il existe une borne n à l'ensemble des nombres premiers jumeaux". Par contre la question "la conjecture des nombres premiers jumeaux est-elle indécidable ?" n'a pas de sens.