Lycée > Terminale > NSI > Introduire les notions de calculabilité et de décidabilité

Introduire les notions de calculabilité et de décidabilité

Fiche de cours
Quiz
Profs en ligne
Videos
Application mobile

Objectifs

Comprendre que tous les problèmes ne sont pas résolubles par un algorithme ou par un programme informatique.
Comprendre que le fait de connaitre la décidabilité ou l'indécidabilité d’un problème est important.
Comprendre que la calculabilité ne dépend pas du langage de programmation utilisé.

Points clés

Tout problème n’a pas forcément une méthode systématique de résolution. On parle de problème indécidable.
A contrario, les problèmes qui ont au moins une méthode systématique de résolution sont dits décidables.
Le problème de l’arrêt est indécidable : il n’existe pas de méthode systématique pour démontrer qu’un programme s’arrête ou non.
Les notions de calculabilité et de décidabilité sont équivalentes.

Pour bien comprendre

Savoir écrire et utiliser un algorithme.
Établir un raisonnement par l’absurde.

1. La décidabilité

a. Notion de problème

Bien avant l’existence des ordinateurs, les mathématiciens et les logiciens se sont intéressés aux méthodes de résolution des problèmes. LA question était la suivante : « Chaque problème a-t-il une méthode de résolution ? Tout problème peut-il être résolu par une méthode systématique, par un algorithme ? ».

La réponse est NON.

Ici, la notion de problème est à préciser.

Un problème est caractérisé par les trois propriétés suivantes.

Le problème est une question générique qui s’applique à un ensemble d’éléments.
Exemple
« Déterminer si un nombre entier positif est pair ou impair » est un problème qui s’applique sur l’ensemble des entiers positifs.
Chaque instance du problème a une réponse.
Exemple
Si on considère le problème précédent, chaque entier positif a une réponse : on peut dire s’il est pair ou impair.
Le problème n’est pas défini par un algorithme ou par un programme.
Exemple
Le problème précédent ne dépend pas directement d’un algorithme, mais de la définition de ce qu’est un nombre pair.

b. Décidabilité, indécidabilité

Un problème est décidable si on peut le résoudre avec une méthode systématique, c’est-à-dire si chacune de ses instances sont résolubles par le même algorithme.

Exemple
Le problème « Déterminer si un nombre entier positif est pair ou impair » est décidable car, si on considère un nombre entier positif quelconque, il suffit d’observer son chiffre des unités pour déterminer s’il est pair ou impair. Si ce chiffre est égal à 0, 2, 4, 6 ou 8, le nombre est pair, il est impair sinon.

Il existe des problèmes indécidables. Cela ne signifie pas simplement que nous ne savons pas les résoudre, mais qu’il n’existe aucune méthode systématique pour les résoudre.

Généralement, les démonstrations de décidabilité ou d’indécidabilité sont complexes à établir et sont hors programme.

Exemple
Un problème célèbre est celui du pavage du plan par des polygones. Paver le plan avec des polygones signifie recouvrir le plan avec ces polygones sans qu’ils ne se chevauchent et sans qu’il y ait d’espace entre eux.

Le problème se pose de la manière suivante : « Déterminer si une collection de polygones peut paver le plan ou non. »

Ce problème est indécidable. Il n’existe pas d’algorithme, pas de méthode systématique qui détermine si une collection de polygones peut paver le plan ou non. Cette indécidabilité a été démontrée dans les années 1960.

Connaitre l’indécidabilité d’un problème a les deux avantages suivants.

Savoir qu’il est inutile de chercher un algorithme de résolution du problème.
Orienter l’étude du problème vers des sous-problèmes qui pourraient, quant à eux, être décidables.

Exemple
Si on réduit le problème du pavage à des carrés, qui sont des polygones particuliers (même de dimensions différentes), le sous-problème ainsi obtenu est décidable.

2. La calculabilité

a. Historique

Dans les années 1930, des mathématiciens ont formalisé les notions de problème et de méthode de calcul. Leur interrogation était la suivante : « Peut-on tout calculer ? Peut-on réduire tout calcul à une succession finie d’opérations arithmétiques élémentaires ? » Ainsi est née la notion de fonction calculable.

Tout d’abord, une fonction est une relation entre un ensemble de départ et un ensemble d’arrivée, qui à chaque élément de l’ensemble de départ associe un unique élément de l’ensemble d’arrivée.

