Calculabilité

Equipe pédagogique:

Eugène Asarin, mail: Professeur à l'UJF, UFR IMA, Laboratoire VERIMAG, Chargé de cours et de TD (groupe 4)
Christian Boitet, mail : Professeur à l'UJF, UFR IMA, Laboratoire CLIPS, Chargé de TD (groupe 6)
Yassine Lakhnech, mail : Professeur à l'UJF, UFR IMA, Laboratoire VERIMAG, Chargé de TD (groupe 5)
Pour joindre toute l'équipe

Horaires et salles:

Cours : mercredi 13h00-15h00 F316 (05/02 - 19/02/2003) et lundi 10h-12h F320 (03/03 - 07/04)

TD G4 mardi 8h00-10h00 F021
TD G5 mardi 10h30-12h30 F114
TD G6 lundi: 15h15 -17h15 C02

Présentation:

Le cours sera consacré aux fondements, et surtout aux limitations de l'informatique. Après avoir défini formellement la notion d'algorithme, on verra que certains problèmes (souvent très importants) ne peuvent pas être résolus par un algorithme, et aucun ordinateur super-puissant ne sera capable de résoudre ces problèmes.

Les trois grandes parties de cours seront:

1. Définition rigoureuse de la notion d'algorithme. Modèles de calcul.
2. Propriétés de décidabilité et de calculabilité, premiers problèmes indécidables.
3. Problèmes indécidables en informatique, théorie des langages, logique.

Bibliographie:

1. Pierre Wolper. Introduction à la calculabilité - Paris : InterEditions, 1991.
2. H. Rogers. Theory of Recursive Functions and Effective Computability, MacGraw Hill, N.Y, 1967.
3. Ch. Boitet. Récursivité, calculabilité, application à la théorie des langages : notes de cours - Grenoble : Université scientifique et médicale, 1983,1987...

Le polycopié

Les notes de cours

Autres documents:

Sujets d'examens et d'interrogations écrites de l'année 2000

Sujets d'examens, d'interrogations écrites et de TDs de l'année 2001

Plan détaillé de cours, sujets d'examens, d'interrogations écrites et de TDs de l'année 2002

Documents nouveaux: Quick du 19/03/03 corrigé, TD Sans théorie, TD récursif primitif, TD Arithmétisation, TD Diagonalisation, TD s-m-n, TD analyse de décidabilité, TD Compteurs, TD Réécriture

Et enfin : le sujet d’examen et son corrigé.

Les cours

Introduction

