Réductions

Il a été vu que le problème d'acceptation est indécidable. En fait, beaucoup d'autres problèmes sur les machines de Turing sont indécidables. La preuve que le problème d'acceptation est indécidable était directe. Pour d'autres problèmes, il n'est pas toujours nécessaire de faire une preuve directe. Il est souvent plus facile de se servir d'un autre problème qui est déjà connu comme indécidable.

Problème de l'arrêt

Pour une machine de Turing M et pour un mot w, ⟨M, w⟩ dénote le codage de M et de w. On considère alors le langage L suivant.

L = { ⟨M, w⟩ | M s'arrête sur la donnée w }

Le langage L code le problème de savoir si une machine M s'arrête sur une donnée w. Ce problème est appelé problème de l'arrêt. Le résultat suivant montre que ce problème est indécidable (non récursif).

Proposition. Le problème de l'arrêt est indécidable.

Pour montrer que ce langage n'est pas récursif, on utilise le fait que le problème de l'acceptation n'est pas décidable. Le raisonnement se fait par l'absurde. On montre que si le langage L était récursif alors le problème de l'acceptation serait décidable. Supposons que L est accepté par la machine de Turing H sans calcul infini. On considère alors la machine A suivante.

 
  Machine A avec en entrée ⟨M, w⟩
    Si H n'accepte pas l'entrée ⟨M, w⟩.
      rejeter.
    Sinon, 
      simuler la machine M sur w jusqu'à l'arrêt.
    Accepter si M accepte et rejeter si M rejette.

La machine A est sans calcul infini et elle accepte les entrées ⟨M, w⟩ telles que M accepte w. Du coup, elle accepte le langage du problème de l'acceptation. Ceci est une contradiction car une telle machine ne peut pas exister. La machine H n'existe donc pas non plus et le problème de l'arrêt est donc indécidable.

L'idée de la preuve précédente est de ramener le problème de l'acceptation au problème de l'arrêt. En effet la machine A montre que si le problème de l'arrêt est décidable, alors le problème de l'acceptation devient aussi décidable. Ce principe général est appelé une réduction puisqu'un problème a été réduit à un autre problème.

Problème du vide

On s'intéresse ici au problème de savoir si l'ensemble des mots acceptés par une machine de Turing M est vide, c'est-à-dire s'il existe ou non un mot w accepté par M. Ce problème est appelé problème du vide. Pour une machine de Turing M, on note L(M) l'ensemble des mots acceptés par la machine M. On considère alors le langage L suivant.

L = { ⟨M⟩ | L(M) = ∅ }

Proposition. Le problème du vide est indécidable.

Pour montrer que ce problème est indécidable, on va utiliser une méthode similaire à celle employée pour le problème de l'arrêt. On montre que le problème d'acceptation se réduit au problème du vide. Ceci consiste à montrer que résoudre le problème du vide suffit à résoudre le problème d'acceptation. Le raisonnement est encore par l'absurde. On suppose qu'une machine de Turing V sans calcul infini accepte le langage L. On construit alors la machine A suivante.

 
  Machine A avec en entrée ⟨M, w⟩
    Construire la machine M' = 
      [ Machine M' avec entrée w'
          si w != w' 
	    rejeter
	  sinon
            faire comme M sur w'
      ]
    Calculer V(⟨M'⟩)
    Accepter si V rejette et rejeter si V accepte (négation).

La machine M' est facile à construire à partir de la machine M. Il suffit d'ajouter une première partie qui teste l'égalité de l'entrée w' de M' avec la constante w. En cas d'inégalité, la machine M' rejette w' et sinon, elle continue le calcul comme M sur w' = w. La seule entrée qui peut être acceptée par M' est l'entrée w. Si M accepte w, M' accepte aussi w et si M rejette w alors M' n'accepte aucune entrée. Par conséquent, l'ensemble des mots acceptés par M' est vide si et seulement si M n'accepte pas w. La machine A accepte donc les entrées ⟨M, w⟩ telles que M accepte w. Comme la machine A n'existe pas, la machine V n'existe pas non plus.

Problème de l'égalité

On s'intéresse ici au problème de savoir si deux machines de Turing M₁ et M₂ sont équivalentes c'est-à-dire si elles acceptent les mêmes entrées. Ce problème est appelé problème de l'égalité (des langages acceptés par M₁ et M₂). On considère alors le langage L suivant.

L = { ⟨M₁, M₂⟩ | L(M₁) = L(M₂) }

Proposition. Le problème de l'égalité est indécidable.

Pour montrer que ce problème est indécidable, on utilise encore la méthode de réduction. On réduit ici le problème du vide au problème de l'égalité. On suppose avoir une machine de Turing E sans calcul infini qui accepte le langage L. On considère alors la machine V suivante.

 
  Machine V avec en entrée ⟨M⟩
    Construire la machine M' = 
      [ Machine M' avec entrée w
	  rejeter
      ]
    Calculer E(⟨M, M'⟩)
    Accepter si E accepte et rejeter si V rejette.

Il est clair que la machine M' rejette toutes les entrées et que le langage L(M') est vide. Les deux machines acceptent donc le même langage si et seulement si le langage de M est vide. La machine V accepte donc les entrées ⟨M⟩ telles que L(M) est vide. Comme cette machine n'existe pas, la machine E n'existe pas non plus.

Définition

À partir des exemples précédents, on peut extraire une définition formelle de la réduction d'un problème A à autre problème B. Intuitivement, une réduction est une fonction qui à une instance du problème A fait correspondre une instance du problème B qui a la même réponse. On suppose que les problèmes A et B sont codés par les langages L_A et L_B sur des alphabets Σ_A et Σ_B. Une réduction de A à B est une fonction f de Σ_A^* dans Σ_B^* calculable par une machine de Turing telle que

w ∈ L_A ⇔ f(w) ∈ L_B

On note A ≤_m B lorsqu'il existe une réduction du problème A au problème B. Le fait de pouvoir réduire A à B signifie que le problème A n'est pas plus compliqué que le problème B puisque résoudre le problème B suffit à résoudre le problème A.

Proposition. Si A ≤_m B et si B est décidable, alors A est aussi décidable.

Corollaire. Si A ≤_m B et si A est indécidable, alors B est aussi indécidable.

Théorème de Rice

Les exemples de problèmes indécidables semblent indiquer que beaucoup de problèmes sur les machines de Turing sont indécidables. Le théorème de Rice établit en fait que toutes les questions non triviales portant sur les langages des machines de Turing sont indécidables.

On dit qu'une propriété P sur les langages est non triviale s'il existe au moins un langage récursivement énumérable L qui vérifie P et au moins un langage récursivement énumérable L' qui ne vérifie pas P. Si une propriété P est triviale, tous les langages récursivement énumérables vérifient ou ne vérifient pas la propriété P. Du coup, il est facile de faire une machine de Turing qui accepte les codages ⟨M⟩ des machines M telles que L(M) vérifie P.

Théorème (Rice). Pour toute propriété non triviale P sur les langages, le problème de savoir si le langage L(M) d'une machine de Turing M vérifie P est indécidable.

Quitte à remplacer la propriété P par sa négation, on peut toujours supposer que le langage vide vérifie la propriété P. Puisque P n'est pas triviale, il existe une machine de Turing M₀ telle L(M₀) ne vérifie pas P. On raisonne par l'absurde et on suppose qu'il existe une machine M₁ qui accepte le langage { ⟨M⟩ | M vérifie P }. On construit alors la machine A suivante.

 
  Machine A avec en entrée ⟨M, w⟩
    Construire la machine M' = 
      [ Machine M' avec entrée w'
          Si M accepte w
	     simuler M0 sur w'
      ]
    Calculer M1(⟨M'⟩);
    Accepter si M1 rejette et rejeter si M1 accepte.

Si la machine M rejette l'entrée w, la machine M n'accepte aucune entrée. Le langage L(M') est alors vide et il vérifie P. Si au contraire M accepte w, alors M' est équivalente à la machine M₀. Comme L(M₀) ne vérifie pas P, la machine M accepte w si et seulement si le langage L(M') ne vérifie pas P. La machine A accepte donc les entrées ⟨M, w⟩ telles M accepte w. Comme la machine A n'existe pas, la machine M₁ n'existe pas non plus.