Indécidabilité

Encodage des machines de Turing

• On pourrait imaginer plusieurs conventions possibles pour encoder une machine de Turing. Cet encodage devrait spécifier le 6-tuplet (S, , , , , h).

• Pour des raisons pratiques, on choisit un encodage binaire (sur l’alphabet {0,1}) des machines de Turing.

• Pour une machine de Turing M, dénotons M l’encodage de M.

Différence entre M et M

• Lorsque l’on parle d’un “programme” on ne fait souvent pas la distinction entre le code source du programme et l’exécutable qui lui correspond.

• La différence entre M et M est de la même nature. – La machine M est une “machine” donc un processus

automatique, un exécutable, quelque chose qui reçoit une entrée et retourne (peut-être) une sortie.

– M est une suite de 0 et de 1. On choisit d’interpréter cette suite de 0 et de 1 comme ayant un sens précis, celui de l’encodage de M.

• Dépendamment de notre encodage, il est possible que certaines suites de 0 et de 1 ne correspondent pas à une description valide d’une machine de Turing. Pour se simplifier la vie, nous allons supposer que toutes les descriptions invalides correspondent à la machine de Turing suivante:

Cette machine de Turing ne fait que boucler à l’infini sur l’état initial.

• L’encodage permet donc d’associer à n’importe quel chaîne de {0,1}* une machine de Turing.

• Pour chaque machine de Turing M, il existe un mot M de {0,1}* qui encode M.

• Inversement, chaque mot w de {0,1}* est l’encodage d’une machine Mw.

Machine de Turing universelle

• C’est une machine «programmable». On lui donne en entrée la description encodée d’une machine de Turing M et d’une séquence w. La machine de Turing universelle peut alors simuler l’exécution de M sur l’entrée w et accepter si et seulement si M accepte w.

• Voici une définition informelle de la machine de Turing universelle U.

U = “Entrée M, w1. Si encodage invalide, rejeter;

2. Sinon, écrire sur un second ruban le mot w. Sur ce deuxième ruban, simuler l’exécution de M sur le mot w. Cette simulation peut s’effectuer en déterminant au fur et à mesure la transition qu’effecuterait M.

3. Si M accepte w, alors U accepte. Si M s’arrête et rejette w, alors U rejette.

Considérons le langage suivant:

L0 = {M : M n’accepte pas M}

On pourrait aussi écrire ce langage comme

L0 = {w: Mw n’accepte pas w}.

La définition semble étrange: on demande le résultat de l’exécution de M sur M.

Théorème

Soit L0 le langage

L0 = {M : M n’accepte pas M}. L0 n’est pas Turing-acceptable.

Attention, la définition peut sembler étrange.

Démonstration

La preuve est une preuve par contradiction. Supposons au contraire qu’il existe une machine de Turing N qui accepte L0.

Appliquons notre encodage: la machine N peut alors être encodée par le mot N.

Question

A-t-on N L(N)? Est-ce que N accepte sa propre description?

1. Supposons que oui. Puisque L0 = L(N), on a N L0. Par définition de L0 , cela veut dire que n’accepte pas N, et donc que Nn’est pas dans L(N). C’est une contradiction; on ne peut donc pas avoir N L(N). Examinons l’autre possibilité.

A-t-on N L(N)?