Une fonction f est dite calculable si on peut la caractériser comme une succession finie de manipulations de symboles qui à n’importe quelle valeur x associe f(x).

Autrement dit, une fonction f est calculable s’il existe un algorithme qui permet de déterminer f(x) pour toutes valeurs de x.

Entre 1932 et 1936, Alonzo Church, un mathématicien américain, a identifié une classe de fonctions arithmétiques qui semblent correspondre aux fonctions calculables. Cette conjecture s’appelle la « Thèse de Church ».

Parallèlement à cela, en 1936, Alan Turing, un mathématicien britannique, a défini un modèle abstrait de machine mécanique qui permet d’effectuer des calculs. Il s’agit de la première modélisation de ce que seront les ordinateurs.

Un an après, Alan Turing a montré qu’il y avait une équivalence entre l’ensemble des fonctions programmables sur ses machines et l’ensemble des fonctions calculables. Toute fonction programmable est ainsi calculable et inversement. C’est pourquoi cette machine a été appelée machine universelle puisqu’elle pouvait faire fonctionner tous les algorithmes. Cette machine est maintenant nommée machine de Turing.

Finalement, Alan Turing et Alonzo Church ont à eux deux posé les bases de l’informatique en établissant l’équivalence entre l’ensemble des fonctions calculables, l’ensemble des fonctions arithmétiques et l’ensemble des fonctions programmables sur les machines de Turing. Cette équivalence constitue la Thèse de Church-Turing.

b. Décidabilité et calculabilité

La notion de décidabilité et celle de calculabilité sont semblables.

En effet, si P est un problème, son instance P(a) pour la valeur a est vraie ou fausse.

Ainsi tout problème est une fonction à valeurs dans l’ensemble {vrai, faux} :

P : a → P(a) {vrai, faux}

Si le problème P est décidable, alors il existe un algorithme qui le résout. La fonction P est donc calculable.

Réciproquement, si la fonction P est calculable, il existe un algorithme qui en calcule chaque image. Donc pour chaque valeur a, un algorithme permet de savoir si P(a) est vraie ou fausse. Le problème P est décidable.

3. Le problème de l'arrêt

a. Énoncé

Maintenant, une question reste : « Toutes les fonctions sont-elles calculables ? » La réponse fut tranchée dans les années 1930. Toutes les fonctions ne sont pas calculables.

Le problème de l’arrêt en est un exemple.

Le problème de l'arrêt s’énonce de la manière suivante : « Déterminer si un algorithme s’arrête ».

Le problème est ici de déterminer s’il existe une méthode systématique pour prouver qu’un algorithme se termine ou non.

b. Une démonstration

Le problème de l’arrêt est indécidable. Cela se démontre par l’absurde.

On suppose que ce problème est décidable. On montre ensuite qu’il y a une incohérence.

Démonstration par l’absurde
On suppose qu’il existe une fonction arrêt(A) qui à tout algorithme A associe Vrai si l’algorithme A se termine et Faux sinon.

Pour tout entier naturel n, on définit un algorithme Turing(n) de la manière suivante.

Lister les algorithmes qui s’écrivent avec au plus n caractères, qui prennent en entrée un entier et qui retournent un entier.
Avec la fonction arrêt, sélectionner les algorithmes qui se terminent si l’entrée est n.
Déterminer les nombres que chacun de ces algorithmes renvoie.
Renvoyer le plus grand de ces nombres + 1.

On étudie le cas où k est le nombre de caractères de l’algorithme Turing(n).
Si on teste Turing(k), on a alors :

Turing fait lui même partie de la liste des algorithmes qui s’écrivent avec au plus k caractères prenant en entrée un entier et retournant un entier.
Turing est sélectionné car cet algorithme s’arrête.
Si Turing(k) renvoie m₀, alors m₀ fait partie des nombres que les algorithmes sélectionnés renvoient.
Il y a deux possibilités :
- Si m₀ est le plus grand des nombres, alors Turing(k) renvoie m₀ + 1. C’est absurde car Turing(k) renvoie m₀.
- Si le plus grand des nombres est p₀ > m₀, alors Turing(k) renvoie p₀+ 1 > m₀ + 1. C’est absurde car Turing(k) renvoie m₀.