Leçon 914 : Décidabilité et indécidabilité. Exemples.

(2017) 914
(2019) 914

Dernier rapport du Jury :

(2017 : 914 - Décidabilité et indécidabilité. Exemples.) Le programme de l’option offre de très nombreuses possibilités d’exemples. Si les exemples classiques de problèmes sur les machines de Turing figurent naturellement dans la leçon, le jury apprécie des exemples issus d’autres parties du programme : théorie des langages, logique,... Le jury portera une attention particulière à une formalisation propre des réductions, qui sont parfois très approximatives.

Développements :

Plans/remarques :

2018 : Leçon 914 - Décidabilité et indécidabilité. Exemples.


2016 : Leçon 914 - Décidabilité et indécidabilité. Exemples.


2015 : Leçon 914 - Décidabilité et indécidabilité. Exemples.


Retours d'oraux :

2018 : Leçon 914 - Décidabilité et indécidabilité. Exemples.

  • Leçon choisie :

    914 : Décidabilité et indécidabilité. Exemples.

  • Autre leçon :

    903 : Exemples d’algorithmes de tri. Correction et complexité.

  • Développement choisi : (par le jury)

    Théorème de Rice

  • Autre(s) développement(s) proposé(s) :

    Pas de réponse fournie.

  • Liste des références utilisées pour le plan :

    Pas de réponse fournie.

  • Résumé de l'échange avec le jury (questions/réponses/remarques) :

    Question sur le développement :
    - J'avais commencé par montrer l'indécidabilité du problème de l'acceptation en l'appelant problème de l'arrêt. Un jury m'a demandé si c'était vraiment ça le problème de l'arrêt, j'ai répondu que non, et il m'a demandé le lien entre problème de l'arrêt et problème de l'acceptation (ils sont équivalents). Ils m'ont demandé de prouver que tout langage reconnaissable se réduit au problème de l'acceptation et m'ont fait remarqué que le résultat que je prouvais montre en fait la complétude du problème de l'acceptation pour la reconnaissabilité.

    Question sur le plan :
    - J'avais mis une remarque sur l'impossibilité pour un compilateur de déterminer si un while termine en règle générale, ils m'ont demandé le rapport exact avec les problèmes décrits.
    - Le théorème de Rice est-il un résultat sur les machines de turing ou sur les langages ? Exemple d'applications ? (Langage du vide)

    Autres :
    - Langages de polynomes : le langage des polynomes à une variable à coefficients entiers admettant une racine entière est-il reconnaissable (oui), décidable (oui, j'ai mit longtemps à montrer qu'on peut borner l'espace sur lequel chercher les racines en fonction des coefficients). Que ce passe-t-il si on prend deux variables ? (C'est toujours reconnaissable, mais plus décidable).
    - Langages récursivement énumérable et reconnaissable est-ce la même chose ? Pourquoi ? Y-a-t il des langages non reconnaissables ? (oui, le complémentaire du langage de l'acceptation) ? Des langages non reconnaissable et non co-reconnaissables ? (Oui, par dénombrabilité, mais un exhiber un est compliqué) ? Un langage récursivement énumérable par ordre lexicographique est-il décidable, et réciproquement (oui, dans les deux sens).
    - existence de fonction non-calculable : est-ce qu'on a besoin d'exhiber le castor affairé ? (Non, par un argument de dénombrabilité) Exemple de fonction totale calculable non récursive primitive ? (Ackerman) Y-a-t il des fonctions récursives dont le graphe n'est pas décidable ? (Les fonctions partielles) Si on considère la réciproque du castor affairé, qu'est-ce qu'on calcule ? (Je n'ai pas su répondre, en fait c'est la compression optimale, i.e. la complexité de Komogorov, dont on prouve ainsi qu'elle n'est pas calculable).

  • Quelle a été l'attitude du jury (muet/aide/cassant) ?

    Jury souriant, mais fatigué. Ils m'ont aidé quand c'était nécessaire, mais ils ont surtout cherché à m'empêcher de partir dans des impasses. Par contre quand je rebondissais sur les questions pour chercher à aller plus loin ils me laissaient chercher un peu.

  • L'oral s'est-il passé comme vous l'imaginiez ou avez-vous été surpris par certains points ? Cette question concerne aussi la préparation.

    Pas de réponse fournie.

  • Note obtenue :

    Pas de réponse fournie.


Références utilisées dans les versions de cette leçon :

Introduction to the theory of computation , Sipser (utilisée dans 12 versions au total)
Langages formels, Calculabilité et Complexité, Carton (utilisée dans 19 versions au total)
Calculabilité et décidabilité , Autebert (utilisée dans 3 versions au total)
Introduction à la calculabilité, Wolper (utilisée dans 3 versions au total)
Introduction à l'informatique théorique: calculabilité & complexité, Arto Salomaa (utilisée dans 2 versions au total)
Mathématiques de l'informatique , Dehornoy (utilisée dans 8 versions au total)
Logique et fondements de l'informatique, Rougemont, Lassaigne (utilisée dans 6 versions au total)