Vocabulaire
Connaître- a.Définis : fonction calculable, problème indécidable.
›Voir le corrigéMasquer le corrigé
- Fonction calculée par un algorithme en un nombre fini d'étapes.
- Problème qu'aucun algorithme ne résout dans tous les cas.
NSITleTerminaleSans inscriptionProgramme en vigueur — arrêtés du 19 juillet 2019, applicable en Terminale depuis la rentrée 2020. Voir le texte
NSI terminale : programme en tant que donnée, interpréteur et compilateur, calculabilité, thèse de Church-Turing, problème de l'arrêt et indécidabilité (Turing, 1936).
La règle d'or
Un programme est une donnée que d'autres programmes manipulent ; certains problèmes, comme celui de l'arrêt, sont indécidables : aucun algorithme ne les résout.
L'erreur que tout le monde fait
Croire qu'indécidable signifie très long à calculer.
Un problème indécidable n'a aucun algorithme qui le résout dans tous les cas, même avec un temps illimité.
Distinguer « difficile » et « impossible ».
Un ordinateur peut-il tout calculer ? Peut-on écrire un programme qui détecte si n'importe quel autre programme va boucler à l'infini ? Alan Turing a montré en 1936 que la réponse est non : il existe des problèmes qu'aucun algorithme ne peut résoudre.
Un programme est un texte, donc une donnée qu'un autre programme peut lire, analyser ou exécuter : c'est ce que font un interpréteur (Python), un compilateur, un antivirus ou un système d'exploitation qui lance une application.
fonction calculable — Fonction qu'un algorithme peut calculer en un nombre fini d'étapes, quelle que soit l'entrée.
Ce qui est calculable ne dépend pas du langage de programmation : Python, C ou une machine de Turing calculent les mêmes fonctions (thèse de Church-Turing).
problème de l'arrêt — Déterminer, pour tout programme P et toute entrée e, si P s'arrête sur e. Turing a démontré en 1936 qu'aucun programme ne peut le résoudre : il est indécidable.
Idée de la preuve : si un programme arret(P, e) existait, on construirait un programme paradoxe(P) qui boucle quand arret(P, P) répond vrai et s'arrête sinon ; paradoxe(paradoxe) mène alors à une contradiction.
Pourquoi un antivirus ne peut-il pas détecter à coup sûr tout comportement malveillant ?
L'indécidabilité impose des limites théoriques aux outils qui analysent des programmes.
Croire qu'indécidable signifie très long à calculer.
Pourquoi — Un problème indécidable n'a aucun algorithme qui le résout dans tous les cas, même avec un temps illimité.
Le réflexe — Distinguer « difficile » et « impossible ».
L'essentiel en 3 points
Gratuit · sans compte
Trois documents à imprimer, 4 pages en tout : le cours, les exercices avec la place pour écrire, et le corrigé détaillé avec son barème.
Au sommaire du cours
Conforme au programme officiel · version 2026.2.
Ce qui rapporte des points, ce qui en coûte
Raisonner par l'absurde sur l'arrêt
Supposer qu'un programme arret existe.
Construire paradoxe qui fait l'inverse de ce que prédit arret.
Appliquer paradoxe à lui-même.
Aucun compte requis — réponds, la correction s'affiche aussitôt.
Tes réponses sont déjà comptées dans ce navigateur. Un compte gratuit les conserve d'un appareil à l'autre et débloque le suivi de tes points faibles.
Avec un compte gratuit
1 · Ta séance du jour
Calculabilité — décidabilité, problème de l'arrêt
3 minutes, sur ce qui résiste
2 · Ta progression, vue aussi par tes parents
3 · Tes erreurs, rejouées
Gratuit, sans carte bancaire. Les chiffres ci-dessus sont un exemple d'affichage.
Ce chapitre est au programme de NSI au lycée, en classe de Terminale, année du Baccalauréat. Il est défini par le Bulletin Officiel de l'Éducation nationale, le texte de référence qui fixe ce qui doit être enseigné dans chaque matière.
NSI terminale : programme en tant que donnée, interpréteur et compilateur, calculabilité, thèse de Church-Turing, problème de l'arrêt et indécidabilité (Turing, 1936). Les notions à maîtriser sont : calculabilité, décidabilité, problème de l'arrêt, Turing, NSI terminale, NSI.
Sur cette page, dans le bloc « Imprimer » : 3 documents à télécharger — le cours, les exercices et le corrigé — soit 4 pages au format A4, prêtes à imprimer. Le téléchargement est gratuit, immédiat, et ne demande ni compte ni adresse e-mail.
Oui, et c'est un document à part : chaque exercice y est repris étape par étape, avec le barème détaillé en fin de fiche — ce qui est attendu, combien de points, et ce qui fait perdre le point. Un parent qui ne se souvient plus du programme peut corriger une copie avec.
Ce chapitre fait partie du programme officiel de Terminale, il entre donc dans le périmètre du Baccalauréat. Le sujet exact varie chaque année et aucun chapitre n'est garanti, mais l'ensemble du programme de l'année est susceptible d'être évalué : mieux vaut ne pas parier sur des impasses.
Commence par lire la fiche de révision pour remettre la règle en place, puis enchaîne immédiatement sur le quiz de cette page. Répondre juste après avoir lu ne suffit pas : reviens sur le chapitre deux ou trois jours plus tard. C'est l'espacement des révisions, plus que leur durée, qui fait tenir une notion en mémoire. Une session de quinze minutes répétée vaut mieux qu'une heure unique.
Non. Les quiz, les corrections détaillées et les fiches de révision sont accessibles sans créer de compte et sans donner d'adresse e-mail. Le compte gratuit sert uniquement à conserver la progression d'un appareil à l'autre.
Les chapitres qui traitent des mêmes notions, ici ou dans une autre année.
Python dès la seconde, exposés, espace numérique de travail : un portable qui suit jusqu'au bac.
Petit budget, 16 Go
Acer Aspire Go 15 (Ryzen 5 7430U, 16 Go, 512 Go)
Le prix de référence
HP 15 (Core i5-1334U, 16 Go, 512 Go)
Léger, pour le cartable
Acer Swift Go 14 AI
En tant que Partenaire Amazon, ProgresSchool réalise un bénéfice sur les achats remplissant les conditions requises.
Les annales de la matière, et le grand oral.
Grand oral
Prépabac Le Grand Oral, terminale générale, bac 2027
Hatier
Réviser la philosophie
Prépabac philosophie, terminale générale, bac 2027
Hatier
En tant que Partenaire Amazon, ProgresSchool réalise un bénéfice sur les achats remplissant les conditions requises.