[PDF] CH.8 Décidabilité Propriétés des langages

View - Download CH.8 Décidabilité

Previous PDF

Next PDF

Automates ch8 1

CH.8 Décidabilité

• 8.1 Les langages récursifs • 8.2 La machine de Turing universelle • 8.3 Des problèmes de langages indécidables • 8.4 D'autres problèmes indécidables

Automates ch8 2

8.1 Les langages récursifs

Propriétés des langages récursifs :

Fermés par complémentation, union et intersection. Mw oui nonouinon

Complémentation :

M 1 w oui non oui non M 2 oui non ou / et logique

Union / intersection

Propriétés des langages récursivement énumérables :

Fermés par union mais pas par intersection.

Automates ch8 3

Théorème :

Le langage L est récursif si et seulement s'il est récursivement

énumérable et son complémentaire aussi.

M 1 w oui oui non M 2 oui Utile pour montrer qu'un langage n'est pas récursif. On montre que son complémentaire n'est pas récursivement énumérable.M 1 et M 2 reconnaissent L et son complémentaire.

La machine ci-contre s'arrête

toujours.

Automates ch8 4

8.2 La machine de Turing universelle

Numérotage des programmes permet de numéroter les machines de

Turing (voir la machine comme un programme).

Pour tout entier n, on peut parler de la machine M n . Cette machine peut être construite explicitement au moyen d'un programme (donc d'une machine de Turing. On peut aussi numéroter les mots. Connaissant k, le mot w k peut aussi être construit explicitement par une machine de Turing.

Exemple :le langage diagonal L

