CALC-AGREG

ENS Rennes - Année 2014/2015

3 octobre 2014	Machines de Turing Définition Non-déterminisme Langage accepté/décidé Activité : feuille de TD du module LF
10 octobre 2014	Présentation par un étudiant : équivalence de machines à 1 ruban / plusieurs rubans, machines non dét / dét Fonctions récursives Notre but est de construire une classe de fonctions qui correspond à ce que l'on définirait comme calculable avec une machine (cerveau, ordinateur etc.). I) Fonctions récursives primitives Au début, nous avons construit l'ensemble des fonctions primitives récursives. On a introduit les schémas primitifs. Avec tout cela, on peut exprimer plein de choses : sommes, produits, minimisation bornée. Cette classe de fonctions correspond à tout ce qu'on peut exprimer en Bucle (un langage avec des boucles "répéter f(n) fois" et des définitions de fonctions, mais on n'a pas le droit à la récursivité). Les algorithmes écrits terminent tous. On a vu que l'on peut simuler de la récursivité multiple (Fibonacci). On peut aussi simuler des structures de données pour des listes. Les opérations de base (extraire la tête, la queue etc. sont récursives primitives). II) Limites Avec le procédé de diagonalisation de Cantor, et en utilisant une énumération que l'on peut effectivement mécaniser, on construit une fonction qui a l'air calculable, mais qui n'est pas primitive. De quoi s'amuser avec les fonctions récursives
17 octobre 2014	Présentation par un étudiant : la fonction d'Ackermann n'est pas primitive récursive. III) Fonctions récursives partielles (et totales) On introduit alors les fonctions récursives partielles via la minimisation non bornée. Le seule moyen de les rendre totales est d'utiliser des prédicats sûrs. Au niveau langage de programmation, on peut introduire le Mucle (en rajoutant des boucles mu). Les fonctions récursives totales sont les fonctions Mucle dont on a une garantie qu'elle termine et les fonctions récursives partielles correspondent à toutes les fonctions que l'on peut écrire en Mucle. Si on réapplique le diagonalisation de Cantor aux fonctions récursives totales, on obtient une fonction... mais qui n'a pas l'air calculable. Peut-on décider si un prédicat est sûr ? Avec quel formalisme le prouver ? On a l'impression que l'on a atteint les limites. C'est la thèse de Church-Turing : c'est l'hypothèse qu'il y ait une correspondance entre les fonctions récursives totales et ce que l'on peut calculer avec une machine réelle (ordinateur, cerveau etc.). IV) Equivalence entre fonctions récursives et machine de Turing Compilateur fonctions récursives vers machines de Turing
24 octobre 2014	(In)décidabilité Notre motivation suprême est de pouvoir tester algorithmiquement si un prédicat est sûr ou non. Malheureusement, on va montrer que ce problème est indécidable : impossible de trouver un algorithme (ie. une machine de Turing) qui prend en entrée une description d'un prédicat et qui dit s'il est sûr ou non. C'est relié au problème de l'arrêt. I) Machine de Turing universelle Dans ce chapitre, nous allons beaucoup simuler des machines de Turing. D'habitude, le programme est le système de transition de la machine et le ruban contient les données. Mais on peut aussi écrire un "programme" (ie. la description d'une machine de Turing) sur le ruban d'une machine et le système de transition sous-jacent simule l'exécution de la dite-machine. On parle alors de machine universelle. II) Classes R et RE, co-RE 1) Définitions 2) Le paysage global (diagramme de Venn) - on compare aussi à ce qui se passe tout en bas avec P, NP, co-NP où il y a plein de problèmes ouverts... 3) Exemple dans R et RE - formules valides du 1er ordre - formules satisfiables dans un modèle fini du 1er ordre 4) Langage universelle et ma première réduction III) Problème de l'arrêt IV) Théorème de Rice Présentation par un étudiant : Les démonstrations du cours.
Vacances
7 novembre 2014	Feuille de TD sur l'indécidabilité Présentation par un étudiant : Le problème de correspondance de Post est indécidable. A la maison : lire des chapitres (+ poly) sur P et NP, réduction polynomiale.
14 novembre 2014	Feuille de TD sur la NP-complétude Gadgets pour montrer que REACHABILITY dans un niveau de Super Mario Bros est NP-dur
21 novembre 2014	Les machines de Turing alternantes complètent le modèle : les machines de Turing non-déterministes ne sont pas stables par complémentation alors qu'en rajoutant des choix universels, c'est le cas. On définit les classes L, NL, AP, P, NP, AP, PSPACE, NPSPACE, etc. Présentation par un étudiant : Théorème de Savitch On a montré que QBF est PSPACE-complet et que AP = PSPACE = NPSPACE. Puis, on a montré que le problème de l'accessibilité dans un graphe est NL-complet. Les théorème de hierarchie "P différent de EXPTIME", coNL = NL sont laissés en lecture.

Références