Le début du calcul moderne

Vnous allons aborder ici le paradoxal début de l'informatique moderne. Et je dis paradoxal, car elle est née non pas lorsque l'on cherchait une manière efficace de faire des calculs, mais lorsque l'on tentait de montrer qu'il existait des problèmes non calculables.

Le héros de cette histoire, c'est un certain Alan Turing, qui a déjà été personnage d'un film hollywoodien, "Le Jeu de l'Imitation"Le Jeu de l'Imitationet possède un prix de science informatique portant son nom, le Prix de Turing, décerné annuellement à un chercheur qui s'est distingué dans le domaine. En 1937, il a démontré mathématiquement qu'il existe des problèmes qui ne peuvent pas être calculés. Cependant, pour cela, il a dû définir ce que signifie "être calculable", et dans ce processus, il a créé les Machines de Turing. Ces machines sont des concepts mathématiques abstraits qui formalisent la notion de calcul, et un résultat mathématique important qu'il a découvert montre qu'il existe une machine spéciale, appelée Machine Universelle de Turing, qui joue un rôle central dans la Théorie de l'Informatique. Cette Machine Universelle de Turing est la base de la construction des ordinateurs tels que nous les connaissons aujourd'hui.

L'article initial de Turing contient certaines choses qui attirent l'attention et qui sont présentes dans le titre de l'article lui-même, traduit ici de manière libre :Sur les nombres calculables et une application au problème de décision. Comment, des nombres calculables ? Est-ce que cela signifie qu'il existe des nombres non calculables ?

Oui, et ce n'est pas si difficile à voir. Mais avant, revenons un peu dans le temps, car les débuts de l'informatique sont intimement liés aux nombres infinis. En 1874, le mathématicien allemand Georg Cantor a publié un article dans lequel il montrait qu'il existait plus d'un type d'infini. En particulier, il a montré que l'infini des nombres naturels 0,1,2,3, ... est inférieur à l'infini des nombres réels. Vous avez peut-être déjà remarqué cela, à partir d'un simple dessin. L'infini des nombres réels correspond à une ligne continue (cet ensemble est appelé Continu), et, sur cette ligne, bien espacées, nous pouvons insérer les nombres naturels ou les nombres entiers (la taille de cet infini est appelée Comptable). Avec une stratégie très innovante, Cantor a montré qu'il n'est pas possible d'aligner les éléments du Continu un par un avec les éléments Comptables, il reste toujours un certain nombre qui n'est pas aligné. De cette manière, il a montré que le continu est strictement plus grand que les nombres comptables.

Ainsi, Turing démontre qu'il existe des nombres réels non calculables. Les nombres non calculables sont toujours des éléments du Continu. Selon sa définition, un nombre réel est calculable si un programme ou, dans sa version originale, une Machine de Turing, imprime infiniment ses chiffres. Mais chaque programme et chaque Machine de Turing ont une taille finie et sont stockés dans un fichier. Un fichier n'est rien d'autre qu'un nombre naturel, qui peut être très grand. Ainsi, le nombre maximum de programmes est un infini comptable, et il ne peut pas y avoir suffisamment de programmes pour imprimer tous les nombres réels. De nombreux nombres réels ne peuvent pas être imprimés par aucun programme, et ce sont les nombres réels non calculables. Et nous savons maintenant que la plupart des nombres réels ne sont pas calculables, seulement une petite proportion d'entre eux peuvent être imprimés par un programme ou par une Machine de Turing.

Une petite rumeur ici. Lorsque Turing a écrit son article en 1936, sans que cela soit de son fait, un autre mathématicien célèbre, appelé Alonzo Church, avait déjà démontré l'existence de nombres non calculables, en utilisant des techniques très différentes. Ainsi, les éditeurs du journal se sont mis en doute si l'article de Turing était véritablement original. L'article est resté sur une table jusqu'à ce qu'une personne ait eu l'idée de montrer cet article au propre Church, qui a trouvé l'idée de Turing si originale qu'il l'a invité à être son étudiant à doctorat aux États-Unis. C'est pour cette attente que l'article n'a été publié qu'en 1937. Turing a terminé son doctorat en un an et était de retour en Angleterre lorsque la Seconde Guerre mondiale a éclaté. C'est là que commence l'histoire du film.Le Jeu de l'Imitation, après que Turing ait déjà apporté sa grande contribution à l'histoire de l'informatique moderne.

Retour aux nombres, la première réaction des gens lorsqu'ils apprennent qu'il existe des nombres non calculables est la suivante : "S'il vous plaît, montrez-moi un exemple de nombre non calculable". Et moi, avec plaisir, je réponds : "Je ne peux pas le montrer. Si je montre le nombre, je l'ai déjà calculé. Et un nombre non calculable ne peut pas être calculé. C'est évident, n'est-ce pas ? Bon, si ce n'est pas évident, habituez-vous à l'idée que vous ne pourrez jamais voir un nombre non calculable, exactement parce qu'il n'est pas calculable".

Mais, si le nombre n'est pas comptable, comment le désignons-nous ? Eh bien, nous devons utiliser des formes indirectes pour définir le nombre sans effectuer de calcul. Un exemple bien connu est "la probabilité qu'un programme informatique s'arrête". Cette expression entre guillemets est la définition du nombre. Il est démontré que ce nombre est non comptable et dont nous ne pouvons connaître presque aucune propriété. Il n'est pas possible de savoir si ce nombre est inférieur à 0,5 ou supérieur à 0,00000001. Toutes ces questions sont également des questions non comptables.

Et cela nous ramène à l'article initial d'Alan Turing. Il a montré qu'il existe des problèmes non comptables, c'est-à-dire qu'ils ne peuvent pas être calculés par aucune Machine de Turing, y compris le fameux Problème de Décision (de la logique de premier ordre) qui figurait dans le titre de son article.

Et c'est ainsi que la computation moderne a pris naissance, montrant que la computation a des limites. Il existe des choses qui ne pourront jamais être calculées, et nous devons vivre dans les limites de ce qu'il est possible de faire avec une machine de computation. Le Théorème de Turing ne dépend d'aucune langue de programmation et aucun type de ordinateur. Ainsi, les problèmes non comptables restent non comptables avec toute technologie, même avec l'intelligence artificielle la plus moderne ou les technologies qui seront inventées dans plus d'un siècle.

________________
(Les opinions exprimées dans les articles publiés dansLe Journal de l'USPLa seule responsabilité de leurs auteurs et ne reflètent pas les opinions du média ni les positions institutionnelles de l'Université de São Paulo. Veuillez consulter ici nosparamètres éditoriaux pour les articles d'opinion.)