Calculabilité, décidabilité =========================== ... ou l'étude des possibilités et limites des algorithmes <br><br> *Ce document a été créé en collaboration avec Bing Copilot (relié à GPT4) pour transposer le cours correspondant (accessible [ici](recherche-textuelle)) en un diaporama.* *Pour voir la conversation avec Copilot : [cliquer ici](https://copilot.microsoft.com/sl/cRLnEzsqfVk)* --- # Introduction --- ## Le problème de décision de Hilbert - Question posée par David Hilbert en 1928 : « *Existe-t-il un algorithme capable de déterminer, pour tout énoncé mathématiques bien formulé, si ce dernier est vrai ou faux ?* » <img class="r-stretch centre image-responsive" alt="Alonzo Church" src="data/David_Hilbert.jpg"> - C'est l'origine de la **théorie de la calculabilité**. ---- ## Le problème de décision de Hilbert - Réponse négative apportée indépendamment par Alonzo Church et Alan Turing en 1936. - Excellente vidéo retraçant cette histoire : <iframe width="560" height="315" src="https://www.youtube-nocookie.com/embed/Zci9m08HQws" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe> <small>Crédits : Voyages au pays des maths, ARTE</small> --- ## Programme en tant que donnée - Idée clé de la théorie de la calculabilité : **un programme est une donnée comme une autre** - Concrètement : un programme peut être lu, écrit et exécuté par d'autres programmes. - Exemples : - Commande `python` : est un programme (ici c'est l'**interpréteur** Python) qui exécute d'autres programmes ```bash python prog.py ``` - **Compilateur** : un programme qui convertit un autre programme en langage machine. ---- ## Programme en tant que donnée - Autres exemples : - pour **télécharger un programme** (logiciel) on utilise des programmes (navigateur, gestionnaire de téléchargement) - **système d'exploitation** : programme qui gère tous les autres - **antivirus** : programme scanne d'autres programmes - **virus informatique** : programme qui prend en entrée un programme et en produit d'autres (infectés) ---- ### Même en Python... - Une fonction peut prendre d'autres fonctions en paramètres. - Exemple : la fonction `sorted` avec le paramètre `key` qui est une fonction. ```python >>> animaux = ['vache', 'anaconda', 'chat', 'chien', 'ver', 'poule', 'souris'] >>> sorted(animaux, key=len) # fonction len passée en paramètre ['ver', 'chat', 'vache', 'chien', 'poule', 'souris', 'anaconda'] ``` - `doctest.testmod()` : fonction qui prend en entrées des fonctions, les exécute et vérifie leur comportement --- # Calculabilité --- ## Quelques définitions - Un *algorithme* est une méthode de calcul qui peut être vue comme une *fonction mathématique* (paramètres en entrée et calcule un résultat) - La **théorie de la calculabilité** étudie les fonctions qui peuvent être calculées par un algorithme. - Une fonction est dite **calculable** si elle peut être calculée par un algorithme en un nombre fini d'étapes. ---- ## Quelques définitions - Il existe des fonctions calculables (ex : le pgcd de deux nombres) mais d'autres ne le sont pas (nous en verrons) - La théorie de la calculabilité permet de **comprendre les limites des problèmes que peuvent résoudre les ordinateurs**. - Théorie (à la frontière entre mathématiques et informatique) développée dans les années 1930 par **Alan Turing** et **Alonzo Church** qui essayaient de répondre au problème de décision de Hilbert --- ## La vision de Church <img class="r-stretch centre image-responsive" alt="Alonzo Church" src="data/Alonzo_Church.jpg"> - **Alonzo Church** (américain) a proposé une définition (mathématique) des fonctions calculables. - Il a introduit le **$\lambda$-calcul**, un langage pour décrire les fonctions calculables : c'est l'ancêtre des langages de programmation - Dans ce langage : une fonction est **calculable** si elle peut s'exprimer comme une $\lambda$-expression. ---- ## La vision de Church - Le $\lambda$-calcul considère qu'**une fonction est une donnée comme une autre**, qui peut être passée en paramètre à une fonction et aussi le résultat d'une fonction. - Les $\lambda$-expressions ont une structure définie *récursivement* : la théorie de Church est à la base des langages de *programmation fonctionnelle*. ---- ## La vision de Church (exemples) - Exemples de $\lambda$-expressions (ni à connaître, ni même à comprendre) : - L'entier 0 est $\lambda f.\lambda x. x$ - L'entier 1 est $\lambda f.\lambda x.f(x)$ - La fonction $f:x \longmapsto x+1$ est calculable car elle peut s'exprimer ainsi : $\lambda x.\lambda f.\lambda z.x(f)(f(z))$ - En Python : ```python zero = lambda f: lambda x: x un = lambda f: lambda x: f(x) ajouter_un = lambda x: lambda f: lambda z: x(f)(f(z)) ``` ```python # Utilisation de la fonction pour ajouter 1 au nombre un deux = ajouter_un(un) ``` ---- ## La vision de Church (exemples) - Comment vérifier que `deux` correspond bien à l'entier 2 ? ... pas évident car `deux` est alors une fonction et non un nombre entier - `deux` est une fonction qui applique une autre fonction `f` à un argument `x` (en écrivant `deux(f)(x)`) - Elle doit normalement appliquer *deux* fois (c'est ce qu'on veut vérifier !) la fonction `f` en partant de l'argument `x` - Vérification avec `f` qui est la fonction `triple` : ```python >>> triple = lambda x: x * 3 >>> deux(triple)(1) # calcule bien 1 * 3 * 3 9 >>> deux(triple)(2) # calcule bien 2 * 3 * 3 18 >>> deux(triple)(5) # calcule bien 5 * 3 * 3 45 ``` --- ## La vision de Turing <img class="r-strecth centre image-responsive" alt="Portrait d'Alan Turing" src="data/Alan_Turing.jpg"> - **Alan Turing** (britannique) propose une définition mécanique approche mécanique du calcul et donc des fonction calculables - Il a définit les **machines de Turing** (concept *abstrait* malgré son nom) pour décrire les fonctions calculables - Pour Turing : une fonction est **calculable** si elle peut être calculée par une machine de Turing. ---- ## La vision de Turing - Qu'est-ce qu'une **machine de Turing** ? - une tête de lecture/écriture - un ruban infini - un ensemble de règles pour indiquer ce que doit faire la machine dans chaque situation <img class="r-stretch centre image-responsive" alt="Vue d'artiste d'une machine de Turing" src="data/machine_turing.png"> ---- ## La vision de Turing (exemple) - Exemple : la fonction $f:x\mapsto x+1$ est calculable car elle peut être calculée par la machine de Turing suivante <iframe class="centre" loading="lazy" src="https://animations.interstices.info/machine-turing/index.html" width="745" height="350" frameborder="0" scrolling="no"></iframe> <p class="legende"><small>Animation HTML5/JS réalisée par Hugo Lehmann, <a href="https://centralelilleprojets.fr/" target="_blank">Centrale Lille Projets</a>, librement adaptée d’une <a title="Machine de Turing" href="https://interstices.info/machine-de-turing/" target="_blank" rel="noopener">applet Java</a> écrite par Hamdi Ben Abdallah.</small></p> ---- ## La vision de Turing - Chaque machine est monotâche ? - Non ! Turing a montré qu'il existe des **machines de Turing universelles** : elles peuvent simuler l'exécution de n'importe quelle autre machine de Turing $M$ sur une entrée $e$. - On retrouve ici qu'**un programme** (une machine) **est une donnée comme une autre** : peut être donné en entrée à un autre programme (une autre machine). - Machine de Turing universelle : ancêtre des ordinateurs programmables. --- ## Universalité de la calculabilité - Les théories développées par Church et Turing sont équivalentes ! - **Thèse de Church-Turing** : fonctions $\lambda$-calculables = fonctions calculables par machines de Turing. - Traduction : *tout problème qui peut être résolu, peut l’être par une machine de Turing ou par une fonction de Church* - Affirmation jamais encore contredite - Traduction contemporaine : tout ce que le plus puissant des ordinateurs peut faire, une (simple) machine de Turing peut le faire aussi. ---- ## Universalité de la calculabilité - Tous les langages de programmation ordinaires sont construits pour permettre de calculer exactement les mêmes choses qu'une machine de Turing (ou que les fonctions de Church) : on dit qu'ils sont *Turing-complets*. - Conséquence : **la calculabilité ne dépend pas du langage de programmation** - Si un problème peut être résolu dans un certain langage de programmation, il peut l'être dans tous les autres - Si un problème ne peut pas être calculé par une machine de Turing ou une fonction de Church, il ne peut être résolu par aucun programme (donc par aucun ordinateur) --- # Décidabilité --- ## Définitions - **Problème de décision** : problème dont la réponse est oui ou non - Exemples : 3 est-il premier ? ce programme contient un virus ? ce programme renvoie la valeur 42 ? le problème de décision de Hilbert ! ... - Un problème de décision est : - **décidable** si la solution est calculable (= il existe un algorithme qui calcule la solution) - **indécidable** sinon (= aucun algorithme ne peut donner la solution) - Turing et Church ont chacun explicité un problème de décision **indécidable** --- ## Le problème de l'arrêt (Turing) - Question : « *Existe-t-il un algorithme (ou un programme) universel capable de déterminer, à partir d'un programme et d'une entrée, si ce programme s'arrête avec cette entrée ou non ?* » - Réponse de Turing : **Non** ! Il a démontré qu'il n'existait pas de machine de Turing qui résout le problème de l'arrêt. - Donc : **le problème de l'arrêt est indécidable**. ---- ### Une démonstration avec Python - On *raisonne par l'absurde* : on suppose le contraire de ce qu'on veut montrer et cela va nous amener à une contradiction - Supposons qu'il existe une fonction `arret` qui résout le problème de l'arrêt. ```python def arret(prog, x): """Fonction qui renvoie Vrai si prog(x) termine, False sinon.""" ... # inutile d'écrire quoi que ce soit ``` - Définissons une fonction `paradoxe` qui utilise `arret`. ```python def paradoxe(prog): if arret(prog, prog): # si prog(prog) termine while True: pass else: return False ``` ---- ### Une démonstration avec Python ```python [] def paradoxe(prog): if arret(prog, prog): # si prog(prog) termine while True: pass else: return False ``` **Quel est le résultat de l'appel `paradoxe(paradoxe)` ?** - 1er cas : `paradoxe(paradoxe)` rentre dans une boucle infinie si `arret(paradoxe, paradoxe)` est vrai donc si `paradoxe(paradoxe)` termine : *contradiction !* - 2ème cas : `paradoxe(paradoxe)` termine (en renvoyant `False`) si `arret(paradoxe, paradoxe)` est faux donc si `paradoxe(paradoxe)` ne termine pas : *contradiction !* ---- ### Une démonstration avec Python - Dans les deux cas, nous obtenons une contradiction. - Cela signifie que notre supposition de départ est fausse : une fonction `arret` ne peut pas exister ! - Le problème de l'arrêt est indécidable ! > Remarquez à nouveau que la démonstration proposée utilise un programme comme une donnée qui peut être passée à un autre programme. --- ## Le problème de l'égalité de deux fonctions (Church) - Question : « *Existe-t-il un algorithme (ou un programme) universel capable de déterminer si deux programmes font exactement la même chose sur les mêmes entrées.* » - Réponse de Church : Non, **le problème de l'égalité de fonctions est indécidable**. - La démonstration, qui s'appuie sur le $\lambda$-calcul, est hors de portée --- ## Et le problème de Hilbert ? - Turing et Church ont montré respectivement que, comme les problèmes de l'arrêt et de l'égalité de fonctions sont indécidables alors le **problème de décision de Hilbert est aussi indécidable**. - Il ne peut pas exister d'algorithme universel capable de décider si un énoncé mathématique est vrai ou faux. - (Turing a raisonné par l'absurde : il a montré que si l'*Entscheidungsproblem* était calculable par une machine de Turing, alors le problème de l'arrêt le serait également. Mais comme ce n'est pas le cas, il y a une contradiction. Donc l'*Entscheidungsproblem* est indécidable.) --- ## Indécidabilité : compléments - Indécidabilité concerne des fonctions qui doivent répondre pour *toutes* les entrées possibles. - Un problème général indécidable ne signifie pas qu'on ne peut pas y répondre dans des cas particuliers - Exemples : - on peut prouver que certain énoncés mathématiques sont vrais - on peut prouver que la fonction suivante s'arrête sur toute entrée entière `n` positive (en utilisant un *variant de boucle*): ```python def marrete_je(n): while n >= 0: print("Bonjour") n = n - 1 ``` ---- ## Indécidabilité : compléments - **Gordon Rice** généralise le problème de l'arrêt - Théorème de Rice (1951) : *toute propriété non triviale sur le comportement d'un programme est indécidable*. - Exemples : il n'existe pas d'algorithme général qui répond à coup sûr aux questions suivantes : - « le programme ne renvoie jamais la valeur 42 » - « le programme ne termine jamais par une erreur d'exécution » - « le programme calcule un résultat correct par rapport à sa spécification » - « le programme contient un virus » ---- ## Indécidabilité : compléments - Conséquences : - on ne peut pas savoir ce que fait un programme sans le faire tourner - la preuve automatique de programmes est difficile - il n'existe pas d'antivirus totalement efficace : ces derniers analysent le code source pour détecter une signature malveillante mais ne se posent pas la question : « ce que fait ce code est il dangereux ? » (ce serait inutile d'après le théorème de Rice) --- # Bilan --- ## Bilan - Théorie de la calculabilité : - Quelles fonctions peuvent être calculées par un algorithme ? - Ces fonctions sont dites **calculables** - Permet de savoir : - quels problèmes peuvent ou ne pas être résolus - quelles sont les limites des ordinateurs - Church et Turing ont développé de manière différente leur théorie de la calculabilité pour définir la notion de fonction calculable : - approche *mathématique* pour Church : langage appelé $\lambda$-calcul - approche *informatique* pour Turing : machine de Turing ---- ## Bilan - Les deux théories sont équivalentes (c'est la *thèse de Church-Turing*) : fonctions de Church = fonctions calculables par machines de Turing - Elles ont une portée universelle : tout problème qui peut être résolu peut l’être par une machine de Turing, ou par une fonction de Church - Tous les langages de programmation ordinaires (peu importe le paradigme) sont construits pour permettre de calculer exactement les mêmes choses qu'une machine de Turing (ou que les fonctions de Church) ---- ## Bilan - Conséquence : **la calculabilité ne dépend pas du langage de programmation** - tout problème qui peut être résolu par un programme dans un langage de programmation peut l’être dans tous les autres (et aussi par une machine de Turing) - tout ce que le plus puissant des ordinateurs peut faire, une (simple) machine de Turing peut le faire aussi. - un problème qui ne peut pas être résolu par une machine de Turing ne peut l'être par aucun ordinateur ---- ## Bilan - **Problème de décision** : problème dont la réponse est oui ou non - Un tel problème est **décidable** si la solution est calculable par un algorithme pour chaque entrée, **indécidable** sinon - Le **problème de l'arrêt** (démontré par Turing) est un exemple de problème indécidable : il ne peut exister d'algorithme général qui prendrait en entrée un programme $P$ (et une entrée $e$ de ce programme) et qui puisse déterminer si ce programme $P$ va s'arrêter (sur l'entrée $e$) - La **décidabilité** est également **indépendante du langage de programmation utilisé**. --- ### Références - Document ressource de l'équipe éducative du DIU EIL de l'Université de Nantes, diffusé sous licence CC BY : [Les barrières de l'informatique](data/diu2019_bloc5_séance5.pdf) (Bloc 5, Séance 5) - Livre *Spécialité Numérique et sciences informatiques : 24 leçons avec exercices corrigés - Terminale*, éditions Ellipses, T. Balabonski, S. Conchon, J.-C. Filliâtre, K. Nguyen. Site du livre : [http://www.nsi-terminale.fr/] - Livre *Prépabac, NSI, Terminale*, éditions Hatier, G. Connan, V. Petrov, G. Rozsavolgyi, L. Signac. - Articles Wikipédia : [Théorie de la calculabilité](https://fr.wikipedia.org/wiki/Th%C3%A9orie_de_la_calculabilit%C3%A9), [Théorème de Rice](https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Rice) - Article Interstices : [Comment fonctionne une machine de Turing ?](https://interstices.info/comment-fonctionne-une-machine-de-turing/) --- Germain BECKER, Lycée Mounier, ANGERS Ressource éducative libre distribuée sous [Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International](http://creativecommons.org/licenses/by-sa/4.0/)