Calculabilité
Plan détaillé
(cf. [Sip97])
- Machines de Turing
- notion de problème et de codage
- définition et exemples
- normalisation
- composition
- fonction calculée par une machine de Turing
- machines à bande bi-infinie
- machines à plusieurs bandes
- machines non déterministes/machines déterministes
- Langages récursivement énumérables
- définition
- équivalence avec les énumérateurs
- propriétés des langages récursivement énumérables
- exemple de langage non récursivement énumérable
par argument diagonal
- Langages décidables
- définition
- machine universelle
- propriétés des langages récursivement énumérables
- exemple de langage récursivement énumérable
mais pas décidable
- Réductions
- définition
- réduction du problème d'acceptation au problème de l'arrêt
- réduction du problème d'acceptation au problème du vide
- réduction du problème du vide au problème de l'égalité
- Problème de correspondance de Post (PCP)
- définitions de PCP et de PCP Modifié (PCPM)
- équivalence entre PCP et PCPM
- réduction du problème d'acceptation à PCP
- application aux grammaires algébriques
- indécidabilité de LG(S) ∩ LG'(S')
= ∅
- indécidabilité de LG(S) = A*
- indécidabilité de LG(S) = LG'(S')
- indécidabilité de l'ambiguïté d'une grammaire
- Théorème de récursion
- programme qui s'écrit
- programme qui manipule son propre source
- application à l'indécidabilité de l'acceptation
- point fixe transformations de programmes
- Machines linéairement bornées (LBM)
- définition
- équivalence avec les grammaires contextuelles
- décidabilité de l'acceptation
- exemple de langage décidable non accepté par une LBM
- indécidabilité du vide
- complémentation des langages acceptés par les LBM
- Décidabilité de théories logiques
- décidabilité de 〈N, +〉
- indécidabilité de 〈N, +, x〉