Introduction
au notion d'alphabet, langage, type de machines, modèle de machines,
définition d'un problème, équivalence reconnaissance
de langage, exemples problèmes faisaibles/non-faisables
Décidabilité de langages
Calculabilité de fonctions
Philippe Rolland : 4/05/98
[ Décidabilité | Calculabilté | Synthèse ]
NOTE:
Il est important de remarquer que le fait qu'une machine de Turing satisfait ou non la condition
"a un calcul qui s'arrête sur toute donnée "
ne se lit pas sur la définition de cette machine de Turing, et même, il n'existe en fait aucune méthode systématique (i.e. valable pour toutes les machines de Turing) permettant de savoir si cette condition est ou non satisfaite. Les notions de décidalibité, acceptation distinguent les temps de résolution fini et non-fini.
1. Notion de Problèmes et langages
Rappelons qu'un problème est constitué par:
(1) la description de la représentation (finie) des éléments d'un ensemble fini ou infini dénombrable,
(2) un énoncé portant sur les éléments de cet ensemble, énoncé qui peut être soit vrai, soit faux selon l'élément choisi.
A chaque problème P, constitué d'une représentation des éléments d'un ensemble et d'un énoncé portant sur ceux-ci, est associé le langage caractéristique Lp du problème, constitué de l'ensemble des mots qui sont la représentation d'un élément de l'ensemble pour lequel la question admet pour réponse: vrai, et Lcp le langage caractéristique du problème contraire CP obtenu à partir de P en gardant la même représentation des données et en prenant l'énoncé contraire.
DÉFINITION: La résolution d'un problème se ramène donc à la reconnaissance d'un langage: une machine résout un problème P si et seulement si pour tout mot qui est la représentation d'un élément de l'ensemble considéré par ce problème, elle permet de déterminer, en un temps fini, si ce mot appartient à Lp ou à Lcp.
Si l'on admet la thèse de Church, résoudre un problème c'est exhiber une machine de Turing qui permet de déterminer, en un temps fini, si ce mot appartient à Lp ou à Lcp. C'est donc une machine de Turing qui s'arrête pour toute donnée et qui reconnaît Lp.
Un des résultats les plus importants de l'informatique fondamentale est qu'il existe des problèmes indécidables. Ainsi, le problème suivant est indécidable:
- Appelation: Problème de l'arrêt uniforme
- Donnée: Une machine de Turing M
- Question: M s'arrête-t-elle sur toute donnée ?
Exemples:
Lien entre la décidabilité, le temps de résolution
Définition: Un langage L est décidé par une machine M si
- 1. M accepte L
- 2. M n'a pas d'execution infini
On peut trouver une autre définition similaire dans le chapitre sur MT:
La machine M décide
le langage si elle atteint toujours l'état d'arrêt
en temps fini. Le ruban 'resultat' contient 1 pour les mots du langage,
0 sinon.
La machine M accepte un langage
si pour tout mot du langage, l'exécution de la machine atteint l'état
d'arrêt avec 1 sur le ruban 'resultat'. Pour les mots qui ne sont
pas du langage l'exécution peut être infinie ou atteindre
l'état d'arrêt, dans ce dernier cas 'resultat' contient 0.
Remarque:
Le concept de langage décidé ainsi défini ne s'applique qu'à des automates déterministes.
Définition: Un langage L est récursif s'il est décidé par une machine de Turing.
Définition: Un langage L est récursif énumérable s'il est accepté par une machine de Turing.
On appelle R la classe des langages récursifs et RE celle des langages récursifs énumérables. (Note : le complément d'un langage L est l'ensemble de tous les mots qui n'appartiennent pas à L. Formellement :
Lc={w | w 
L}
Lemme: La classe R est contenue dans la classe RE.
Lemme: Le complément d'un langage de la classe R est aussi un langage dans R.
Lemme: Si un langage L ainsi que son complément sont dans RE alors ils sont dans R.
Remarque: Il existe des langages non dans RE: la classe des langages accéptés par aucune machines de Turing. Ces langages ne sont pas décidables, d'un certain point de vue on peut dire qu'ils sont plus indécidables que les langages de classe RE. Cette discussion indique que tous les langages indécidables ne sont pas égaux, ie qu'il existe une hiérarchie de problèmes indécidables. Içi on ce limitera à une hiérarchie à 2 niveaux: les problèmes indécidables dans RE et ceux non-RE. Cette hiérarchie peut être complétée et comporte une infinité de niveau.
Introduire les machines non-déterministes de Turing.
| Théorème: Tout langage accepté par une machine de Turing non déterministe est aussi accépté par une machine de Turing déterministe. |
Il existe plusieurs définitions équivalentes de la calculabilité. Dans un premier temps, on rappelle la thèse de Turing-Church suivant deux angles: les langages décidés et les fonctions calculables.
1. Les langages reconnus par une procédure effective sont ceux décidés par une machine de Turing.
2. Les fonctions calculables par une procédure effective sont celle calculable par une machine de Turing.
-récurssives.
La thèse de Turing-Church étaient justement la justification
de cette équivalence entre les fonctions -récurssives
et les fonctions calculables par une machine de Turing. Dans le cadre de
ce module destiné au DEUG2, nous ne présenterons pas la notions
de fonctions -récurssives et donc pas
cette équivalence.
Dans la présentation de la thèse Turing-Church, existe la connexité entre la décidabilité des langages et la calculabilité des fonctions. On peut exprimé cette connexité en fonction de la classe R (R comme récussif). La classe R est la classe des langages (problèmes):
La classe R n'apporte rien de fondamentale, elle permet simplement de regrouper des notations différentes.
Les
Fonctions calculables et les fonctions -récurssives.
(non introduit en DEUG2)
La décidabilité:
Prècisement ce critère s'applique à un langage. Ce langage peut modèliser un problème, un algorithme. Lien vers l'équivalence entre la résolution de problème et la reconnaissance de langage.
Q&A: (FAQ)
Qu'elle est le lien entre la décidabilité d'un problème et la classe (P, NP) du problème ?
Un problème est décidable si il est récursif; et si il est récursif alors il existe un programme qui le résoud en temps fini. Toutefois, rien n'implique que ce programme soit utilisable pratiquement. La théorie sous-jacente au classement des problèmes solubles pratiquement, ie la complexité, distingue les problèmes dans P (ie la classe des langages décidés par une machine de Turing déterministe en temps polynomiale) des problèmes dans NP ( ie la classe des langages acceptés par une machine de Turing non-déterministe en temps polynomiale): P étant la classe des problèmes solubles pratiquements par opposition à NP.
Philippe Rolland : 21/03/98
