Informatique théorique
Travail demandé:
Qu’arrive-t-il quand on exécute un programme qui
vérifie le grand théorème de Fermat ?
Réponse:
Rappel de l’hypothèse de Fermat :
Pour n entier, n ≥ 3, il n’existe
pas d’entiers positifs a, b, c tels
que :
an + bn = cn
Programme en C++ :
Afin de constater ce qui se passe quand on
essaie de vérifier ce théorème, on a réalisé un programme en C++ dont voici le
code :
Quand on exécute le programme,
celui-ci nous demande d’introduire des valeurs de a, b et c pour vérifier l’hypothèse de Fermat.
Lorsqu’on
clique sur « Entrer », le programme s’exécute et ne s’arrête que lorsqu’une valeur (
an , bn , cn ou n) arrive à la valeur
correspondante à la taille limite du type de la variable ( la valeur limite dans notre cas est +ou-
1073741824 égale à 2*230),
résultat logique sachant que le compilateur utilisé alloue 4 octets aux variables
de type entier. Afin de concrétiser ceci le programme affiche n à chaque
exécution de la boucle.
Commentaire :
D’après l’exécution du programme on
constate qu’en aucun cas celui-ci arrive
à trouver une valeur de « n » vérifiant un contre exemple. Cependant,
ce résultat ne peut pas confirmer la vérification de l’hypothèse puisqu’il est
pratiquement impossible de vérifier tous les cas. Alors on peut dire que ce
programme (algorithme) est indécidable.
En
effet, une proposition est, logiquement, dite décidable dans une théorie
axiomatique, si on peut la démontrer ou démontrer sa négation dans le cadre de
cette théorie. Un énoncé mathématique est donc indécidable dans une théorie
s'il est impossible de le déduire, ou de déduire sa négation, à partir des
axiomes ; ceci d’une part.
D’autre
part, un algorithme consiste en un ensemble fini d'instructions simples et
précises qui sont décrites avec un nombre limité de symboles. Un algorithme
doit toujours produire le résultat en un nombre fini d'étapes. L’exécution d’un
algorithme ne requiert pas d'intelligence de l'humain sauf celle qui est
nécessaire pour comprendre et exécuter les instructions.
Ainsi,
on peut dire que le problème est décidable s'il existe un algorithme ou une
procédure mécanique qui termine en un nombre fini d'étapes, qui le décide,
c'est-à-dire qui réponde par
« oui » ou par
« non » à la question posée par le problème. S'il n'existe pas de
tels algorithmes, le problème est dit indécidable. En outre, le problème
décidable réfère à la notion de calculabilité en cherchant un algorithme qui
s’arrête à un temps fini et fournit la réponse OUI ou NON à la question posée.
Dans ce sens, dire qu'un problème est indécidable ne veut pas dire que les
questions posées sont insolubles mais seulement qu'il n'existe pas de méthode
unique et bien définie, applicable d'une façon mécanique, pour répondre à
toutes les questions, en nombre infini, rassemblées dans un même
problème ; et ceci correspond exactement à l’hypothèse de Fermat.
Pour
conclure, On peut dire que l’hypothèse de Fermat ne peut être vérifiée ni démontrée
à travers un algorithme exécuté sur une machine de Turing universelle.