d = { w i : w i L(M i Ce langage n'est pas récursivement énumérable.

Supposons L

d = L(M k ), reconnu par la machine de numéro k.

Soit w

k . On a alors : ( w k L d ) ( w k L(M k ) ) par définition de L d ( w k L d ) par définition de L(M k

Contradiction dans tous les cas, donc M

k n'existe pas.

Automates ch8 5

U(n, k)

oui si M n accepte w k non si M n rejette w k boucle si M n boucle sur w k

Interpréteur = réalisation pratique de machine universelle.En assemblant numérotage des machines et numérotage des mots,

on a la machine de Turing universelleU :Conséquence : le problème "étant donnés n et k, la machine M n accepte-t-elle le mot w k est indécidable. Si on pouvait le décider, on pourrait aussi décider "étant donné k, la machine M k accepte-t-elle le mot w k ?". Ceci impliquerait la récursivité de L d En fait le problème est équivalent au problème de l'arrêt.

Automates ch8 6

8.3 Des problèmes de langages indécidables

Beaucoup d'arguements d'indécidabilité font appel au lemme suivant.

Lemme :

Soit une machine M prenant en entrée deux entiers n et k. On fixe n. On obtient, pour chaque n, une machine prenant en entrée un entier k. Cette machine a comme numéro g(n). Alors la fonction qui à n associe g(n) est récursive totale. Si on voit les machines de Turing comme des programmes, la démonstration est facile. Lorsque n est donné, on remplace dans le programme de M l'instruction de lecture de n par la valeur de n. On obtient ainsi un programme qui peut servir de numéro g(n). Par contre, rien n'exige que la machine fasse quoi que ce soit d'utile...

Automates ch8 7

Un problème sur les langages peut toujours se ramener un énoncé du type "le langage L a-t-il la propriété S? On peut voir Scomme un sous- ensemble de l'ensemble Lde tous les langages récursivement énumérables (le sous-ensemble constitué des langages ayant cette propriété). De cette manière, une propriété et un sous-ensemble de L sont la même chose. Les propriétés triviales sont L, satisfaite par tous les langages récursivement énumérables, et , satisfaite par aucun langage.

Théorème (Rice) :

Si Sest une propriété non-triviale, alors le problème "étant donné n, le langage L(M n ) a-t-il la propriété S?" est indécidable.

Démonstration :

Supposons qu'il existe une machine MS prenant en entrée n et décidant si L(M n ) S. En intervertissant les sorties oui et non, on obtient une machine décidant L(M n ) S.

Automates ch8 8

On suppose que le langage vide n'a pas la propriété S. Sinon, on s'intéresse à la propriété L-S. Puisque Sn'est pas triviale, au moins un langage L(M t ) possède la propriété S. On peut trouver t explicitement. Pour cela, on utilise MS en rentrant successivement tous les entiers 0, 1, ... La machine MS s'arrête toujours. Tant qu'elle s'arrête sur non, on continue. Puisque Sest n'est pas triviale, elle finira par s'arrêter sur oui, pour un entier t. On construit la machine A suivante, avec 3 entrées, n, k et i :

U(n, k)ouiM

t i oui

Dans la machine A, la machine M

t est lancée avec i en entrée seulement si la machine U s'est arrêtée sur oui. En vertu du lemme, il existe une fonction a(n, k), récursive totale, calculée par la machine M telle que A(n, k, i) = M a(n, k) (i).

Automates ch8 9

Supposons n et k donnés. Deux cas se présentent : soit w k L(M n ), auquel cas M t démarre et répond oui si et seulement si w i L(M t ) = L, c'est-à-dire que L(M a(n, k) ) = L ; soit w k L(M n ), auquel cas M t ne démarre pas donc A n'accepte aucun i et L(M a(n, k)

Soit maintenant la machine B suivante :

M(n, k)a(n, k)MS

oui non Avec les mêmes n et k donnés, deux cas se présentent de nouveau : soit elle s'arrête sur oui, ce qui signifie L(M a(n, k) ) S. On a vu plus haut que soit L(M a(n, k) ) = L, soit L(M a(n, k) ) = ; comme le langage vide n'est pas dans S, alors L(M a(n, k) ) = L, et donc w k L(M n soit elle s'arrête sur non, ce qui signifie L(M a(n, k) ) S. La seule possibilité est maintenant L(M a(n, k) ) = , et donc w k L(M n

La machine B déciderait si M

n accepte w k , ce qui est indécidable...

Automates ch8 10

Les conséquences du théorème de Rice sont innombrables ; sont indécidables : "L(M n ) = ?", "L(M n ) est fini ?", "L(M n ) est récursif ?", "L(M n ) est rationnel ?", "İL(M n ) ?", "L(M n ) = L donné ?" ; du dernier, on déduit "L(M n ) = L(M k ) ?", et, de façon analogue, "L(M n ) L(M k )= ?", etc. Ce résultat peut être raffiné en n'exigeant pas une machine qui décide (oui-non, récursif) mais une machine répondant oui si la propriété est vraie et boucle sinon (récursivement énumérable). Par exemple, on peut trouver une telle machine pour le problème "L(M n ) ?". Il suffit d'essayer tous les mots par taille croissante. Ce programme s'arrête lorsqu'il trouve un mot accepté. Ceci montre aussi qu'on ne peut pas faire de même pour "L(M n ) = ?", les deux problèmes étant complémentaires l'un de l'autre.

Automates ch8 11

8.4 D'autres problèmes indécidables

Le problème de Post.

On donne deux suites finies A et B de mots sur un alphabet. A = w 1 , w 2 , ... , w k et B = x 1 , x 2 , ... , x k

Probleme de Post :

Etant données les suites A et B, existe-t-il une suite i 1 , i 2 , ... , i m telle que w i 1 w i 2 ... w i m = x i 1 x i 2 ... x i m Par exemple, sur l'alphabet {0, 1}, le problème avec A = {1, 10111, 10} et B = {111, 10, 0} est vrai : w 2 w 1 w 1 w 3 = x 2 x 1 x 1 x 3

Mais le problème avec

A = {10, 011, 101} et B = {101, 11, 011} n'a pas de solution. On peut montrer que le problème de Post est indécidable, en montrant qu'il est équivalent à celui de l'appartenance d'un mot à un langage L(M).

Automates ch8 12

On en déduit que le caractère intrinsèquement ambigu d'une grammaire algébrique est indécidable.

Le théorème du "point fixe"

Théorème :

Soit ıune fonction récursive totale d'une variable entière. Alors il existe un entier x 0 et deux machines de Turing équivalentes de numéros x 0 et ı(x 0

En d'autres termes, M

x 0 (x) = M

ı(x

0 (x)quelle que soit l'entrée x.

Démonstration :

On construit la machine de Turing G suivante :

Automates ch8 13

UM i (i) U x i M Mi(i) (x) On considère la fonction g qui, à i fixé, donne le numéro de la machine ci-dessus, avec la seule entrée x (lemme vu plus haut) : M g(i) (x) = G(i, x)

La fonction g est récursive totale, donc ı

og aussi, calculable par la machine de Turing M t : pour tout x, on a M t (x) = ı(g(x)).

Soit x

0 = g(t), qui est bien défini. On vérifie qu'il convient.

En effet,

M x 0 (x) = M g(t) (x) = G(t, x) = M M t (t) (x) = M

ı(g(t))

(x) = M

ı(x

0 (x).

Le théorème est donc démontré.

Automates ch8 14

On a calculé un tel x

0 . Mais la machine correspondante n'a pas d'autre propriété. peut-être qu'elle ne produit jamais aucun résultat... On a un ensemble fini d'axiomes F et on dispose du calcul logique des prédicats pour fabriquer des démonstrations de propositions. Si une proposition dérive logiquement des axiomes, on dit qu'elle est démontrable dans F. On suppose aussi que F est non-contradictoire, ou encore que toutes les propositions qu'on peut démontrer à partir de

F sont vraies.

Théorème :

Il existe une machine de Turing M qui ne s'arrête sur aucune entrée et pour laquelle, quelle que soit l'entrée, il n'existe pas de démonstration dans F qu'elle ne s'arrête pas.

Automates ch8 15

Démonstration :

On peut numéroter toutes les démonstrations (suites finies de symboles).

Etant donnée une démonstration D

i et une proposition, on peut, à l'aide d'un algorithme, vérifier si la proposition est démontrée par cette démonstration. Soit donc d(i, j) =1 s'il existe une démonstration que la machine M i ne s'arrête pas sur le mot w j ; d(i, j) est indéfini sinon.

On peut calculer d : la proposition est que M

i (j) s'arrête. On énumère toutes les démonstrations et on vérifie si chacune démontre cette proposition. S'il existe une démonstration, l'algorithme s'arrête et on renvoie la valeur 1. Sinon, on bouclera indéfiniment. Donc d est récursive partielle. En vertu du lemme du paragraphe 8.3, il existe une fonction récursive totale g telle que, pour tout j, M g(i) (j) = d(i, j).

Automates ch8 16

D'après le théorème du point fixe, on construit un entier i 0 tel que, pour tout j, on a M i 0 (j) = M g(i 0 (j) = d(i 0 , j).

Supposons que M

i 0 (j) s'arrête. Alors d(i 0 , j) est défini, donc vaut 1 et donc il existe une démonstration que M i 0 (j) ne s'arrête pas. Puisque à partir de F on ne peut rien démontrer de faux, on arrive à une contradiction.

Donc, M

i 0 (j) ne s'arrête pas. Par conséquent d(i 0 , j) n'est pas défini. Il n'existe donc pas de démonstration que M i 0 (j) ne s'arrête pas.

On a trouvé la machine M cherchée.

de Peano), la numérotation des démonstrations et peut du coup se passer des machines de Turing en ramenant tout à des propriétés arithmétiques des entiers.quotesdbs_dbs45.pdfusesText_45

[PDF] épaisseur atmosphère saturne

[PDF] fonction primitive récursive exercice corrigé

[PDF] théorème de godel démonstration

[PDF] codage de godel

[PDF] théorème de gödel pdf

[PDF] arithmétique de robinson

[PDF] nombre de godel

[PDF] godel dieu

[PDF] théorème d'incomplétude pour les nuls

[PDF] incomplétude définition

[PDF] introduction ? la calculabilité pdf

[PDF] indemnité prof principal 2017

[PDF] isoe prof principal

[PDF] hsa prof

[PDF] indemnite tuteur stagiaire education nationale