(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.