Contenus | Capacités attendues | Commentaires |
|---|---|---|
Notion de programme en tant que donnée. Calculabilité, décidabilité. | Comprendre que tout programme est aussi une donnée. Comprendre que la calculabilité ne dépend pas du langage de programmation utilisé. Montrer, sans formalisme théorique, que le problème de l’arrêt est indécidable. | L’utilisation d’un interpréteur ou d’un compilateur, le téléchargement de logiciel, le fonctionnement des systèmes d’exploitation permettent de comprendre un programme comme donnée d’un autre programme. |
Comme nous l'avons vu en première, un programme est la traduction électronique d'un algorithme afin qu'il puisse être compris par une machine. Dans ce chapitre, nous allons montrer qu'un programme ne peut pas tout calculer ou décider.
Certains programmes utilisent comme données le code source d'autres programmes.
La notion de calculabilité date de 1936, il s'agit de savoir ce qui peut être calculé par un ordinateur, et donc permet de voir les limites des problèmes que peuvent résoudre les ordinateurs.
On dira qu’une fonction est calculable si elle peut être programmée dans l’un ou l’autre des langages de programmation usuels. Cette année, nous utiliserons le langage Python comme témoin : une fonction est calculable si on peut la programmer en Python.
Il existe d’autres modèles de calcul, comme le λ-calcul, les fonctions récursives, les machines de Turing, que nous ne développerons pas ici, et qui ne font pas partie des attendus du programme.
La thèse de Church postule que tous ces modèles de calcul sont équivalents : une fonction calculable pour un modèle l’est pour un autre. Cela nous permet d’utiliser le modèle des fonctions programmables en Python sans perdre de généralité.
Calculabilité et décidabilité sur eduscol
On peut calculer beaucoup de choses avec un ordinateur comme le nombre , les nombres rationnels , ...
Par contre, il a été prouvé que certains problèmes n'étaient pas calculables comme par exemple :
Il s'agit de problèmes de décidabilité.
Un problème de décision est dit décidable s'il existe un algorithme, une procédure mécanique qui se termine en un nombre fini d'étapes, qui le décide, c'est-à-dire qui réponde par oui ou par non à la question posée par le problème. S'il n'existe pas de tels algorithmes, le problème est dit indécidable. Par exemple, le problème de l'arrêt est indécidable.
Article Wikipédia sur la décidabilité
Tous les sous-ensembles finis des entiers sont décidables, par exemple:
Notons qu'un ensemble peut être théoriquement décidable sans qu'en pratique la décision puisse être faite, parce que celle-ci nécessiterait trop de temps (plus que l'âge de l'univers) ou trop de ressources (plus que le nombre d'atomes de l'univers). L'objet de la théorie de la complexité des algorithmes est d'étudier les problèmes de décision en prenant en compte ressources et temps de calcul.
L'indécidabilité du problème de l'arrêt a été démontrée par Alan Turing en 1936.
On peut l'interpréter ainsi : il n'existe pas de programme permettant de tester n'importe quel programme informatique afin de conclure dans tous les cas s'il s'arrêtera en un temps fini ou bouclera à jamais.
Preuve par l'absurde de non-décidabilité de l'arrêt
Supposons qu'il existe une fonction calculable termine(programme, données) qui prend 2 arguments :
et qui renverra True si le programme termine et False s'il entre dans une boucle infinie.
est_pair() définie dans la partie exercicetermine(est_pair, 128) ou termine(est_pair, 127) renverraient True.
def est_positif(n):
if n >= 0:
return True
else:
while n < 0:
n = n - 1 # boucle infinie
return Falseentrainerait une boucle infinie pour les nombres négatifs, et on aurait :
termine(est_positif, 128) renvoie True alors que termine(est_positif, -2) renverrait False
non pas car -2 n'est pas positif mais parce que l'appel positif(-2) ne se terminerait jamais.
Définissons une fonction test_sur_soi.
def test_sur_soi(programme):
if termine(programme, programme):
while True: pass # boucle infinieOn obtient alors une contradiction si on appelle test_sur_soi sur elle-même :
test_sur_soi(test_sur_soi)
# l'appel éxecutera l'algorithme suivant
if termine(test_sur_soi, test_sur_soi):
while True: passOn arrive au paradoxe suivant :