1. Présentation, équipe, bibliographie, page web , quicks etc... Aspects math et info dans la calculabilité.
2. Question essentielle : Existe-t-il un algorithme pour ce problème ?
3. Exemples. On constate que dans certains cas on voit un algorithme de décision, dans d'autres cas - un algorithme de semi-décision ("un semi-algo"), et parfois on ne voit rien.
4. Notions informelles d'algorithme, de problème décidable, de problème semi-décidable.
5. Pour montrer qu'un problème est décidable il suffit de montrer un algo, mais pour montrer l'indécidabilité on a besoin d'une définition formelle d 'algorithme (et d'une technique pour travailler avec).
6. Les définitions formelles d’algorithme des années 30 ont aussi un intérêt fondamental pour l'informatique. Elles ont fourni la base à l'architecture des premiers ordinateurs et aux langages de programmation...
7. Calculabilité vs Complexité. Comparaison de problématiques, de modèles de base, de techniques.
8. Plan de l'enseignement:

o

• Chapitre 1. Définition formelle d'algo. Modèles de calcul.
• Chapitre 2. Propriétés de décidabilité/semi-décidabilité/indécidabilité. Preuves d'indécidabilité
• Chapitre 3. Applications.

Chapitre 1. Modèles de calcul

• Réduction de la décidabilité de problèmes à la calculabilité de fonctions.
  Un problème générique a la forme P=(U,B). Pour un x\in U on veut répondre est-ce que x\in B...

Première tentative de définition d'algorithme: Fonctions récursives primitives

• Définition. On définit une classe RP de fonctions de N^k->N par induction

·

• 0(), s(x)=x+1, p_i^k(x₁,...,x_k)=x_i - éléments de base
• deux constructeurs: Comp(f,g₁,...g_k)(x)= f(g₁(x),....g_k(x))
  et RecPri(f,g)=h telle que

o

• h(x,0)=f(x)
• h(x,n+1)=g(x,n,h(x,n+1))
• Sens de la définition. Calculabilité intuitive des fonctions RP. For-programmes.
• Exemples de fonctions récursives primitives
• Quelques propriétés de la classe RP

·

• Chaque fonction RP est définie partout
• Classe RP est fermée par S et P (somme et produit fini)
• Prédicats RP.

·

• Définition: P est un prédicat RP ssi c_P est une fonction RP
• Fermeture booléenne
• Fermeture par quantification bornée
• Fonctions définies par cas
• Minimisation bornée - une méthode puissante pour définir des fonctions RP

·

• Définition
• Fermeture de la classe RP par m bornée.
• Exemples d'utilisation
• Limitations des fonctions récursives primitives

·

• Fonction d'Ackermann: "calculable" mais non RP
• Il manque le "while"…

Fonctions récursives partielles — une bonne définition d’algorithme

• Deux idées : ajouter à la définition de RP

·

• Minimisation non-bornée
• Fonctions partielles
• Réalisation de deux idées :

·

• Fonctions partielles — définition, notations, terminologie
• Opérations Comp et RecPri sur les fonctions partielles
• Opération m sur les fonctions totales et partielles
• Un bon conseil : évitez RecPri et surtout m sur les fonctions non-totales.
• Définition inductive de la classe de fonctions récursives partielles

·

• Base : 0, s, p_i^k
• Trois constructeurs : Comp, RecPri, m
• La sous-classe de fonctions récursives totales (générales)

·

• Définition : f est récursive générale si (1) elle est récursive partielle, (2) elle est totale
• Pas de définition inductive…
• Exemples (voir TD4)
• Thèse de Church : Calculable (par une procédure effective) =Récursif Partiel

Machines de Turing — un autre modèle de calcul

• Rappel : automates, machines à pile,…
• Définition de machines de Turing : (Q,S,q₀, d) avec
• Q - un ensemble fini d'états
• S - un alphabet de ruban (fini), contient 0
• q₀ - l'état initial
• d - programme: un ensemble d'instructions de la forme q,a->q', a',[D, G,_]
• Configurations, calculss etc
• La fonction de k variables calculée par une MT

Equivalence des deux modèles de calcul

• Énoncé de théorème: f est calculable par MT <=> f est récursive partielle
• Thèse de Church - Turing: Calculable (par une procédure effective) = Turing-Calculable
• par théorème précédent les Thèses de Church et de Turing sont équivalentes
• MT<= récursive partielle: preuve inductive "par programmation"
• MT>= récursive partielle: preuve
• Difficulté: MT travaille sur les séquences, récursion partielle - sur les entiers
• Solution: arithmétisation.
• Numéros de Gödel
• Fonctions RP représentant le fonctionnement de MT
• La fonction calculée par MT est récursive partielle
• Filière de Church

Conséquences de la preuve - énumération etc

• Fonction universelle. Machine universelle.
• Théorème d'énumération. Notation j^(k)_i
• Théorème de la forme normale.
• Théorème s-m-n

Chapitre 2. Propriétés de décidabilité/semi-décidabilité/indécidabilité. Preuves d'indécidabilité

Indécidabilité du problème d'arrêt

• Prédicats Arrêt(x,y)= (j_x(y) converge) et K(x)= (j_x(x) converge)
• Indécidabilité du prédicat K - preuve par diagonalisation.
• Indécidabilité du prédicat Arrêt - preuve par réduction

Preuves d'indécidabilité par réduction

• m-réduction - la définition
• m-réduction et décidabilité : si B est décidable et A £ _mB, alors A est décidable
• Méthode de preuve d'indécidabilité par m-réduction: montrer que K £ _mP
• Technique de réduction et exemples de propriétés indécidables des fonctions récursives partielles
• Théorème de Rice

Semi-décidabilité

• Idée intuitive
• Définitions de prédicats semi-décidables et récursivement énumérables (r.e.)
• Equivalence de deux dernières propriétés
• Forme normale
• Théorème de Post: P décidable si et seulement si P et son complément sont r.e.

· Propriétés de fermeture:

o Prédicats décidables: par opérations booléennes, quantification bornée

o Predicats semi-décidables: par conjonction, disjonction, quantification existentielle

Chapitre 3. Applications

Problèmes décidables et indécidables dans l'informatique. La plupart de propriétés de programmes pour des modèles de calcul infinis sont indécidables.

Preuve de l'indécidabilité par simulation de MT. Exemple: le problème d'arrêt est indécidable pour les machines à 2 piles.