Résumé de Cours : Calculabilité et Décidabilité
La calculabilité et la décidabilité sont des concepts fondamentaux en informatique théorique qui examinent les limites de ce qui peut être résolu algorithmiquement. Ce cours explore ces notions clés en utilisant le langage de programmation Python comme outil illustratif.
1. Introduction à la calculabilité
La calculabilité se concentre sur la question de savoir si un problème particulier peut être résolu par un algorithme. Le théorème de l'arrêt, formulé par Alan Turing, énonce qu'il est impossible de créer un algorithme général capable de déterminer si n'importe quel autre algorithme s'arrêtera ou non.
1.1 Machine de Turing
La machine de Turing est un modèle abstrait d'un ordinateur qui consiste en une bande infinie divisée en cellules, une tête de lecture/écriture, et un ensemble d'états et de règles de transition. Elle peut être utilisée pour décrire formellement la notion d'algorithme.
La définition formelle d'une machine de Turing peut être exprimée comme :
M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)
Où :
- \(Q\) : Ensemble fini d'états.
- \(Σ\) : Alphabet d'entrée fini.
- \(Γ\) : Alphabet de ruban fini.
- \(δ\) : Fonction de transition.
- \(q₀\) : État initial.
- \(q_{accept}\) : État d'acceptation.
- \(q_{reject}\) : État de rejet.
La fonction de transition \(δ\) spécifie comment la machine évolue d'un état à l'autre en fonction de la lecture de symboles sur la bande. Cet ensemble d'éléments forme la base mathématique permettant de comprendre la calculabilité.
1.2 Théorème de l'arrêt
Le théorème de l'arrêt d'Alan Turing énonce qu'il est impossible de créer un programme général qui, étant donné un autre programme en entrée, peut déterminer si ce dernier s'arrêtera ou continuera indéfiniment. Cela souligne une limitation fondamentale de ce qui peut être calculé.
def arret(programme, entree):
try:
resultat = executer(programme, entree)
return "S'arrête"
except Exception:
return "Ne s'arrête pas"
La fonction Python ci-dessus est une simplification du problème de l'arrêt, illustrant qu'il est impossible de créer une fonction générale qui décide si n'importe quel programme s'arrêtera ou non. L'introduction à la calculabilité explore ces concepts fondamentaux, fournissant une base théorique pour comprendre les limites de ce qui peut être accompli par des algorithmes.
2. Problèmes indécidables
Les problèmes indécidables sont des problèmes pour lesquels il n'existe pas d'algorithme général permettant de déterminer une réponse correcte pour toutes les instances du problème. Alan Turing a démontré l'existence de problèmes indécidables en formulant des énoncés qui mettent en lumière les limites fondamentales de ce qui peut être calculé. L'un des exemples les plus célèbres est le Problème de l'Arrêt.
2.1 Problème de l'arrêt
Le Problème de l'Arrêt pose la question suivante : étant donné une description d'un programme informatique \(P\) et une entrée \(I\), peut-on déterminer si \(P\) s'arrêtera ou continuera indéfiniment lorsqu'il est exécuté avec \(I\) ? Formellement, le problème peut être exprimé comme :
\[ \text{Halt}(P, I) = \begin{cases} \text{"S'arrête"} & \text{si } P \text{ s'arrête sur } I \\ \text{"Ne s'arrête pas"} & \text{si } P \text{ ne s'arrête pas sur } I \end{cases} \]
Le théorème de l'arrêt prouve l'indécidabilité de ce problème, montrant qu'il n'existe pas d'algorithme général capable de résoudre le Problème de l'Arrêt pour tous les programmes \(P\) et toutes les entrées \(I\).
def arret(programme, entree):
# Impossible à implémenter de manière générale
# en raison du théorème de l'arrêt
pass
Le code ci-dessus représente une tentative simplifiée du problème de l'arrêt, mais il ne peut pas être implémenté de manière générale.
2.2 Problème de l'équivalence de programme
Un autre exemple de problème indécidable est le Problème de l'Équivalence de Programme. Ce problème pose la question suivante : étant donné deux programmes \(P_1\) et \(P_2\), déterminer s'ils sont équivalents, c'est-à-dire s'ils produisent la même sortie pour toutes les entrées possibles.
Formellement :
\[ \text{Équivalent}(P_1, P_2) = \begin{cases} \text{"Équivalents"} & \text{si } P_1 \text{ et } P_2 \text{ sont équivalents} \\ \text{"Non équivalents"} & \text{sinon} \end{cases} \]
Le Problème de l'Équivalence de Programme est également indécidable, démontrant ainsi une autre facette des limites de la calculabilité en informatique.
3. Décidabilité
La décidabilité est un concept opposé à l'indécidabilité. Un problème est décidable s'il existe un algorithme qui, pour chaque instance du problème, produit une réponse correcte en un temps fini. En d'autres termes, il est possible de construire un algorithme qui résout le problème de manière systématique.
3.1 Problème de la parité
Un exemple classique de problème décidable est le Problème de la Parité. Ce problème consiste à déterminer si un entier donné est pair ou impair. Voici une implémentation en Python :
def parite(n):
if n % 2 == 0:
return "Pair"
else:
return "Impair"
Cette fonction retourne "Pair" si l'entier \(n\) est pair, et "Impair" sinon. Le Problème de la parité est décidable car il existe un algorithme (cette fonction) capable de déterminer la parité d'un entier en un temps fini.
3.2 Problème de l'appartenance au Langage
Un autre exemple de problème décidable est le Problème de l'appartenance au Langage. Soit un langage formel défini par une grammaire, ce problème consiste à déterminer si une chaîne de caractères donnée appartient à ce langage. Un algorithme peut être construit en utilisant les règles de la grammaire pour résoudre ce problème.
La décidabilité offre une perspective optimiste en informatique théorique, montrant que pour certains problèmes, il est possible de concevoir des algorithmes systématiques garantissant des réponses correctes en un temps fini.
Éducation
