Le pouvoir de l'algorithmique n'est pas infini. On sait que certains problèmes ne peuvent pas être résolus parfaitement de manière automatique.
L'étude des possibilités et limites des algorithmes définit le champ de la calculabilité, qui est l'un des piliers de la science informatique.
Mettre le résultat ici (code et figure).
Supposons que l'on souhaite réaliser, en Python, un détecteur d'erreurs pour les programmes Python.
Pour fixer les idées, concentrons-nous sur une seule erreur à détecter:
la division par zéro.
On veut donc définir une fonction detecteur prenant en entrée un programme p et renvoyant True si l'exécution de p s'interrompt avec ZeroDivisionError et False sinon.
Mettre le résultat ici (code et figure).
Erreurs
En mathématiques, la division par zéro n'est pas définie. Tenter d'en réaliser une dans un programme Python lève une exception qui interrompt l'exécution du programme.
Tester le code suivant et noter l'erreur:
x = 1/0
Mettre le résultat ici (code et figure).
Le programme en tant que donnée
L'idée qu'un programme puisse n'être qu'une donnée manipulée par un autre programme peut paraître vertigineuse.
Nous l'avons cependant déjà croisée plusieurs fois, et sous différentes formes.
Considérons un programme Python défini dans un fichier don_jose.py :
Programme — don_jose.py
i = 3
while i > 0:
print(\"Prends garde à toi !\")
i = i - 1
print(1 / i)
print(\"Carmen épouse-moi !\")
Ce programme se présente sous la forme d'un fichier de texte contenant une suite de caractères.
Ce fichier est présent dans la mémoire de l'ordinateur et peut être manipulé, déplacé, copié par les autres programmes comme tout autre fichier.
Mieux, on peut même donner ce fichier comme paramètre à l'interprète Python avec la ligne de commande suivante dans le terminal:
$ python don_jose.py
Copier le programme dans le fichier don_jose.py et tester le dans le terminale avec la ligne de commande ci-dessus.
","title":""},{"edit":"Mettre le résultat ici de l'exécution de la ligne de commande.
Ainsi, l'interprète Python lui-même est un exemple de programme prenant
en paramètre un autre programme.
On peut alors imaginer un détecteur fonctionnant de même, avec une fonction prenant en paramètre un nom de fichier à analyser et récupérant le texte qu'il contient.
def detecteur(nom_de_fichier):
fichier = open(nom_de_fichier)
programme = fichier.read()
La variable programme contient alors l'ensemble du programme à analyser, donné sous la forme d'une chaîne de caractères.
Même s'il reste assurément de la distance à parcourir, on peut imaginer qu'une analyse fine du contenu de cette chaîne nous donnera toutes les informations dont nous pourrions avoir besoin à propos du programme.
Détecteur naïf
Une approche très simple de la détection consisterait alors à faire comme l'interprète Python lui-même:
exécuter le programme donné
en paramètre.
La fonction exec fait exactement ceci si on lui donne en paramètre la chaîne de caractères représentant un programme.
Il suffit alors de l'encadrer avec les mécanismes de gestion des exceptions de Python pour détecter d'éventuelles erreurs.
def detecteur_naif(nom_de_fichier):
fichier = open(nom_de_fichier)
programme = fichier.read()
try:
exec(programme) # exécution du programme à analyser
return False
except ZeroDivisionError:
return True
except:
return False
Dans le cas où le programme à analyser complète son exécution sans avoir déclenché d'erreur, on exécute ensuite la ligne return False.
Toute erreur lors de cette exécution déclenche en revanche l'exécution d'un bloc except, et renvoie True en cas de division par zéro et False dans les autres cas.
Exécuter ce détecteur avec la commande suivante et noter le résultat.
erreur = detecteur_naif('don_jose.py')
print(\"Erreur dans don_jose.py?\",erreur)
Le programme intercepte l'erreur et renvoie True (après avoir affiché trois fois «Prends garde à toi!».
Mettre le résultat ici (code et figure).
Ça va durer encore longtemps?
Notre détecteur naïf ne répond hélas pas
complètement au problème posé.
Observons le programme escamiilo.py :
while True:
print(\"Veillez sur vous !\")
print(1 / 0)
Enregistrer ce programme sous escamiilo.py et tester le avec le détecteur d'erreurs. Conclure.
erreur = detecteur_naif('escamiilo.py')
print(\"Erreur dans escamiilo.py?\",erreur)
Ce programme exécute indéfiniment sa boucle sans jamais générer d'erreur.
On attendrait donc du détecteur qu'il renvoie False.
Cependant, l'exécution infinie du programme escamillo empêcherait notre
détecteur d'atteindre ses instructions return:
la détection n'aboutirait pas.
On cherche donc encore un détecteur qui répondrait à tous les coups, quel que soit le comportement fini ou infini du programme à analyser.
Mettre le résultat ici (code et figure).
Ce que cache exec
L''exécution ou l'analyse d'un programme donné par son code source sous la forme d'une chaîne de caractères n'est pas
immédiate.
'i = 3\\nwhile i > 0:\\n print(\"Prends garde à toi !\")\\n i = i - 1\\nprint(1 / i)\\nprint(\"Carmen épouse-moi !\")'
Nous n'avons sous la main qu'une suite de caractères, et toute la structure du programme est à reconstruire en comparant cette suite de caractères et les règles de syntaxe du langage Python.
Le résultat de cette reconstruction est un arbre de syntaxe:
uue structure de données en forme d'arbre reproduisant la structure du programme.
Les fonctions chargées de cette analyse syntaxique en Python sont définies dans le module parse.
![](\"https://sciencesappliquees.com/images/nsi/calcu1.png\")
Un interprète, dans sa forme la plus simple, utiliserait alors cet arbre de
syntaxe pour simuler l'exécution du programme sur une entrée donnée.
Cet arbre de syntaxe peut également être compilé, c'est-à-dire traduit, en une séquence d'instructions élémentaires de type assembleur.
C'est ce qui se passe dans la version de référence de Python, avec une traduction en bytecode :
un langage assembleur qui n'est pas celui de notre ordinateur physique, mais celui d'un ordinateur idéal qui serait dédié à l'exécution des programmes Python (et qui est simulé par le programme python lui-même).
1 0 SETUP_LOOP 12 (to 14)
2 >> 2 LOAD_NAME 0 (print)
4 LOAD_CONST 0 ('Veillez sur vous !')
6 CALL_FUNCTION 1
8 POP_TOP
10 JUMP_ABSOLUTE 2
12 POP_BLOCK
3 >> 14 LOAD_NAME 0 (print)
16 LOAD_CONST 1 (1)
18 LOAD_CONST 2 (0)
20 BINARY_TRUE_DIVIDE
22 CALL_FUNCTION 1
24 POP_TOP
26 LOAD_CONST 3 (None)
28 RETURN_VALUE
En Python, on produit le bytecode avec la fonction compile.
On peut alors soit l'exécuter directement, notamment avec la fonction exec, soit manipuler ses instructions avec les fonctions du module dis.
Tester et analyser les différentes fonctions ci-dessous:
import dis
fichier = open('don_jose.py')
programme = fichier.read()
c = compile(programme, '<string>', 'exec')
print(dir(c))
print(c.co_code)
print(c.co_names)
print(c.co_consts)
dis.dis(c)
Mettre le résultat ici (code et figure).
Impossibilité de la détection
Supposons que quelqu'un ait réussi à écrire en Python une fonction detecteur_parfait, qui réalise un détecteur de divisions par zéro fonctionnant à tous les coups.
Observons alors le programme carmen.py et réfléchissons à son comportement.
Programme - carmen.py
if detecteur_parfait('carmen.py'):
print(\"Tu crois le tenir, il t'évite\")
else:
print(\"Tu crois l'éviter, il te tient\")
print(1 / 0)
Notez qu'il s'agit d'un programme qui s'applique à lui-même notre détecteur parfait de division par zéro, et se comporte ensuite à l'inverse du diagnostic obtenu.
Supposons d'abord que l'exécution du programme carmen résulte en une erreur ZeroDivisionError.
Le détecteur parfait, par définition, renverrait True.
L'exécution passerait dans ce cas par la première branche et ne déclencherait aucune erreur, en contradiction avec notre supposition.
L'exécution du programme carmen ne peut donc pas produire d'erreur ZeroDivisionError. Or, si effectivement cela n'était pas le cas, le détecteur parfait renverrait False, aiguillant l'exécution dans la branche else qui, elle, produirait l'erreur.
Nous avons ici une contradiction qui conclut notre raisonnement par l'absurde:
la fonction detecteur parfait utilisée par notre programme (par ailleurs légitime) carmen.py ne peut pas exister en Python.
Autrement dit le problème de la détection des erreurs ZeroDivisionError dans les programmes Python ne peut pas être résolu par un programme Python.
Mettre le résultat ici (code et figure).
Est-ce dû à une limitation de Python?
Existe-t-il un algorithme exprimable dans un autre langage qui répondrait à notre problème?
Ou avons-nous touché quelque limite plus fondamentale?
Répondre à ces questions implique soit d'élaborer un algorithme comprenant des aspects impossibles à réaliser en Python, ce qui serait une première, soit de justifier qu'aucun algorithme ne saurait résoudre notre problème de détection.
La notion d'algorithme a longtemps existé en mathématiques, désignant an sens large des méthodes de calcul.
Le mot à l'origine faisait référence notamment aux techniques que nous avons apprises à l'école primaire pour réaliser les quatre opérations arithmétiques de base.
De manière générale, un algorithme attend des entrées et calcule un résultat en fonction de ces entrées.
Ainsi, un algorithme réalise une fonction mathématique et on appelle fonction calculable une fonction pour le calcul de laquelle ii existe un algorithme.
Par exemple, la fonction qui a une équation du second degré associe l'ensemble de ses solutions est calculable :
la méthode du discriminant est justement un algorithme réalisant cet objectif.
Cette notion informelle et intuitive a été suffisante jusqu'à la fin du dix-neuvième siècle.
Mais pour répondre à nos questions sur la détection d'erreurs, nous avons besoin d'une vision plus précise de ce qu'est un algorithme et de ce qui est, ou non, calculable par un algorithme.
La caractérisation des fonctions calculables acceptée aujourd'hui a été établie dans les années 1930 et elle constitue l'un des événements fondateurs de l'informatique en tant que science.
Mettre le résultat ici (code et figure).
Programme de Hilbert et Entscheidungsproblem
![](\"https://upload.wikimedia.org/wikipedia/commons/7/79/Hilbert.jpg\")
David Hilbert
1862-1943
Cet événement que nous allons relater est intimement lié à l'essor de l'un des courants majeurs des mathématiques du vingtième siècle :
l'école formaliste.
Le chef de file de ce courant de pensée, David Hilbert, appelle à fonder les mathématiques sur la logique et clame dès 1900 sa conviction que tout énoncé mathématique bien formulé peut être soit démontré, soit réfuté à l'aide de règles de déduction formelles en se ramenant à une base finie de postulats de départ (les axiomes).
Dans ce contexte, Hilbert développe un vaste projet de formulation des mathématiques appelé aujourd'hui programme de Hilbert et y énonce quelques objectifs de référence, dont notamment les démonstrations de la complétude :
tout énoncé vrai peut être démontré
et de la cohérence
aucune contradiction ne peut être obtenue
de cette formulation des mathématiques.
Un dernier objectif, ajouté en 1928 sous le nom d'Entscheidungsproblem (en français, problème de la décision), demande de créer un algorithme déterminant, pour tout énoncé mathématique bien formulé donné en entrée, si ce dernier est vrai ou faux.
On entend ici par algorithme un procédé mécanique, assimilable à une méthode de
calcul.
Ainsi, dans les années 1930 deux mathématiciens, Alonzo Church et Alan
Turing, ont proposé quasi simultanément deux approches radicalement différentes pour caractériser ce qui peut être, ou non, calculé par un algorithme.
Mettre le résultat ici (code et figure).
Les fonctions λ-calculables de Church
![](\"https://upload.wikimedia.org/wikipedia/en/a/a6/Alonzo_Church.jpg\")
Alonzo Church
1903 - 1995
Par définition, les fonctions calculables couvrent tout ce qui peut être calculé.
Dit autrement tout calcul, petit ou grand, se ramène à l'application d'une fonction calculable à des arguments, et cela vaut encore pour chaque calcul intermédiaire d'une fonction que l'on chercherait à définir.
Ainsi, Church propose de définir une fonction calculable comme une fonction dont le résultat est obtenu par une combinaison d'applications de fonctions calculables.
Il propose pour les décrire un langage à la syntaxe minimale appelé λ-calcul (prononcer «lambda-calcul»).
Dans ce langage, on ne manipule rien d'autre que des fonctions calculables:
on définit des fonctions calculables dont les paramètres sont des fonctions calculables et dont le résultat n'est de même rien d'autre qu'une fonction calculable.
On peut rapprocher cela d'un programme Python qui ne manipulerait rien d'autre que la construction lambda:
f = lambda x: 2*x**2 + 3*x + 4
print(\"f(3)\",f(3))
Tester le code.
Comme on le voit cette description donnera quelques décennies plus tard les bases théoriques de la programmation fonctionnelle.
Autre fait moins intuitif :
bien que ce système extrême n'admette rien d'autre comme élément de base que la fonction, il permet tout à fait de représenter, indirectement et à l'aide de fonctions particulières, nos objets habituels, à commencer par les nombres entiers et certaines structures de données (voir page ci-après pour quelques exemples).
Grâce à cela, le λ-calcul permet effectivement de représenter des algorithmes traditionnels.
Mettre le résultat ici (code et figure).
Le λ-calcul
Ce langage manipule des expressions dont la structure est définie récursivement.
Une expression est soit :
- l'application d'une expression e1 à une expression e2, notée e1(e2);
- une fonction attendant un paramètre x et dont le résultat est calculé par une expression e, notée λ.x.e, à rapprocher d'une fonction anonyme Python lambda x: e;
- une référence à un paramètre x.
Voici trois exemples d'expressions du λ-calcul:
- λx.x
- λx.λy.x
- λf.λg.λx.g(f(x))
Mettre le résultat ici (code et figure).
Le λ-calcul (suite)
La première est la fonction identité, qui attend un paramètre x et le renvoie tel quel comme résultat.
La deuxième est une fonction qui attend un paramètre x et renvoie comme résultat la fonction constante attendant un paramètre y mais renvoyant simplement x.
Notez que l'on peut également la voir comme une fonction attendant deux paramètres x et y et renvoyant le premier (x).
La dernière peut être vue comme une fonction qui, si on lui passe deux paramètres f et g, renvoie la fonction composée g o f.
On «calcule» avec les expressions du λ-calcul à l'aide d'une unique règle résolvant l'application
(λx.e)(a)
d'une fonction λx.e à un argument a.
Pour cela, il suffit de remplacer, dans l'expression e donnant le résultat de la fonction, chaque occurrence du paramètre x par l'argument a.
(λf.λx.f(f(x))) (λy.y) = λx(λy.y)((λy.y)(x))
Mettre le résultat ici (code et figure).
Données
Étant données deux expressions a et b, l'expression λz.z(a)(b} est une manière de représenter le couple (a,b).
Pour obtenir l'un des éléments composant un tel couple, on peut alors appliquer à ce couple l'une des deux fonctions λc.c(λx.λy.x) où λc.c(λx.λy.y).
On peut en effet développer l'application de la première ainsi:
(λc.c(λx.λy.x))(λz.z(a)(b))
= (λz.z(a)(b))(λx.λy.x)
= (λx.λy.x)(a)(b)
= (λy.a)(b)
= a
Les deux expressions λx.λy.x et λx.λy.y aperçues dans les deux fonctions de projection précédentes sont également couramment utilisées pour représenter respectivement True et False.
Avec cette double possibilité de représenter une information binaire (True/False) et de concaténer deux éléments, nous avons le pouvoir de représenter toute séquence de bits.
Mettre le résultat ici (code et figure).
Itération
Prenons comme dernier exemple sur le λ-calcul l'expression suivante, usuellement notée θ (theta) et appelée combinateur de point fixe de Turing :
(λx.λy.y(x(x)(y)))(λx.λy.y(x(x)(y)))
l'application de cette expression θ à une expression f quelconque on obtient l'enchaînement suivant:
θ(f) = f(θ(f) = f(f(θ(f))) = ...
Autrement dit, on obtient la possibilité d'itérer une fonction. et le risque de rencontrer un jour un calcul qui ne s'arrêterait jamais.
Ce double tranchant peut rappeler les fonctions récursives ou la boucle while.
Mettre le résultat ici (code et figure).
Les machines de Turing
![](\"https://upload.wikimedia.org/wikipedia/commons/thumb/a/a1/Alan_Turing_Aged_16.jpg/440px-Alan_Turing_Aged_16.jpg\")
Alan Turing
1912 - 1964
L'approche de Turing retient quant à elle l'aspect mécanique du calcul, avec un système comportant deux composantes:
- un ruban de mémoire infini dont le contenu peut être consulté et modifié,
- et une machine se déplaçant le long de ce ruban et en modifiant le contenu en fonction de quelques règles très simples constituant le programme de cette machine.
![](\"https://sciencesappliquees.com/images/nsi/calcu2.png\")
On peut voir une telle machine de Turing comme calculant le résultat d'une fonction f :
on commence par écrire sur le ruban un paramètre e,
on démarre la machine puis, lorsqu'elle s'arrête,
on lit le ruban pour obtenir le
résultat f(e).
Une fonction calculable selon Turing est alors définie comme une fonction pour laquelle il existe une machine.
Le programme réalisé par une machine de Turing est décrit par un ensemble de règles de transition qui, en fonction de l'état actuel de la machine et de l'information lue à la position observée du ruban, donnent trois éléments:
- une instruction d'écriture, indiquant ce qui doit être écrit à la position actuelle du ruban à la place de l'imformation actuelle;
- une instruction de déplacement, indiquant s'il faut déplacer la machine le long du ruban et dans quel sens;
- l'état dans lequel passera la machine après cette étape.
On peut comprendre l'état de la machine comme une indication de notre situation dans l'exécution du programme, indication similaire à ce que serait un numéro de ligne pour un programme Python.
L'idée des machines de Turing donne ainsi les germes de la programmation impérative, avec des instructions exécutées successivement et agissant sur une mémoire.
L'information que peut contenir chaque case du ruban est définie par un ensemble fini de symboles appelé alphabet.
On prendra typiquement comme base un ensemble de trois symboles:
0, 1 et ⚈,
dans lequel 0 et 1 représentent des bits et ⚈ (prononcer «blac») indique une case vide.
Ces symboles sont parfois combinés avec des marqueurs permettant de repérer une position sur le ruban.
Ainsi, un nombre entier positif pourra être représenté en binaire sur un morceau de ruban contenant des symboles 0 et 1, délimité de chaque côté par un symbole ⚈.
Voici un fragment de ruban représentant le nombre 19, c'est-à-dire 10011 en binaire:
![](\"https://sciencesappliquees.com/images/nsi/calcu3.png\")
Une machine incrémentant un tel entier de 1, en supposant un démarrage à l'extrémité gauche du nombre, pourrait fonctionner en deux étapes :
- d'abord se déplacer jusqu'à l'extrémité droite,
- puis ajouter 1 au bit de poids faible, et revenir vers la gauche autant que nécessaire pour propager les retenues.
On pourrait donner à une telle machine trois états possibles:
- un état de départ A pour la première phase de déplacement,
- un état B pour la phase d'incrément,
- et un état final F indiquant que le calcul est terminé.
Dans l'état A, la machine se déplace vers la droite sans modifier le contenu du ruban ni changer d'état tant qu'elle y observe des bits.
Lorsque la machine vient de dépasser le dernier bit, c'est-à-dire lorsqu'elle observe ⚈, elle revient alors d'une case en arrière et passe à l'état B.
![](\"https://sciencesappliquees.com/images/nsi/calcu4.png\")
![](\"https://sciencesappliquees.com/images/nsi/calcu5.png\")
![](\"https://sciencesappliquees.com/images/nsi/calcu6.png\")
![](\"https://sciencesappliquees.com/images/nsi/calcu7.png\")
Dans cet état, tant que la machine bserve des 1 elle les remplace par des 0 et poursuit son retour vers la gauche.
![](\"https://sciencesappliquees.com/images/nsi/calcu8.png\")
![](\"https://sciencesappliquees.com/images/nsi/calcu9.png\")
Ce retour s'arrête dès que la machine lit un 0 ou un ⚈, auquel cas ce symbole est remplacé par un 1 et la machine passe à son état final F et s'arrête.
![](\"https://sciencesappliquees.com/images/nsi/calcu10.png\")
L'ensemble de ces règles de transitions est résumé dans la table suivante:
![](\"https://sciencesappliquees.com/images/nsi/calcu11.png\")
Dans cette version, on suppose qu'il y a suffisamment de symboles blancs ⚈ à gauche du nombre pour qu'il en reste bien toujours un, même après la propagation d'une retenue.
Les trois états de la machine et leurs successions possibles au cours d'un calcul peuvent être résumés dans le graphe orienté suivant, appelé automate.
![](\"https://sciencesappliquees.com/images/nsi/calcu12.png\")
Dans ce graphe, chaque sommet correspond à un état et chaque arc à une transition possible.
On a étiqueté chaque arc par les symboles dont la lecture peut déclencher la transition correspondante, et on pourrait compléter pour préciser chaque action de déplacement et d'écriture associée.
Mettre le résultat ici (code et figure).
Machine de Turing universelle
L'un des coups de force de Turing, qui a montré que ses machines sont capables de réaliser des algorithmes complexes, est la définition d'une machine universelle.
Cette machine prend en entrée une autre machine de Turing M et une entrée e pour la machine M, et simule l'exécution de la machine M sur l'entrée e.
On peut faire un parallèle entre cette machine et nn interprète Python qu'on aurait écrit dans le langage Python lui-même.
Mettre le résultat ici (code et figure).
Universalité de la calculabilité
Dès 1936, Turing établit que les fonctions pouvant être définies comme
des fonctions λ-calculables de Church et les fonctions pouvant être calculées par des machines de Turing sont exactement les mêmes.
Autrement dit, les deux approches, si différentes soient-elles, décrivent la même notion de fonction calculable.
Cette convergence entre les résultats obtenus par deux approches si radicalement différentes à vite étayé l'idée, baptisée thèse de Church-Turing, que l'on venait effectivement de réussir à capturer la vraie notion de fonction calculable.
De ce point de vue, la compétition qu'on
aurait pu attendre entre ces deux approches n'eut donc jamais lieu.
Depuis, cette notion commune sert donc d'étalon et l'on qualifie de Turing-complets les modèles d'algorithmes et les langages de programmation permettant de calculer les mêmes choses que les machines de Turing.
Et de fait, la thèse de Church-Turing n'a jamais été démentie depuis.
Les autres manières de caractériser ce qui est calculable par algorithme développées par la suite ont encore été démontrées équivalentes à ces deux premières, c'est-à-dire Turing-complètes.
Tous les langages de programmation ordinaires, quels que soient les paradigmes qu'ils empruntent, sont de
même Turing-complets.
Certains langages permettent de résoudre plus naturellement que d'autres certains problèmes, mais il n'existe aucune tâche
qui puisse être réalisée par un programme écrit dans un langage de programmation donné qui ne soit pas réalisable dans tous les autres.
Mettre le résultat ici (code et figure).
Autrement dit, tout problème de calcul dont on peut démontrer qu'il ne peut pas être résolu par une machine de Turing, par une fonction de Church ou par un programme Python, est officiellement hors de portée de l'algorithmique et de la programmation.
En particulier l'impossibilité de détecter à coup sûr à l'aide d'un programme Python les programmes effectuant une division par zéro, que nous avons montrée au début de cette séquence, à bien une portée universelle et n'est pas liée à une limitation du langage.
Pour cette section, nous prendrons donc le langage Python comme référence pour raisonner sur la calculabilité et ses limites :
par algorithme nous entendrons fonction Python, à distinguer de la notion de fonction mathématique qui n'est pas nécessairement calculable.
Mettre le résultat ici (code et figure).
Les premiers résultats d'incalculabilité
Turing et Church ont chacun, en même temps qu'ils introduisaient leur modèle de calcul, explicité un problème dont ils ont montré que la solution n'était pas calculable.
Church a démontré qu'il ne pouvait exister de fonction calculable prenant en paramètres deux fonctions f et g et déterminant leur égalité, c'est-à-dire
répondant vrai si pour tout paramètre e, f(e) = g(e), et faux sinon.
Turing à démontré qu'il ne pouvait exister de machine de Turing prenant en paramètres une machine M et une entrée e, et déterminant si l'exécution de la machine M sur l'entrée e termine un jour ou au contraire se poursuit indéfiniment.
Ce deuxième problème, appelé problème de l'arrêt, est encore aujourd'hui un point de référence majeur que nous allons détailler ci-dessous.
L'un et l'autre en ont déduit, chacun dans son système, que l'Entscheidungsproblem ne pouvait être résolu par un algorithme.
Mettre le résultat ici (code et figure).
Problèmes de décision
On s'intéresse souvent à la calculabilité de fonctions particulières, dont le résultat est oui où non.
On parle dans ce cas d'un problème de décision.
Le problème de l'arrêt, le problème de l'égalité de deux fonctions, ou encore le problème de la détection d'erreur en Python sont des problèmes de décision.
Le problème de la résolution d'une équation du second degré n'en est pas.
On appelle décidable un problème de décision dont la solution est calculable, et indécidable un problème de décision dont la solution n'est pas calculable.
Parmi les problèmes indécidables, on nomme semi-décidables ceux pour lesquels on possède un algorithme qui répond à coup sûr lorsque la réponse attendue est oui, mais qui est susceptible de ne jamais s'arrêter lorsque la réponde attendue est non.
Notre détecteur naïf pour la division par zéro avait justement cette propriété, et montre donc que notre problème de détection d'erreur est semi-décidable.
Mettre le résultat ici (code et figure).
Problème de l'arrêt
Dans le problème de l'arrêt, reformulé pour les algorithmes assimilés à des fonctions Python, on s'intéresse à la fonction mathématique qui prend en paramètre une fonction Python f et une entrée e pour cette fonction Python, et qui renvoie le résultat True si l'exécution de f sur l'entrée e finit par s'arrêter, et False si au contraire elle ne s'arrête jamais.
On démontre qu'il n'existe pas d'algorithme calculant cette fonction mathématique, par un raisonnement par l'absurde similaire à celui tenu à propos du détecteur parfait.
Supposons donc qu'il existe un algorithme
arret prenant deux paramètres f et e et renvoyant en un temps fini soit True soit False selon que l'exécution de f sur e s'arrête ou non.
On définit grâce à arret un nouvel algorithme qu'on appelle paradoxe, qui attend un entier n et agit comme suit.
def paradoxe (n) :
if arret(paradoxe , n):
while True:
pass
else:
return n
Est-ce que l'application paradoxe(0) de cet algorithme au paramètre 0 produit un résultat, et si oui lequel?
Supposons que paradoxe(0) renvoie un résultat r. Cela signifie que cette exécution s'arrête et donc que arret(paradoxe, 0) va renvoyer True.
Autrement dit, l'algorithme paradoxe va déclencher la boucle infinie et ne jamais s'arrêter, ce qui est une contradiction.
Supposons à l'inverse que paradoxe(0) ne renvoie pas de résultat, car ne s'arrête jamais. Alors arret(paradoxe, 0) va répondre False et l'algorithme paradoxe renverra ainsi 0, ce qui est à nouveau une contradiction.
L'algorithme paradoxe ne peut donc pas exister.
Notez que le paramètre n attendu par paradoxe n'a pas de rôle particulier dans la preuve :
il a seulement été ajouté car on a énoncé le problème de l'arrêt pour des couples algorithme/entrée.
On aurait également pu énoncer le problème de l'arrêt pour des algorithmes sans paramètre et obtenir le même résultat.
Mettre le résultat ici (code et figure).
À propos des fonctions passées en paramètre
En général, passer une fonction f en paramètre à une fonction g comme on le fait facilement en programmation fonctionnelle permet à g d'appeler f, maïs pas nécessairement d'étudier le code de f.
On pourrait alors arguer que, dans notre
étude de la calculabilité, passer la fonction en paramètre plutôt que le code source lui-même n'est pas suffisant.
En Python, cependant, où tout est toujours un peu plus mélangé que dans là plupart des autres langages, il est possible d'obtenir le bytecode d'une fonction passée en paramètre grâce aux fonctions du module dis, et la différence entre les deux versions n'importe donc pas.
Mettre le résultat ici (code et figure).
Indécidabilité : cas général, cas particuliers.
La notion d'indécidabilité algorithmique concerne une fonction à laquelle on demande de répondre à coup sûr, sur toutes les entrées possibles.
Le fait que le problème général soit indécidable n'empêche pas que lon sache y répondre dans certains cas particuliers.
Ainsi, bien que le problème de l'arrêt soit indécidable, il reste tout à fait envisageable, un algorithme étant donné, de démontrer que cet algorithme particulier s'arrête sur une entrée particulière, ou même sur toute entrée.
La notion de variant de boucle vue en première permet justement de produire une telle démonstration dans certains cas.
Mettre le résultat ici (code et figure).
Autres problèmes indécidables et réductions
La connaissance d'un problème indécidable permet de justifier plus simplement l'indécidabilité de nombreux autres problèmes, à l'aide de techniques dites de réduction.
Considérons par exemple le problème de l'équivalence de deux algorithmes.
Étant donnés deux algorithmes f et g, on souhaite savoir si, pour toute entrée e, les appels f(e) et g(e) ont le même comportement, c'est-à-dire soit les deux produisent le même résultat, soit les deux s'interrompent avec la même exception, soit aucun ne termine.
Le problème de l'équivalence de deux algorithmes est indécidable.
Pour le justifier, supposons qu'il existe une fonction Python équivalentes prenant en paramètres deux fonctions f1 et f2 et renvoyant True si f1 et f2 sont équivalentes et False sinon.
Montrons que cette hypothétique fonction pourrait être détournée pour résoudre le problème de l'arrêt.
Définissons une fonction arret prenant en paramètres une fonction f et une entrée e pour f, qui va déterminer si f s'arrête sur e.
def arret(f, e):
On construit à partir de f une nouvelle fonction f1 qui, quelle que soit l'entrée, exécute f(e) et ne s'arrête donc que si f(e) s'arrête également.
def f1(x):
return f(e)
Notez qu'il s'agit d'une définition de fonction locale, placée à l'intérieur de la définition de arret.
Une telle fonction peut faire référence aux éléments locaux de la fonction englobante, ici en l'occurrence aux paramètres de arret.
Elle n'est en contrepartie pas directement accessible depuis l'extérieur.
On définit de même une fonction f2 qui ne s'arrête sur aucune entrée.
def f2(x):
while True:
pass
Ainsi, la fonction f1 est équivalente à la fonction f2 si et seulement si elle
ne s'arrête pour aucune entrée, c'est-à-dire si f(e) ne s'arrête pas.
Il suffit de nier le résultat de equivalentes(f1, f2) pour obtenir la réponse au problème de l'arrêt de f sur e.
return not equivalentes(f1, f2)
Nous aurions donc pu, à l'aide de la fonction equivalentes, définir une fonction décidant l'indécidable problème de l'arrêt.
Cette fonction equivalentes ne peut donc exister, et le problème de l'équivalence de deux algorithmes n'est donc pas décidable.
Mettre le résultat ici (code et figure).
Pas d'indécidabilité sans infini
Aucun problème n'est indécidable lorsque l'on à la possibilité d'en explorer toutes les configurations en un temps fini, puisqu'il suffit alors de mener cette exploration exhaustive avant de renvoyer True où False.
Le problème de l'arrêt est indécidable
car le ruban de mémoire d'une machine de Turing est infini et qu'on ne peut donc pas borner à priori le nombre de configurations différentes de ce ruban rencontrées dans une exécution.
Ainsi, à strictement parler, l'arrêt d'un programme Python sur un ordinateur donné est décidable, du fait de la finitude de la mémoire de cet ordinateur.
Le nombre de configurations possibles (deux puissance le nombre de bits de la mémoire) est cependant tel que cette décidabilité n'est que théorique.
Mettre le résultat ici (code et figure).
Indécidabilité mathématique / indécidabilité algorithmique.
La notion d'indécidabilité que nous décrivons ici, liée à Palgorithmique, est
absolument différente de celle existant en mathématiques.
En mathématique, on qualifie d'indécidable un énoncé dont on a pu
justifier qu'il ne pouvait ni être démontré ni être réfuté, un ensemble
d'axiomes étant donné. La notion concerne donc une formule qui n'est ni vraie ni fausse, et on parle également dans ce cas d'indépendance.
En algorithmique en revanche, nous avons vu que l'indécidabilité est une propriété d'un problème de décision, désignant l'impossibilité d'établir un algorithme répondant à coup sûr à une question donnée, pour toutes les entrées possibles.
On pourrait parler ici d'incalculabilité.
Le lien entre ces deux notions n'est pas conceptuel, mais historique :
l'indécidabilité mathématique est apparue avec les travaux de Kurt Güdel
en 1930, dont certaines techniques ont été réutilisées dans les travaux de Church et Turing sur l'indécidabilité algorithmique (en particulier une manière d'établir des correspondances entre des objets complexes et les nombres entiers, appelées codages de Güdel).
On prétend pourtant parfois que les concepts sont également liés, car le point de départ de l'indécidabilité algorithmique est l'Entscheidungsproblem, c'est-à-dire un problème de décision lié à la logique, mais il s'agit d'une contingence apportant plus de confusion qu'autre chose :
l'indécidabilité mathématique est une propriété d'une seule formule, alors que l'indécidabilité algorithmique de l'Entscheidungsproblem est une propriété d'un problème de décision relatif à l'ensemble des formules.
Mettre le résultat ici (code et figure).
Indécidabilité des propriétés des programmes.
Avec les problèmes de détection des divisions par zéro, de l'arrêt, et de l'équivalence de deux algorithmes, nous avons déjà pu énoncer plusieurs propriétés des programmes qui étaient indécidables.
Il se trouve que, de manière générale, toute propriété non triviale à propos des programmes est de même indécidable.
La forme précise (et démontrée!) de cette allégation est appelée théorème de Rice.
Mettre le résultat ici (code et figure).
Problème de correspondance de Post : un problème indécidable qui ne parle pas de programmes
Voici un petit puzzle:
on dispose d'un ensemble de dominos affichant de chaque côté une suite de symboles
![](\"https://sciencesappliquees.com/images/nsi/calcu14.png\")
et d'un domino de départ, par exemple celui de gauche.
On cherche à disposer des dominos côte à côte à la suite de notre domino de départ, de sorte à pouvoir lire la même suite de symboles en haut et en bas.
On se donne le droit d'utiliser chaque domino autant de fois que nécessaire.
On a par exemple ici la solution suivante dans laquelle les deux lignes jouent (pas exactement ensemble) la même mélodie «la re sol sol sol do re sol sol».
Notez que l'un des dominos à servi deux fois.
![](\"https://sciencesappliquees.com/images/nsi/calcu15.png\")
Si en revanche on n'avait eu à notre disposition que les dominos de gauche et de droite, ce puzzle n'aurait pas eu de solution.
Considérons maintenant le problème de décision suivant :
étant donnés un ensemble de dominos et un domino de départ, le puzzle correspondant a-t-il une solution?
Ce problème de décision est l'une des variantes du problème de correspondance de Post, du nom d'Emil Post son créateur.
Il s'agit d'un problème indécidable.
L'une des clés de l'indécidabilité de ce problème est que, lors de la construction d'une solution, le décalage entre la ligne du haut et la ligne du bas peut devenir arbitrairement grand.
On ne sait alors pas à coup sûr si les deux lignes finiront par se rattraper, terminant la construction.
La prouve d'indécidabilité du problème de Post, hors de portée du programme de lycée, montre que les dominos de Post et les suites de symboles qu'ils forment peuvent être utilisés pour simuler l'exécution de toute machine de Turing.
Mettre le résultat ici (code et figure).
Un problème de décision est une question s'appliquant aux éléments d'un ensemble et à laquelle Ia réponse est, pour chaque
élément, soit oui soit non.
Un tel problème est dit décidable lorsqu'il existe un algorithme qui, pour chaque élément, calcule à coup sûr et en temps fini la réponse correspondante.
Il existe des problèmes qui ne sont pas décidables, à commencer par le problème de l'arrêt, qui s'applique à l'ensemble des algorithmes et demande de répondre à la question «l'exécution de cet algorithme s'arrête-t-elle ?».
La notion de décidabilité est indépendante du langage de programmation.
Mettre le résultat ici (code et figure).
Montrer qu'il n'existe pas de fonction Python prenant en entrée une fonction Python f, sans paramètre, et renvoyant True si et seulement si l'exécution f() de f s'arrête.
Mettre le résultat ici (code et figure).
En supposant qu’une telle fonction arret existe, on peut écrire la fonction paradoxale suivante.
def paradoxe ():
if arret (paradoxe):
while True:
pass
else:
return None
Simulation de la machine de Turing
On se propose d'écrire un programme simulant l'exécution d'une machine de Turing.
Fixons tout d'abord certains choix de représentation.
- Un état de la machine est identifié par une chaîne de caractères.
- Le symbole écrit dans une case du ruban est représenté par une chaîne de caractères.
- L'ensemble des règles de transition de la machine est matérialisé par un dictionnaire dont les clés sont les états. Consulter ce dictionnaire pour un état donné fournit l'ensemble des règles applicables à partir de cet état, à nouveau sous la forme d'un dictionnaire, dont les clés sont les symboles manipulés par la machine et les valeurs sont les actions associées.
- Les actions à effectuer à la lecture d'un symbole donné dans un état donné sont représentées par un triplet (e,d,s) où :
- e est le symbole à écrire (une chaîne de caractères);
- d est le déplacement éventuel:
- —1 pour aller à gauche,
0 pour ne pas bouger,
1 pour aller à droite; - s est l'état suivant (une chaîne de caractères).
Une machine de Turing est donnée par un état de départ, un état final et un dictionnaire de règles de transition.
Lors de l'exécution de la machine, on fait évoluer une configuration formée d'un ruban mémoire, d'une identification de la position et de l'état courant de la machine.
Pour représenter le ruban, on utilise un tableau bidirectionnel tel que décrit dans la séquence 8 ( programmation objet).
class TaBiDir:
def __init__(self, g, d):
self.gauche = g[::-1]
self.droite = d[:]
def imin(self):
return - len(self.gauche)
def imax(self):
return len(self.droite) - 1
def append(self, v):
self.droite.append(v)
def prepend(self, v):
self.gauche.append(v)
def __getitem__(self, i):
if i >= 0:
return self.droite[i]
else:
return self.gauche[-i-1]
def __setitem__(self, i, v):
if i >= 0:
self.droite[i] = v
else:
self.gauche[-i-1] = v
Ce tableau ne pouvant pas être infini il ne contiendra que les cases effectivement utilisées, toutes les positions au-delà de ce qui est représenté dans le tableau étant réputées contenir le symbole ⚈.
Pour cela, le ruban est initialisé au début de l'exécution avec l'ensemble des cases représentant l'entrée, puis il est étendu à gauche ou à droite à chaque fois que la machine se déplace en dehors des
limites courantes.
Écrire une fonction prenant en paramètres la description d'une machine de ‘Turing M et une entrée e pour cette machine, et simulant l'exécution de la machine M sur l'entrée e.
Il est possible d'utiliser une ou plusieurs classes pour structurer les données manipulées et le code.
Tester ce simulateur avec la machine d'incrément de 1 donnée en exemple dans cette séquence.
regles_incr = {
'A': {'0' : ('0', 1, 'A'),
'1' : ('1', 1, 'A'),
None: (None, -1, 'B')},
'B': {'0' : ('1', 0, 'F'),
'1' : ('0', -1,'B'),
None: ('1', 0, 'F')}
}
machine_incr = MachineDeTuring('A','F',regles_incr)
calcule(machine_incr, ['1','0','0','1','1'])
calcule(machine_incr, ['1','1','1'])
calcule(machine_incr, [None])
Mettre le résultat ici (code et figure).
On propose de définir une première classe pour regrouper les différents éléments définissant une machine de Turing
class MachineDeTuring:
\"\"\"description d’une machine de Turing\"\"\"
def __init__(self, etat_initial, etat_final, regles):
self.etat_initial = etat_initial
self.etat_final = etat_final
self.regles = regles
et une seconde pour représenter une configuration de l’exécution.
class Configuration:
\"\"\"configuration d’une machine de Turing,
ruban bi-infini\"\"\"
def __init__(self, etat, entree):
self.etat = etat
self.pos = 0
self.ruban = TaBiDir([], entree)
Par convention, on placera l'entrée à partir de l'indice 0, qui est aussi l’indice de départ de la machine.
On inclut dans la classe Configuration une méthode pour l'affichage, qui donne le tableau des cases utilisées en ajoutant entre parenthèses l’état de la machine à côté du symbole de la case où se trouve la machine.
Les méthodes lit et evolue permettent respectivement d'obtenir le symbole lu par la machine et de faire évoluer la configuration en fonction du triplet indiqué par une règle de transition.
Notez que nous utilisons ici None pour représenter le symbole ⚈.
def __str__(self):
return str([str(self.ruban[i]) + '(' + self.etat + ')'
if i == self.pos
else str(self.ruban[i])
for i in range( self.ruban.imin(),
self.ruban.imax()+1)])
def lit(self):
return self.ruban[self.pos]
def evolue(self, e, d, s):
self.ruban[self.pos] = e
self.pos += d
if self.pos < self.ruban.imin():
self.ruban.prepend(None)
if self.pos > self.ruban.imax():
self.ruban.append(None)
self.etat = s
La fonction principale crée une configuration avec l'entrée fournie et l’état initial de la machine, puis applique les règles de transition jusqu’à atteindre l’état final de la machine.
def calcule(machine, entree):
config = Configuration(machine.etat_initial, entree)
print(config)
while config.etat != machine.etat_final:
e, d, s = machine.regles[config.etat][config.lit()]
config.evolue(e, d, s)
print(config)
print ('Calcul terminé')
Pour tester ce simulateur il faut d’abord construire une instance de
MachineDeTuring avec le bon dictionnaire de règles.
regles_incr = {
'A': {'0' : ('0', 1, 'A'),
'1' : ('1', 1, 'A'),
None: (None, -1, 'B')},
'B': {'0' : ('1', 0, 'F'),
'1' : ('0', -1,'B'),
None: ('1', 0, 'F')}
}
machine_incr = MachineDeTuring('A','F',regles_incr)
Ne reste plus qu’à observer le travail de la machine sur différentes entrées.
Notez que dans le code que nous avons donné, on suppose que la case d'indice 0 du ruban existe.
Si on veut donner l’entrée vide, il faut donc explicitement placer le symbole ⚈ (c’est-à-dire None) dans cette case.
calcule(machine_incr, ['1','0','0','1','1'])
calcule(machine_incr, ['1','1','1'])
calcule(machine_incr, [None])
Voici un ensemble de règles de transition pour une machine de Turing.
Son état initial est P et son état final F.
![](\"https://sciencesappliquees.com/images/nsi/calcu13.png\")
Avec quel alphabet travaille cette machine?
Quels sont les états de la machine?
L'exécuter sur l'entrée ['1', '0', '0', '1'],
puis sur l'entrée ['1', '1', '1', '0'],
en considérant à chaque fois qu'en dehors de cette entrée, la ruban est intégralement rempli avec le symbole blanc ⚈.
Comment se comporte-t-elle dans chacun des états?
Que fait cette machine?
Il ne faut pas hésiter à tester la machine sur d'autres entrées, y compris en utilisant le simulateur de l'exercice précédent.
Mettre le résultat ici (code et figure).
La machine travaille sur l'alphabet {0,1,⚈}, et ses états sont P, D0, D1, V0, Vi, R, E et F.
Les deux exécutions peuvent être
résumées ainsi en indiquant l’état de la machine dans la case correspondant à sa position.
![](\"https://sciencesappliquees.com/images/nsi/calcu16.png\")
![](\"https://sciencesappliquees.com/images/nsi/calcu17.png\")
Dans l’état P, la machine efface une case et retient son contenu.
Dans les états D0 et D1 elle se déplace jusqu’au bout de l’entrée.
Dans les états V0 et V1 elle vérifie que le contenu de la case correspond à la valeur mémorisée (et efface la case).
Dans l’état R elle revient au début de l’entrée pour reprendre à P.
Dans l’état E elle efface le ruban puis s'arrête.
Cette machine vérifie si l’entrée est un palindrome.
À la fin de l’exécution elle a vidé le ruban et simplement laissé écrit un 1 si l'entrée était un palindrome, et un 0 sinon.
Le retour à l’état P peut être vu comme un appel récursif à notre algorithme de vérification de palindrome, sur une entrée dont le premier et le dernier symbole ont été effacés.
Question subsidiaire : comment est gérée la reconnaissance des palindromes de longueur impaire?
Réponse : le plus simple pour cela est de
regarder le comportement de la machine sur une entrée composée d’un seul symbole.
On y voit notamment l’action des règles (C0,⚈) et (C1, ⚈).
Définir une machine de Turing qui décale son entrée d'une case vers la droite.
On supposera que l'entrée est composée des symboles 0 et 1 et bordée de symboles blancs ⚈.
On supposera également que la position
de départ de la machine est à l'extrémité gauche de l'entrée.
Mettre le résultat ici (code et figure).
Exercice 136, page 282
On se donne un état initial Z, dans lequel la machine va écrire un symbole blanc à la place du premier symbole de l’entrée, puis deux états D0 et D1 indiquant qu'on est en train de décaler respectivement un 0 ou un 1.
La machine se déplace uniquement vers la droite et mémorise donc avec l’état D0 ou D1 le symbole lu sur la case précédente pour l’écrire à la case suivante.
La machine s’arrête (état final F) lorsqu'elle rencontre le symbole blanc suivant l'entrée.
![](\"https://sciencesappliquees.com/images/nsi/calcu18.png\")
Définir une machine de Turing qui, partant de l'extrémité gauche de son entrée, parcourt cette entrée à la recherche du symbole 0.
Si le symbole est trouvé elle devra écrire 1 dans la case précédent l'entrée, et sinon elle devra y écrire 0.
On supposera que l'entrée est composée de
symboles 0 et 1 et bordée de symboles blancs ⚈.
Mettre le résultat ici (code et figure).
On utilise trois états C, P et À en plus de l’état final F.
Dans l’état C (qui est l’état initial), la machine cherche une occurrence de 0.
Dans les états P et A, la machine revient à écrire son verdict.
La machine passe dans l’état P (présent) dès qu’elle observe un symbole 0.
Elle passe dans l’état A si elle atteint le blanc suivant l’entrée sans avoir rencontré de 0.
![](\"https://sciencesappliquees.com/images/nsi/calcu19.png\")
Notez que nous n’avons pas inclus de règles pour (P,0) et (A,0) car ces
situations ne doivent jamais se produire: la machine faisant demi-tour au premier 0 rencontré elle ne trouvera jamais un 0 sur son chemin retour.
La stratégie de cette machine peut faire penser au code de la fonction Python suivante.
def chercher_zero(entree):
for x in entree:
if x == 0:
return True
return False
Modifier la machine de l'exercice précédent pour détecter non pas les occurrences de 0 mais, les occurrences de plus de deux symboles 0 consécutifs.
Mettre le résultat ici (code et figure).
On remplace l’unique état C' par trois états C, D1 et D2 signifiant respectivement «on cherche», «on vient de voir une occurrence de 0 » et « on vient de voir deux occurrences de 0 ».
Lors d’une séquence de plusieurs 0 consécutifs on progresse de C à D1 à D2 puis à P, mais dès que la séquence est coupée par un 1 on revient à C.
![](\"https://sciencesappliquees.com/images/nsi/calcu20.png\")
Supposons un ruban de machine de Turing dont une case contient le symbole 0, et tout le reste le symbole blanc ⚈.
Supposons que la machine se trouve à une certaine position du ruban, dont on ne sait pas si elle est à gauche ou à droite du symbole 0.
Donner un ensemble de règles permettant, à coup sûr, d'arriver en temps fini à la position contenant un 0.
On pourra utiliser un symbole au choix, par exemple l'astérisque *, pour laisser une marque sur une case.
Un objectif facultatif consiste à nettoyer le ruban de toutes les marques * utilisées avant de s'arrêter.
Mettre le résultat ici (code et figure).
Il n’est pas envisageable de partir directement à gauche ou à droite jusqu’à rencontrer le 0, car on pourrait alors ne jamais s'arrêter si l’on choisissait la mauvaise direction.
On peut à la place aller alternativement vers la gauche ou la droite, à chaque fois d’une case plus loin que la précédente, en laissant des marques * dans les cases déjà explorées.
On utilise pour cela deux états D (exploration vers la droite) et G (exploration vers la gauche) en plus de l’état final F.
On peut choisir l'état initial arbitrairement entre G et D.
![](\"https://sciencesappliquees.com/images/nsi/calcu21.png\")
Pour nettoyer les marques il faut en plus, une fois le 0 trouvé, repartir en sens arrière jusqu’à un blanc, puis revenir.
Cela demande au total quatre états supplémentaires (aller et retour, avec le 0 trouvé à gauche ou à droite de la position de départ).