| 4 octobre 2013 | 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.
II) LimitesOn 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). 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.
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.). De quoi s'amuser avec les fonctions récursives De la lecture : Fonction d'Ackermann |
| 18 octobre 2013 | Machines
de Turing Distribution du TD avec la fonction d'Ackermann Transparents On va partir d'un autre point : ce qui est calculable intuitivement l'est avec un modèle qui contient un "programme" et une "mémoire". Un modèle simple est la machine de Turing : un système de transitions qui représente le programme et un ruban infini pour la mémoire. On verra que ce modèle est très flexible (pas grave par exemple si on change la condition d'arrêt). Ce modèle sera un bon tremplin pour montrer que des problèmes sont indécidables et définir les notions de complexité. I) Définitions 1) Machine
II) Equivalences entre machines2) Langage accepté (on ne tient pas compte de la terminaison) 3) Langage décidé (on tient compte de la terminaison) 4) Calcul 1) Condition
d'acceptation
III) Equivalencecs avec les fonctions récursives2) Supprimer le surplace 3) Ruban infini des deux côtés ou juste d'un côté 4) Uniquement 2 états 5) Uniquement 2 lettres 6) Multi-rubans 7) Machines normalisées 8) Non-déterminisation 1) Des fonctions
récursives aux machines de Turing
2) Des machines de Turing aux fonctions récursives --> Une seule minimisation non-bornée suffit |
| 25 octobre 2013 | (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-RE1) Définitions
III) Problème de l'arrêt2) 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
4) Langage universelle et ma première réduction- formules satisfiables dans un modèle fini du 1er ordre IV) Théorème de Rice Toute propriété non
triviale sur RE est indécidable.
|
| Vacances | |
| 8 novembre 2013 | Feuille
de TD sur l'indécidabilité A la maison : lire des chapitres (+ poly) sur P et NP, réduction polynomiale. |
| 22 novembre 2013 | Feuille de TD sur la NP-complétude |
| 29 novembre 2013 | 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. Dans ce cas, 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. |