Supposons que non (c’est-à-dire supposons que N L(N). Puisque L0 = L(N), on a N. Par définition de L0 , cela veut dire que N accepte N, et donc que N L(N). C’est une contradiction; on ne peut donc pas non plus avoir N L(N).

Comme nous ne pouvons avoir ni N L(N) ni N L(N), cela nous force à conclure que la supposition initiale est erronée. Il n’existe donc pas de machine de Turing qui puisse reconnaître L0.

Cela veut dire qu’il existe un langage qui n’est pas Turing acceptable et qu’on vient d’en exhiber un.

Théorème

Si L est décidable alors son complément Lc est également décidable.

Théorème

Si L est Turing acceptable et si son complément Lc est également Turing acceptable alors le langage L est décidable.

Théorème

Soit L0 le langage

L0 = {M : M n’accepte pas M}. L0 n’est pas Turing-acceptable.

Théorème

Dans un langage plus proche de la programmation:

Soit L0 le langage

L0 = {M : M est le code source d’un programme M qui n’accepte pas M}.

L0 n’est reconnaissable par aucun programme.

Preuve• Supposons qu’un tel programme existe et appelons le

N. Soit N le code source de N. On a L(N) = L0.

• Que se passe-t-il si on exécute N sur son code source? – Si N accepte son code, on a d’une part N L(N) = L0

mais aussi N L0 par définition de L0. Contradiction!

– Si N n’accepte pas son code, on a d’une part N L(N) = L0 mais aussi N L0 par définition de L0. Contradiction!

• Ces contradictions montrent qu’un tel N n’existe pas.

Le problème de l’arrêt

On a vu que le problème

L0 = {M : M est une m.t. qui accepte M}

n’est pas Turing-acceptable.

Le problème de l’arrêt est le nom qui est généralement attribué au langage suivant:

Lh = {M: M accepte M}

Remarques

• Le problème de l’arrêt est Turing-acceptable car Lh = L(N) où N est l’algorithme:

N = “Entrée M;1. Simuler M sur M. Si arrêt et acceptation alors accepter

M. Si arrêt et rejet alors rejeter M ”

• Le nom de problème de l’arrêt est parfois réservé aux langages

Lh = {M: M s’arrête sur l’entrée M} ou

Lh = {M: M une m.t. qui s’arrête sur l’entrée } qui ont exactement les mêmes propriétés.

Théorème

• Le problème de l’arrêt est indécidable.

Preuve

• Montrons ce résultat par contradiction. Supposons que Lh est décidable et montrons qu’alors, le langage L0 est décidable également.

• Rappel L0 = {M: M n’accepte pas M} et donc L0 = Lh

c. Puisque le complément d’un langage décidable est décidable, alors L0 est décidable, ce qui est une contradiction.

Un autre problème indécidable

Soit NVMT = { <M> : M une m.t. et L(M) ≠ }

Nous allons montrer que ce langage n’est pas décidable.

Idée clé: Si NVMT est décidable alors le problème de l’arrêt est également décidable.

Démonstration

Supposons que NVMT est décidable grâce à la machine de Turing R.

On peut définir pour chaque machine de Turing M une machine de Turing SM comme suit:

SM = « Entrée x:1. Si x 0 alors rejeter x ;2. Si x = 0 alors simuler M sur <M> et accepter x ssi M

accepte <M>; »

Donc si M accepte <M> on a L(SM) = {0}. Par contre si M n’accepte pas <M> on a L(SM) = .

Notez aussi qu’il est facile de construire la machine SM à partir de <M>.

Que fait alors la machine de Turing suivante?

T = «  Entrée <M>:1. Construire la machine SM et produire <SM>;

2. Simuler R sur l’entrée <SM> et accepter <M> si R accepte <SM> mais rejeter <M> si R rejette <SM>; »

Considérons deux cas.

1. Si M accepte <M> alors L(SM) = {0}. Ce langage n’est pas vide donc R va accepter <SM> et T accepte <M>.

2. Si M n’accepte pas <M> alors L(SM) = donc R va rejeter <SM> et T rejette <M>.

Donc L(T) = Lh. Mais T termine toujours car R est un décideur. Donc Lh est décidable.

Contradiction! Donc NVTM n’est pas décidable.

Exemple relié

• Montrons que le langage K n’est pas décidable.K = {M: Lorsque M reçoit en entrée , M écrit

“hello world” sur son ruban puis s’arrête.}

Supposons qu’il existe une m.t. N qui étant donnée M s’arrête toujours et accepte ssi la machine M a la propriété désirée. Nous allons utiliser cette machine N pour créer une machine N’ qui accepte Lh.

• On veut construire N’ telle que L(N’) = Lh. Cette machine devrait prendre en entrée une description M de machine de Turing et s’arrêter toujours. Elle doit répondre oui ssi M accepte M

N’ = “Entrée M ;1. Modifier la description M pour créer une machine la

description M’ d’une machine qui s’arrête immédiatement si l’entrée est non-vide et qui lorsque son entrée est simule d’abord M sur M. Lorsque la simulation montre que M accepte, M’ efface son ruban, écrit “hello world” et s’arrête.

2. Simuler le décideur N sur l’entrée M’. Si N accepte M’ alors accepter. Sinon rejeter.”

• Analysons le comportement de N’.

1. Si M Lh alors la modification de M va donner une machine M’ qui s’arrête et écrit “hello world”. Donc M’ est accepté par N et ainsi N’ accepte M.

2. Mais si M Lh alors la modification de M va donner un M’ qui est rejeté par N. Ainsi, N’ va également s’arrêter et rejeter M

Donc N’ est un décideur pour Lh, ce qui est une contradiction.

On a donc une série d’inclusions strictes:• Langages réguliers

(a*◦ b*), {w: w contient au moins 2 a}, etc.

• Langages non-contextuels

{an bn: n N}, ensemble des palindromes, etc.

• Langages décidables

{an bn cn : n N}, {<M>: M un automate fini et L(M) }

• Langages Turing-acceptables

Lh = {<M>: M une m.t. et M accepte <M>}

• Langages non-acceptables

{<M>: M une m.t. et M n’accepte pas <M>}, NVTM

Exemple plus concret

• Fonctionnement des logiciels anti-virus.1. Vérifie si l’ordinateur contient un des programmes

d’une liste de programmes considérés comme dangereux.

2. Avertit l’utilisateur lorsqu’une action potentiellement malicieuse est effectuée par un programme non-autorisé.

• Idéal: un logiciel anti-virus qui avant l’exécution d’un programme décide si oui ou non ce programme tentera une action considérée dangereuse. Malheureusement impossible.

Fonctions calculables

Définition: Une fonction f:{0,1}* {0,1}* est calculable si il existe une machine de Turing qui lorsqu’elle démarre avec la configuration w… s’arrête dans la configuration f(w)…

Exemple

Les fonctions suivantes sont calculables:

• f(w) = ww

• f(w) = wr

Ces deux exemples sont très simples (exercice: construisez les machines de Turing qui calculent ces fonctions.)

Exemple

La fonction f suivante est calculable:

• Si w n’est pas l’encodage d’une machine de Turing alors f(w) = .

• Si w = <M> alors f(w) = <NM> où NM est une machine de Turing qui accepte xx si M accepte x.

Preuve

Voici une grossière description d’une machine de Turing T qui calcule f.

T = «  Entrée <M>:1. Bâtir une machine NM qui effectue la tâche suivante

NM = « Entrée x:

Simuler M sur xx et accepter si M accepte; »

2. Retourner NM ;»

Réductions

Soient L et K deux langages de {0,1}*. Le langage L se réduit au langage K (dénoté L m K) s’il existe une fonction calculable f: {0,1}* {0,1}* telle que

w L f(w) K.

En d’autres mots, la fonction f nous permet de transformer une question de type L en une question de type K.

Exemple

Le langage L = {0n1n: n N} se réduit au langage K = {0n12n0n: n N}.

Considérons la fonction f: {0,1}* {0,1}* qui donne f(w) = wwr.

Si w est dans L alors w = 0n1n pour un certain n et donc wwr = 0n12n0n. Ainsi, f(w) K.

Par contre si wL alors on a forcément f(w) K

Théorème

Si K est un langage décidable et si L m K alors L est aussi décidable.

Si K est un langage Turing acceptable et si on a L m K alors L est aussi Turing acceptable.

Preuve

Supposons que K peut être accepté par la machine de Turing M. Nous allons construire une machine T qui accepte L grâce à la fonction calculable f qui réduit L à K.

T = « Entrée x:1. Calculer f(x);2. Simuler M sur f(x). Si M accepte f(x) alors T

accepte x. Si M rejette x alors T rejette x; »

Que fait T?

Si x L alors f(x) K par la définition de la réduction. Donc M accepte f(x) et donc T accepte x.

Si x L alors f(x) K parce que f définit une réduction de L à K. Donc M n’accepte pas f(x) et donc T n’accepte pas x.

L(T) = L.

La machine T s’arrête-t-elle toujours?

L’étape 1 (calcul de f) se termine toujours car f est calculable.

À l’étape 2, si M poursuit une éxécution infinie sur f(x) alors T simule M indéfiniment. Sinon, T s’arrête après un nombre fini d’étapes.

Donc si M est un décideur, T est un décideur. Donc on peut conclure:

K décidable L décidable

K Turing-acceptable L Turing-acceptable

Corollaire

Si L est un langage non-décidable et si L m K alors K est non-décidable.

Si L est un langage qui n’est pas Turing-acceptable et si L m K alors K n’est pas Turing acceptable.

Ce corollaire est très utile pour démontrer qu’un problème K n’est pas décidable (ou pas Turing acceptable).

À condition de bien l’utiliser!

Pour obtenir notre contradiction, il faut montrer qu’il existe une réduction d’un langage non-décidable L vers notre cible K et non l’inverse.

Exemple

Je n’arrive pas à décider s’il va pleuvoir demain.

Il est clair que décider s’il va pleuvoir demain est un problème plus simple que de voir l’avenir.

Conclusion: je ne peux pas voir l’avenir?

Exemple

Le langage REGTM = {<M>: M est une mt et L(M) est un langage régulier} est indécidable.

Pour le montrer, nous allons montrer qu’il existe une réduction du langage indécidable Lh à REGTM.

Nous voulons trouver une fonction calculable f telle que

Si <M> est dans Lh alors f(<M>) est dans REGTM.

Si <M> n’est dans Lh alors f(<M>) n’est pas dans REGTM.

Autrement dit

Si M accepte <M> alors f(<M>) est la description d’une mt N telle que L(N) est régulier

Si M n’accepte pas <M> alors f(<M>) est la description d’une mt N telle que L(N) n’est pas régulier.

Pour chaque machine M, considérons la machine NM suivante:

NM = « Entrée x:1. Si x = 0n1n pour un certain n alors N accepte x;

2. Sinon, simuler M sur <M>. Si M accepte <M> alors NM accepte x; »

Que fait NM ?

Si M accepte <M> alors NM accepte tous les x, soit à l’étape 1, soit à l’étape 2. Donc L(NM ) = {0,1}*, un langage régulier.

Si M n’accepte pas <M> alors, NM ne peut accepter x que dans l’étape 1. Donc L(NM ) = {0n1n: n N}, un langage non-régulier.

Étant donné une description <M> d’une machine de Turing M, on peut facilement calculer la description < NM > de la machine NM.

Donc la fonction f définie par f(<M>) = <NM> est une fonction calculable.

Si M accepte <M> alors <NM> est dans REGTM.

Si M n’accepte pas <M> alors <NM> n’est pas dans REGTM.

Donc Lh REGTM.

D’après le corollaire, puisque Lh n’est pas décidable, alors REGTM n’est pas décidable.

Exemple

Le langage REGTM = {<M>: M est une mt et L(M) est un langage régulier} n’est pas non plus Turing-acceptable.

Pour le montrer, nous allons montrer qu’il existe une réduction du langage non-acceptable L0 à REGTM.

Nous voulons trouver une fonction calculable f telle que

Si <M> est dans L0 alors f(<M>) est dans REGTM.

Si <M> n’est dans L0 alors f(<M>) n’est pas dans REGTM.

Autrement dit

Si M n’accepte pas <M> alors f(<M>) est la description d’une mt NM telle que L(NM) est régulier

Si M accepte <M> alors f(<M>) est la description d’une mt NM telle que L(NM) n’est pas régulier.

Pour chaque machine M, considérons la machine NM suivante:

NM = « Entrée x:1. Si x ≠ 0n1n pour un certain n alors N rejette x;

2. Sinon, simuler M sur <M>. Si M accepte <M> alors NM accepte x; »

Que fait NM ?

Si M accepte <M> alors NM accepte tous les x qui n’on pas été rejetés à l’étape 1. Donc L(NM ) = {0n1n: n N}, un langage non-régulier.

Si M n’accepte pas <M> alors, NM ne peut accepter x ni à l’étape 1 ni à l’étape 2. Donc L(NM ) = , un langage régulier.

Étant donné une description <M> d’une machine de Turing M, on peut facilement calculer la description < NM > de la machine NM.

Donc la fonction f définie par f(<M>) = <NM> est une fonction calculable.

Si M accepte <M> (donc si <M> n’est pas dans L0) alors L(NM) = {0n1n: n N} donc <NM> n’est pas dans REGTM.

Si M n’accepte pas <M> alors <NM> est dans REGTM.

Donc L0 REGTM.

D’après le corollaire, puisque L0 n’est pas acceptable, alors REGTM n’est pas acceptable.

Exercices

Montrez que ces langages ne sont pas décidables.

NCTM = {<M>: M est une mt et L(M) est non-contextuel}

ACCTM = {<M>#w: M est une mt et M accepte w}

Montrez aussi que le premier langage n’est pas Turing-acceptable.

Problèmes décidables

EQREG = {<M1,M2>: M1,M2 des automates finis et L(M1) = L(M2)}

Ce problème est décidable.

Preuve

La machine de Turing suivante décide EQREG.

T = « Entrée <M1,M2>:

1. Construire l’automate N reconnaissant l’union de L(M1) et du complément de L(M2).

2. Tester si L(N) = *. Sinon rejeter l’entrée.

3. Construire l’automate N’ reconnaissant l’union de L(M2) et du complément de L(M1).

4. Tester si L(N’) = *. Sinon rejeter l’entrée.

5. Accepter l’entrée. »

Remarques

• La plupart des problèmes de décision reliés aux automates finis sont décidables.

• La plupart des problèmes de décision reliés aux machines de Turing sont indécidables

• Seuls certains problèmes à propos des grammaires non-contextuelles sont décidables.

Exemples

• Le problème EQGNC = {<G,H>: G et H sont des grammaires non-contextuelles et L(G) = L(H)} est indécidable.

• Le problème TOUTGNC= {<G>: G est non-contextuelle et L(G) = *} est indécidable.

• Le problème VGNC = {<G>: G est non-contextuelle et L(G) = } est décidable.

D’autres problèmes indécidables

• Dixième problème de Hilbert: étant donné une équation à plusieurs variables et dont les coefficients sont des entiers, décider si l’équation possède une solution d’entiers.

• Posé au tournant du XXe siècle, résolu dans les années 70: c’est indécidable!