Un problème décidable est un problème :

Qui admet un algorithme terminant toujours avec la bonne réponse

La thèse de Church-Turing affirme que :

Tout algorithme effectif peut être simulé par une machine de Turing

Pourquoi ne pas utiliser assert pour valider les entrées utilisateur ?

Parce que les assertions peuvent être désactivées en production (python -O)

Un invariant de boucle est :

Une propriété vraie à chaque itération de la boucle

Quel cas est essentiel dans un jeu de tests pour factorielle(n) ?

n = 0 (cas limite). Le cas n = 0 est un cas limite fondamental car 0! = 1 par convention. Les cas limites sont souvent sources de bugs et doivent toujours être testés.

La thèse de Church-Turing affirme que :

Tout algorithme effectif peut être simulé par une machine de Turing. La thèse de Church-Turing pose que tout ce qui est intuitivement calculable peut être calculé par une machine de Turing. C'est une thèse (non prouvable) fondamentale de l'informatique.

Pourquoi ne pas utiliser assert pour valider les entrées utilisateur ?

Parce que les assertions peuvent être désactivées en production (python -O). Les assertions peuvent être désactivées avec l'option -O de Python. Pour la validation des entrées utilisateur, il faut utiliser if/raise qui fonctionnent toujours.

Un invariant de boucle est :

Une propriété vraie à chaque itération de la boucle. Un invariant de boucle est une propriété qui reste vraie avant et après chaque itération. Il permet de raisonner sur la correction de l'algorithme.

La preuve d'indécidabilité du problème de l'arrêt utilise :

Un raisonnement par l'absurde. Turing suppose qu'un programme H résolvant le problème de l'arrêt existe, construit un programme paradoxal qui mène à une contradiction, donc H ne peut pas exister.

NSI (Spé) — Langages et programmation

Calculabilité, décidabilité et mise au point

Q: Le problème de l'arrêt est :

Indécidable. Le problème de l'arrêt est indécidable : il n'existe aucun algorithme capable de déterminer, pour tout programme et toute entrée, si le programme s'arrête ou boucle indéfiniment.

Q: Qui a démontré l'indécidabilité du problème de l'arrêt ?

Alan Turing. Alan Turing a démontré en 1936, par un raisonnement par l'absurde, qu'il est impossible d'écrire un programme universel qui détermine si un programme donné s'arrête.

Q: Que fait l'instruction 'assert x > 0' en Python ?

Vérifie que x > 0, sinon lève AssertionError. assert x > 0 vérifie la condition x > 0. Si elle est fausse, Python lève une AssertionError et le programme s'arrête (sauf si les assertions sont désactivées).

Problèmes décidables et indécidables, problème de l'arrêt, tests, assertions, mise au point de programmes

Résumé synthétiqueFiche en 4 sectionsQuiz de 10 questionsGratuit, sans pub

Résumé

La calculabilité étudie les limites théoriques de ce qu'un ordinateur peut résoudre. Un problème est décidable s'il existe un algorithme qui termine toujours et donne la bonne réponse (oui ou non). Par exemple, tester si un nombre est premier est décidable. Le problème de l'arrêt est le plus célèbre problème indécidable : il n'existe pas d'algorithme capable de déterminer, pour tout programme et toute entrée, si le programme terminera ou bouclera indéfiniment. Alan Turing l'a démontré en 1936 par un raisonnement par l'absurde. La mise au point (debugging) repose sur les assertions (assert condition), les tests unitaires, les préconditions et postconditions. Par exemple, assert n >= 0 vérifie une précondition. Le jeu de tests doit couvrir les cas normaux, les cas limites (0, liste vide) et les cas d'erreur.

Thème complet

Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale

Ce thème dans une autre classe

Seconde — Mathématiques

Algorithmique et programmation

Première — Mathématiques

Algorithmique et programmation Python

Première — Maths (Spé)

Algorithmique et programmation Python

Articles utiles

Spécialités

Bac NSI 2026 : comment réussir l'épreuve écrite et pratique

Questions fréquentes

Les points clés à retenir sur Calculabilité, décidabilité et mise au point, extraits du quiz de révision.

Le problème de l'arrêt est :

Réponse : Indécidable

Le problème de l'arrêt est indécidable : il n'existe aucun algorithme capable de déterminer, pour tout programme et toute entrée, si le programme s'arrête ou boucle indéfiniment.

Qui a démontré l'indécidabilité du problème de l'arrêt ?

Réponse : Alan Turing

Alan Turing a démontré en 1936, par un raisonnement par l'absurde, qu'il est impossible d'écrire un programme universel qui détermine si un programme donné s'arrête.

Que fait l'instruction 'assert x > 0' en Python ?

Réponse : Vérifie que x > 0, sinon lève AssertionError

assert x > 0 vérifie la condition x > 0. Si elle est fausse, Python lève une AssertionError et le programme s'arrête (sauf si les assertions sont désactivées).

Une précondition est :

Réponse : Une condition qui doit être vraie avant l'exécution d'une fonction

Une précondition est une condition qui doit être satisfaite avant l'appel d'une fonction pour garantir son bon fonctionnement. Ex : le paramètre n doit être positif.

Résumé

Questions fréquentes

Les points clés à retenir sur Calculabilité, décidabilité et mise au point, extraits du quiz de révision.

Le problème de l'arrêt est :

Réponse : Indécidable

Le problème de l'arrêt est indécidable : il n'existe aucun algorithme capable de déterminer, pour tout programme et toute entrée, si le programme s'arrête ou boucle indéfiniment.

Qui a démontré l'indécidabilité du problème de l'arrêt ?

Réponse : Alan Turing

Alan Turing a démontré en 1936, par un raisonnement par l'absurde, qu'il est impossible d'écrire un programme universel qui détermine si un programme donné s'arrête.

Que fait l'instruction 'assert x > 0' en Python ?

Réponse : Vérifie que x > 0, sinon lève AssertionError

assert x > 0 vérifie la condition x > 0. Si elle est fausse, Python lève une AssertionError et le programme s'arrête (sauf si les assertions sont désactivées).

Une précondition est :

Réponse : Une condition qui doit être vraie avant l'exécution d'une fonction

Une précondition est une condition qui doit être satisfaite avant l'appel d'une fonction pour garantir son bon fonctionnement. Ex : le paramètre n doit être positif.

Calculabilité, décidabilité et mise au point

Résumé

Calculabilité et décidabilité

Le problème de l'arrêt

Assertions et préconditions/postconditions

Tests et mise au point

Quiz - Calculabilité, décidabilité et mise au point

Ce thème dans une autre classe

Articles utiles

Questions fréquentes

Calculabilité, décidabilité et mise au point

Résumé

Calculabilité et décidabilité

Le problème de l'arrêt

Assertions et préconditions/postconditions

Tests et mise au point

Quiz - Calculabilité, décidabilité et mise au point

Ce thème dans une autre classe

Articles utiles

Questions fréquentes