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

(2016) 914
(2018) 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 :

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


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


Retours d'oraux :

Pas de retours pour cette leçon.

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

Calculabilité et décidabilité , Autebert (utilisée dans 3 versions au total)
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)
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)