Fiche de cours

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

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

Fiche de cours
Quiz et exercices
Vidéos et podcasts

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₀.

Ainsi la supposition initiale est fausse.

Donc le problème de l’arrêt est indécidable.

Évalue ce cours !

Note 4.5 / 5. Nombre de vote(s) : 11

Des quiz et exercices pour mieux assimiler sa leçon

La plateforme de soutien scolaire en ligne myMaxicours propose des quiz et exercices en accompagnement de chaque fiche de cours. Les exercices permettent de vérifier si la leçon est bien comprise ou s’il reste encore des notions à revoir.

S’abonner

Des exercices variés pour ne pas s’ennuyer

Les exercices se déclinent sous toutes leurs formes sur myMaxicours ! Selon la matière et la classe étudiées, retrouvez des dictées, des mots à relier ou encore des phrases à compléter, mais aussi des textes à trous et bien d’autres formats !

Dans les classes de primaire, l’accent est mis sur des exercices illustrés très ludiques pour motiver les plus jeunes.

S’abonner

Des quiz pour une évaluation en direct

Les quiz et exercices permettent d’avoir un retour immédiat sur la bonne compréhension du cours. Une fois toutes les réponses communiquées, le résultat s’affiche à l’écran et permet à l’élève de se situer immédiatement.

myMaxicours offre des solutions efficaces de révision grâce aux fiches de cours et aux exercices associés. L’élève se rassure pour le prochain examen en testant ses connaissances au préalable.

S’abonner

Des vidéos et des podcasts pour apprendre différemment

Certains élèves ont une mémoire visuelle quand d’autres ont plutôt une mémoire auditive. myMaxicours s’adapte à tous les enfants et adolescents pour leur proposer un apprentissage serein et efficace.

Découvrez de nombreuses vidéos et podcasts en complément des fiches de cours et des exercices pour une année scolaire au top !

S’abonner

Des podcasts pour les révisions

La plateforme de soutien scolaire en ligne myMaxicours propose des podcasts de révision pour toutes les classes à examen : troisième, première et terminale.

Les ados peuvent écouter les différents cours afin de mieux les mémoriser en préparation de leurs examens. Des fiches de cours de différentes matières sont disponibles en podcasts ainsi qu’une préparation au grand oral avec de nombreux conseils pratiques.

S’abonner

Des vidéos de cours pour comprendre en image

Des vidéos de cours illustrent les notions principales à retenir et complètent les fiches de cours. De quoi réviser sa prochaine évaluation ou son prochain examen en toute confiance !

S’abonner

Profs en ligne

Découvrez le soutien scolaire en ligne avec myMaxicours

Plongez dans l'univers de myMaxicours et découvrez une approche innovante du soutien scolaire en ligne, conçue pour captiver et éduquer les élèves de CP à la terminale. Notre plateforme se distingue par une riche sélection de contenus interactifs et ludiques, élaborés pour stimuler la concentration et la motivation à travers des parcours d'apprentissage adaptés à chaque tranche d'âge. Chez myMaxicours, nous croyons en une éducation où chaque élève trouve sa place, progresse à son rythme et développe sa confiance en soi dans un environnement bienveillant.

Profitez d'un accès direct à nos Profs en ligne pour une assistance personnalisée, ou explorez nos exercices et corrigés pour renforcer vos connaissances. Notre assistance scolaire en ligne est conçue pour vous accompagner à chaque étape de votre parcours éducatif, tandis que nos vidéos et fiches de cours offrent des explications claires et concises sur une multitude de sujets. Avec myMaxicours, avancez sereinement sur le chemin de la réussite scolaire, armé des meilleurs outils et du soutien de professionnels dédiés à votre épanouissement académique.

EXERCE-TOI EN T'ABONNANT