💻 NSITleTerminaleSans inscription

Calculabilité — décidabilité, problème de l'arrêt

Programme 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 ».

Notions à maîtriser

  • calculabilité
  • décidabilité
  • problème de l'arrêt
  • Turing
  • NSI terminale
  • NSI
  • Python
1

Réviser

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.

1Un programme est une donnée

Règle

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.

2Calculabilité

Définition

fonction calculable — Fonction qu'un algorithme peut calculer en un nombre fini d'étapes, quelle que soit l'entrée.

Règle

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

3Le problème de l'arrêt

Définition

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.

Règle

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.

Exemple

Pourquoi un antivirus ne peut-il pas détecter à coup sûr tout comportement malveillant ?

  1. Prévoir le comportement d'un programme quelconque revient à des problèmes comme celui de l'arrêt.
  2. Ces problèmes sont indécidables en général.
  3. L'antivirus utilise donc des signatures et des heuristiques, sans garantie absolue.

L'indécidabilité impose des limites théoriques aux outils qui analysent des programmes.

Piège

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

Raisonner par l'absurde sur l'arrêt

  1. Supposer qu'un programme arret existe.
  2. Construire paradoxe qui fait l'inverse de ce que prédit arret.
  3. Appliquer paradoxe à lui-même.
  4. Conclure à la contradiction : arret n'existe pas.
  • ▢Ai-je défini le vocabulaire ?
  • ▢Mon code est-il testé sur un exemple ?
  • ▢Ai-je traité les cas limites ?
  • ▢Ai-je justifié la complexité ou le résultat ?

L'essentiel en 3 points

  • ·Un programme est une donnée : interpréteurs, compilateurs, antivirus.
  • ·Calculabilité ; indépendance vis-à-vis du langage (thèse de Church-Turing).
  • ·Problème de l'arrêt : indécidable (Turing, 1936) ; preuve par l'absurde.
2

Imprimer

Fiche PDF — Calculabilité — décidabilité, problème de l'arrêt

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

  1. 1. Un programme est une donnée
  2. 2. Calculabilité
  3. 3. Le problème de l'arrêt

Conforme au programme officiel · version 2026.2.

3

Exercices corrigés

1

Vocabulaire

Connaître
  1. a.Définis : fonction calculable, problème indécidable.
›Voir le corrigé
  1. Fonction calculée par un algorithme en un nombre fini d'étapes.
  2. Problème qu'aucun algorithme ne résout dans tous les cas.
2

Exemples

Connaître
  1. a.Cite deux programmes qui prennent un programme en entrée.
›Voir le corrigé
  1. Un interpréteur Python, un compilateur (ou un antivirus).
3

Repère

Connaître
  1. a.Qui a démontré l'indécidabilité du problème de l'arrêt, et quand ?
›Voir le corrigé
  1. Alan Turing, en 1936.
4

Langage

Analyser
  1. a.Un problème indécidable en Python devient-il décidable en C ?
›Voir le corrigé
  1. Non : la calculabilité ne dépend pas du langage.
5

Distinguer

Analyser
  1. a.Trier un million de nombres est-il un problème indécidable ?
›Voir le corrigé
  1. Non : c'est décidable, des algorithmes efficaces existent.
6

Preuve

Rédiger
  1. a.Résume en deux phrases la preuve de Turing.
›Voir le corrigé
  1. Si arret existait, paradoxe(paradoxe) s'arrêterait si et seulement s'il ne s'arrête pas.
  2. Cette contradiction prouve qu'arret ne peut pas exister.

Ce qui rapporte des points, ce qui en coûte

  • Vocabulaire2 ptsPerdu si : Définitions floues
  • Code juste et testé2 ptsPerdu si : Cas limites oubliés
  • Justification1 ptPerdu si : Résultat non expliqué
4

La méthode

Raisonner par l'absurde sur l'arrêt

  1. 1

    Supposer qu'un programme arret existe.

  2. 2

    Construire paradoxe qui fait l'inverse de ce que prédit arret.

  3. 3

    Appliquer paradoxe à lui-même.

5

Se tester

NSITerminale
Question 1
Quel raisonnement sert à démontrer l'indécidabilité du problème de l'arrêt ?

Aucun compte requis — réponds, la correction s'affiche aussitôt.

Signaler une erreur

Garder ta progression ?

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

La fiche et les exercices restent ouverts. Le compte, lui, te dit quoi travailler.

1 · Ta séance du jour

Calculabilité — décidabilité, problème de l'arrêt

3 minutes, sur ce qui résiste

Commencer

2 · Ta progression, vue aussi par tes parents

  • Maths72 %
  • Français58 %
  • Histoire-géo41 %
  • SVT64 %

3 · Tes erreurs, rejouées

  • Ta réponse, et où elle déraille
  • La bonne, avec l'explication
Rejouer

Gratuit, sans carte bancaire. Les chiffres ci-dessus sont un exemple d'affichage.

Questions fréquentes

Calculabilité — décidabilité, problème de l'arrêt : c'est en quelle classe ?

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.

Que faut-il savoir sur Calculabilité — décidabilité, problème de l'arrêt ?

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.

Où télécharger la fiche PDF de Calculabilité — décidabilité, problème de l'arrêt ?

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.

Le corrigé de Calculabilité — décidabilité, problème de l'arrêt est-il fourni ?

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.

Calculabilité — décidabilité, problème de l'arrêt peut-il tomber au Baccalauréat ?

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.

Comment réviser Calculabilité — décidabilité, problème de l'arrêt efficacement ?

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.

Faut-il un compte pour s'entraîner sur Calculabilité — décidabilité, problème de l'arrêt ?

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.

Notions voisines

Les chapitres qui traitent des mêmes notions, ici ou dans une autre année.

Un ordinateur pour le lycé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.

Pour réviser le bac

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.