::TOC::

LAAXIOMA Axiomatique

Axiomatique, Encyclopédie Larousse en ligne, https://www.larousse.fr/encyclopedie/divers/axiomatique/187310.

LAAXIOMA.1 Cf. Axiomatique, Larousse, op. cit. : Méthode de construction des sciences qui n’utilise qu’un ensemble d’axiomes, certains de ces derniers exposant la logique de la marche à suivre. (C’est en comparant les résultats prédits et l’expérience que l’on garde ou modifie les axiomes de départ.)

LAAXIOMA.2 Cf. Axiomatique, Larousse, op. cit. : Le terme “axiomatique” s’entend en deux sens. C’est d’abord une axiomatique : système formel constitué d’un ensemble d’énoncés admis sans démonstration (axiomes ou postulats), suivi d’un nombre fini de règles de déduction. C’est ensuite la méthode axiomatique : le mode d’écriture et la forme de pensée sous lesquels les sciences exactes veulent parfois se présenter. Dans les deux cas, une exigence sous-jacente est à l’œuvre : l’implicite, le non-dit, l’allusif, voire le bon sens doivent être proscrits de toute théorie. Celle-ci doit exhiber clairement ses propositions premières non démontrées (axiomes) ainsi que les règles de déduction qu’elle emploie, et cela de façon exhaustive. L’exhaustivité est une obligation générale des systèmes formels : ils contiennent tous une règle dite règle de fermeture, qui énonce simplement qu’aucune proposition, aucun énoncé ne peut apparaître valablement s’il n’est déduit des axiomes grâce aux règles de déduction présentes dans la théorie. Historiquement, les axiomatiques apparaissent toujours après des périodes appelées tératologiques, où une science a, correctement mais malgré elle, produit des “monstres” : objets rigoureusement issus de théorèmes communément admis, mais heurtant le bon sens. Lorsque l’irrationalité de la diagonale du carré fut découverte par des mathématiciens grecs qui tenaient pour acquis que tout objet du monde devait se décrire par un nombre entier ou rationnel (les pythagoriciens), apparut dans la mathématique naissante un conflit entre le savoir et le bon sens : racine de 2 était un monstre. Les Éléments d’Euclide (IIIe siècle avant J.-C..), longtemps considérés comme un modèle d’axiomatique, vinrent “mettre à plat” le savoir de l’époque et redéfinir pour près de vingt-deux siècles les fondements de la science mathématique. Beaucoup de ce que nous considérons comme fondamental dans une théorie axiomatisée y figure : les axiomes, les notions communes (axiomes de la logique), les formes de la déduction héritées d’Aristote, jusqu’à cette sorte d’hésitation qui lui fit nommer postulats des axiomes dont l’avenir montrera tout l’aspect problématique. Archimède, dans son étude des lois de l’équilibre des leviers, fit sienne cette méthode.

LAAXIOMA.3 Cf. Axiomatique, Larousse, op. cit. : La seconde période tératologique survint au XIXe siècle : on vit apparaître des objets inadmissibles comme la courbe discontinue dérivable en tout point ou la courbe passant par tous les points d’un plan (Hilbert). Si certains résultats de la géométrie projective posèrent problème, c’est surtout l’invention des géométries non euclidiennes, heurtant fortement le bon sens tel que le concevait Descartes, qui imposa l’exigence d’une méthode axiomatique. À l’idée d’explicite proposée par Euclide se surajouta celle d’abstraction de l’objet formel. Les axiomes et règles de déduction doivent être dépouillés de tout contenu réel et de toute signification particulière. La géométrie peut se faire “avec des tables, des chaises et des verres à bière”, disait Hilbert. Seules comptent les relations que les objets entretiennent entre eux : c’est sur ces relations que portent les axiomes. Explicite et abstraction formelle ont amené les mathématiques à repenser leurs fondements : sur quoi fallait-il faire reposer l’édifice pour en chasser définitivement les monstres ? La présence nécessaire à l’intérieur de toute théorie de lois de déduction issues de la logique est à l’origine du logicisme (Boole, Frege, Russell) : le fondement des théories serait “externe”, et la logique serait la racine des mathématiques ; elle seule ne possède aucun contenu intuitif, manipule des objets vides et des énoncés non interprétés qui ne peuvent donc pas entrer en conflit avec le sens commun. Le logicisme, considéré comme réductionnisme, eut le mérite de permettre de définir très exactement ce qu’était un système formel liant ainsi définitivement entre eux les termes d’axiomatisation et de formalisation d’une théorie. Celle-ci devient alors théorie formelle ou système formel.

LAAXIOMA.4 Cf. Axiomatique, Larousse, op. cit. : Un système formel se constitue en quatre étapes. – Dresser la liste exhaustive (finie ou dénombrable) de tous les symboles qui peuvent apparaître dans une théorie : une suite finie de symboles sera appelée une expression ou mot du langage. – Définir des règles de bonne formation des mots qui constitueront le vocabulaire de cette théorie. Les mots bien formés seront nommés formules : ce sont les propositions (vraies ou fausses) de la théorie. Ces règles de bonne formation sont d’ordinaire récursives et il existe généralement un algorithme permettant de décider si une expression est ou non une formule. Il faut leur adjoindre la règle générale de tout système formel, la règle de fermeture, qui affirme qu’aucune formule ne peut exister si elle n’est pas issue des règles précédentes. Ces deux premières étapes définissent la phase de formalisation, qui est suivie par la phase d’axiomatisation. – Sélectionner parmi l’ensemble des expressions bien formées un sous-ensemble de formules appelées axiomes du système, énoncés “réputés vrais” pour la théorie et admis sans démonstration. Le choix de ces formules est de la seule liberté de l’inventeur de la théorie, qui ne reconnaît aucune instance supérieure à lui pour limiter son choix. – Définir une liste finie de relations nommées règles d’inférence ou règles de déduction, qui sont normalement celles de la logique mathématique. Là encore, il ne faut pas oublier la règle de fermeture. Après ces quatre étapes, la théorie possède pour énoncés admissibles les seuls axiomes. On appelle démonstration une suite finie de formules telle que chacune est soit un axiome, soit la conséquence d’une formule précédente par application d’une règle de déduction. La dernière formule (qui n’est pas un axiome) d’une démonstration est un théorème : autrement dit, un théorème est une formule pour laquelle il existe une démonstration. Un des problèmes fondamentaux des théories axiomatisées consiste à se demander s’il existe un algorithme permettant de décider, pour toute formule du système, si elle est ou non un théorème. Si cet algorithme existe, la formule est dite décidable ; sinon, elle est indécidable. Les mêmes mots s’appliquent à la théorie qui contient la formule.

LAAXIOMA.5 Cf. Axiomatique, Larousse, op. cit. : Les axiomatiques les plus connues sont celle de Giuseppe Peano sur la théorie des nombres entiers, celle de David Hilbert sur la géométrie élémentaire (Grundlagen der Geometrie, 1899) et celle de Andreï N. Kolmogorov (1933) sur la théorie des probabilités. Les axiomatiques de Peano et Hilbert sont encore des “théories-de” (la géométrie, l’arithmétique…) ; elles prennent racine dans des savoirs existants qu’elles formalisent. Mais le mouvement axiomatique s’accentue jusqu’à proposer des systèmes formels sans référent théorique préalable. C’est ainsi qu’une notion classique de la pensée mathématique s’étiole jusqu’à disparaître : la vérité. Le divorce entre le savoir et l’intuition rend les axiomes “libres” : ils ne sont donc pas vrais au sens cartésien du terme, mais ils s’apparentent plus à des hypothèses générales. Issue de ces axiomes, la théorie elle-même n’est plus vraie mais seulement valide, et l’on exige d’elle deux propriétés nécessaires et suffisantes : la consistance (non-contradiction) et l’indépendance de ses axiomes. La non-contradiction est alors la seule garantie de validité de la théorie, qui ne peut produire deux énoncés dont l’un est la négation de l’autre, sous peine de produire alors n’importe quel théorème (y compris celui qui affirme que la théorie est fausse). Les axiomes doivent être indépendants : si un axiome se déduit d’un autre axiome, alors il perd son statut et devient un théorème. La décidabilité est également une propriété des théories formelles, mais elle n’est sûrement pas nécessaire. De 1931 à 1936, Kurt Gödel pour l’arithmétique ordinaire, Alonzo Church pour la logique des prédicats et Alan M. Turing pour les fonctions non récursives montrèrent le caractère non décidable de ces théories réputées simples et fondamentales. L’énoncé qui affirme la non-contradiction de la théorie ne peut être ni démontré ni infirmé. Alfred Tarski généralisa ces résultats (1936), en montrant que ce type d’énoncé ne peut être un théorème à l’intérieur d’une théorie, mais que sa démonstration réclame une théorie plus forte (c’est-à-dire possédant au moins un axiome de plus).

LAAXIOMA.6 Cf. Axiomatique, Larousse, op. cit. : La notion de “théorie-de” fait alors place à celle de modèle. L’axiomatique et son système formel existent en soi et sont créés pour leur logique interne sans rapport aucun avec des objets. Une théorie qui s’abriterait à l’intérieur de ce formalisme en deviendrait un modèle. S’il s’agit d’une théorie physique, un résultat négatif issu d’expérimentations n’infirmera aucunement l’axiomatique ; simplement, d’autres axiomes devront être choisis pour que la théorie physique en devienne un bon modèle. La théorie des modèles est le dernier développement des axiomatiques modernes. Mais, parce que les formalismes axiomatiques ont détruit le concept de vérité, ils ont entraîné les mathématiques vers d’autres débats. À vouloir raisonner sur les objets quelconques, à ne prendre en compte que des propriétés dénuées d’intuition, les formalismes se sont totalement détachés de la réalité et sont devenus un jeu sans rapport avec les sciences appliquées. Quelle est l’existence d’un objet mathématique ? Suffit-il de démontrer son existence pour qu’il ait droit de cité ou bien faut-il réellement le construire ? Les formalistes diront que les mathématiques n’ont jamais eu de rapport avec le réel : “Trois arbres, cela existe, mais le nombre trois ?” Inversement, les constructivistes (Brouwer) exigeront une méthode algorithmique pour admettre l’existence de nombres transcendants. Suffit-il que la non-contradiction d’un objet soit démontrée pour que son existence soit établie et peut-on tenir des raisonnements corrects sur des objets non existants ? Puis-je raisonner sur “la calvitie de l’actuel roi de France” ? se demandait Bertrand Russell. L’objection à la méthode axiomatique réside essentiellement dans son caractère appauvrissant : le “ciel” où Cantor situe les mathématiques les éloigne de nos préoccupations quotidiennes et l’incompréhension qui accompagna les mathématiques ensemblistes dans le système éducatif en France en est un des multiples symptômes. Mais les constructivistes n’apportent rien de plus. La véritable question est finalement épistémologique : une science fortement impliquée dans le développement social peut-elle demeurer longtemps détachée de ce qu’une société considère comme étant “le réel” ? Mais, aussi et inversement, une science peut-elle demeurer libre ?

WPAPPAUT Apprentissage automatique

Apprentissage automatique, Wikipédia, https://fr.wikipedia.org/wiki/Apprentissage_automatique.

WPAPPAUT.1 Cf. Apprentissage automatique, Wikipédia, op. cit. : L’apprentissage automatique (en anglais machine learning, littéralement “apprentissage machine”) ou apprentissage statistique est un champ d’étude de l’intelligence artificielle qui se fonde sur des approches mathématiques et statistiques pour donner aux ordinateurs la capacité d’“apprendre” à partir de données, c’est-à-dire d’améliorer leurs performances à résoudre des tâches sans être explicitement programmés pour chacune.

WPAPPAUT.2 Cf. Apprentissage automatique, Wikipédia, op. cit. : L’apprentissage automatique comporte généralement deux phases. La première consiste à estimer un modèle à partir de données, appelées observations, qui sont disponibles et en nombre fini, lors de la phase de conception du système. L’estimation du modèle consiste à résoudre une tâche pratique, telle que traduire un discours, estimer une densité de probabilité, reconnaître la présence d’un chat dans une photographie ou participer à la conduite d’un véhicule autonome. Cette phase dite “d’apprentissage” ou “d’entraînement” est généralement réalisée préalablement à l’utilisation pratique du modèle. La seconde phase correspond à la mise en production : le modèle étant déterminé, de nouvelles données peuvent alors être soumises afin d’obtenir le résultat correspondant à la tâche souhaitée. En pratique, certains systèmes peuvent poursuivre leur apprentissage une fois en production, pour peu qu’ils aient un moyen d’obtenir un retour sur la qualité des résultats produits.

WPAPPAUT.3 Cf. Apprentissage automatique, Wikipédia, op. cit. : La concrétisation de cette idée est principalement due à Alan Turing (mathématicien et cryptologue britannique) et à son concept de la “machine universelle” en 1936, qui est à la base des ordinateurs d’aujourd’hui. Il continuera à poser les bases de l’apprentissage automatique, avec son article sur “L’ordinateur et l’intelligence” en 1950, dans lequel il développe, entre autres, le test de Turing.

WPAPPAUT.4 Cf. Apprentissage automatique, Wikipédia, op. cit. : Les algorithmes utilisés permettent, dans une certaine mesure, à un système piloté par ordinateur (un robot éventuellement), ou assisté par ordinateur, d’adapter ses analyses et ses comportements en réponse, en se fondant sur l’analyse de données empiriques provenant d’une base de données ou de capteurs. La difficulté réside dans le fait que l’ensemble de tous les comportements possibles compte tenu de toutes les entrées possibles devient rapidement trop complexe à décrire (on parle d’explosion combinatoire). On confie donc à des programmes le soin d’ajuster un modèle pour simplifier cette complexité et de l’utiliser de manière opérationnelle. Idéalement, l’apprentissage visera à être non supervisé, c’est-à-dire que la nature des données d’entrainement n’est pas connue. Ces programmes, selon leur degré de perfectionnement, intègrent éventuellement des capacités de traitement probabiliste des données, d’analyse de données issues de capteurs, de reconnaissance (reconnaissance vocale, de forme, d’écriture…), de fouille de données, d’informatique théorique…

WPAPPAUT.5 Cf. Apprentissage automatique, Wikipédia, op. cit. : Si les classes sont prédéterminées et les exemples connus, le système apprend à classer selon un modèle de classification ou de classement ; on parle alors d’apprentissage supervisé (ou d’analyse discriminante). Un expert (ou oracle) doit préalablement étiqueter des exemples. Le processus se passe en deux phases. Lors de la première phase (hors ligne, dite d’apprentissage), il s’agit de déterminer un modèle à partir des données étiquetées. La seconde phase (en ligne, dite de test) consiste à prédire l’étiquette d’une nouvelle donnée, connaissant le modèle préalablement appris.

WPAPPAUT.6 Cf. Apprentissage automatique, Wikipédia, op. cit. : Quand le système ou l’opérateur ne dispose que d’exemples, mais non d’étiquette, et que le nombre de classes et leur nature n’ont pas été prédéterminées, on parle d’apprentissage non supervisé ou clustering en anglais. Aucun expert n’est requis. L’algorithme doit découvrir par lui-même la structure plus ou moins cachée des données. Le partitionnement de données, data clustering en anglais, est un algorithme d’apprentissage non supervisé. Le système doit ici – dans l’espace de description (la somme des données) – cibler les données selon leurs attributs disponibles, pour les classer en groupes homogènes d’exemples. La similarité est généralement calculée selon une fonction de distance entre paires d’exemples. C’est ensuite à l’opérateur d’associer ou déduire du sens pour chaque groupe et pour les motifs (patterns en anglais) d’apparition de groupes, ou de groupes de groupes, dans leur “espace”. Divers outils mathématiques et logiciels peuvent l’aider. On parle aussi d’analyse des données en régression (ajustement d’un modèle par une procédure de type moindres carrés ou autre optimisation d’une fonction de coût). Si l’approche est probabiliste (c’est-à-dire que chaque exemple, au lieu d’être classé dans une seule classe, est caractérisé par un jeu de probabilités d’appartenance à chacune des classes), on parle alors de “soft clustering” (par opposition au “hard clustering”).

WPAPPAUT.7 Cf. Apprentissage automatique, Wikipédia, op. cit. : L’apprentissage automatique ne se résume pas seulement à un ensemble d’algorithmes mais c’est une listes d’étapes à prendre en compte et à exécuter afin d’arriver à un résultat optimal: 1. L’acquisition de données : L’algorithme se nourrissant des données en entrée, c’est une étape importante. Il en va de la réussite du projet, de récolter des données pertinentes et en quantité suffisante. 2. La préparation, et le nettoyage de la donnée : Il peut arriver que la donnée recueillie à l’étape précédente ne soit pas pleinement pertinente, ou contienne du bruit, ou ne soit pas assez structurée. Un opérateur humain va donc optimiser la donnée pour que l’algorithme puisse mieux la traiter, ou arriver plus rapidement à son but. 3. La création du modèle. 4. L’évaluation : Une fois l’algorithme d’apprentissage automatique entrainé sur un premier jeu de donnée, on va l’évaluer sur un deuxième ensemble de données afin de vérifier que le modèle ne fasse pas de surapprentissage. 5. Le déploiement : Le modèle va être déployé en production pour faire des prédictions, et potentiellement utiliser les nouvelles données en entrée pour se ré-entrainer et améliorer son modèle.

WPAPPAUT.8 Cf. Apprentissage automatique, Wikipédia, op. cit. : L’apprentissage automatique demande de grandes quantités de données pour fonctionner correctement. […] La qualité des “décisions” prises par un algorithme d’AA dépend non seulement de la qualité (donc de leur homogénéité, fiabilité, etc.) des données utilisées pour l’entrainement mais surtout de leur quantité. Donc, pour un jeu de données sociales collecté sans attention particulière à la représentation des minorités, l’AA est statistiquement injuste vis-à-vis de celles-ci. En effet, la capacité à prendre de “bonnes” décisions dépend de la taille des données, or celle-ci sera proportionnellement inférieure pour les minorités. […] L’utilisation d’algorithmes d’apprentissage automatique demande donc d’avoir conscience du cadre de données que l’on a utilisé pour l’apprentissage lors de leur utilisation. Il est donc prétentieux d’attribuer des vertus trop grandes aux algorithmes d’apprentissage automatique.

WPAPPAUT.9 Cf. Apprentissage automatique, Wikipédia, op. cit. : Contrairement aux algorithmes classiques (qui suivent un ensemble de règles prédéterminées), l’apprentissage automatique apprend ses propres règles. […] Le principe de responsabilité est remis en cause par l’apprentissage automatique, car l’algorithme n’est plus écrit mais apprend et développe une sorte d’intuition numérique. Les créateurs d’algorithmes ne sont plus en mesure de comprendre les “décisions” prises par leurs algorithmes, ceci par construction mathématique même de l’algorithme d’apprentissage automatique.

WPAXICHO Axiome du choix

Axiome du choix, Wikipédia, https://fr.wikipedia.org/wiki/Axiome_du_choix.

WPAXICHO.1 Cf. Axiome du choix, Wikipédia, op. cit. : Cet axiome fait partie des axiomes optionnels et controversés de la théorie des ensembles. En effet, l’existence d’un objet défini à partir de l’axiome du choix n’est pas une existence constructive, c’est-à-dire que l’axiome ne décrit aucunement comment construire l’objet dont on affirme l’existence [Une telle construction est d’ailleurs démontrée impossible (en n’utilisant que les axiomes de ZF), car sinon, elle donnerait une preuve de l’axiome du choix dans ZF, contredisant le résultat de Paul Cohen.].

WPBROHIL Brouwer-Hilbert controversy

Brouwer-Hilbert controversy, Wikipédia, https://en.wikipedia.org/wiki/Brouwer%E2%80%93Hilbert_controversy.

WPBROHIL.1 Cf. Brouwer-Hilbert controversy, Wikipédia, op. cit. : In a foundational controversy in twentieth-century mathematics, L. E. J. Brouwer, a supporter of intuitionism, opposed David Hilbert, the founder of formalism.

WPBROHIL.2 Cf. Brouwer-Hilbert controversy, Wikipédia, op. cit. : At issue in the sometimes bitter disputes was the relation of mathematics to logic, as well as fundamental questions of methodology, such as how quantifiers were to be construed, to what extent, if at all, nonconstructive methods were justified, and whether there were important connections to be made between syntactic and semantic notions. […] partisans of three principal philosophical positions took part in the debate – the logicists (Gottlob Frege and Bertrand Russell), the formalists (David Hilbert and his “school” of collaborators), and the constructivists (Henri Poincaré and Hermann Weyl); within this constructivist school was the radical self-named “intuitionist” L.E.J. Brouwer.

WPBROHIL.3 Cf. Brouwer-Hilbert controversy, Wikipédia, op. cit. : Brouwer in effect founded the mathematical philosophy of intuitionism as a challenge to the then-prevailing formalism of David Hilbert and his collaborators Paul Bernays, Wilhelm Ackermann, John von Neumann and others.

WPBROHIL.4 Cf. Brouwer-Hilbert controversy, Wikipédia, op. cit. : The fundamental issue is just how does one choose “the axioms”?

WPBROHIL.5 Cf. Brouwer-Hilbert controversy, Wikipédia, op. cit. : If successful the quest would result in a remarkable outcome: Given such a generalized proof, all mathematics could be replaced by an automaton consisting of two parts: (i) a formula-generator to create formulas one after the other, followed by (ii) the generalized consistency proof, which would yield “Yes – valid (i.e. provable)” or “No – not valid (not provable)” for each formula submitted to it (and every possible assignment of numbers to its variables). In other words: mathematics would cease as a creative enterprise and become a machine.

WPCALCUL Calculabilité

Calculabilité, Wikipédia, https://fr.wikipedia.org/wiki/Calculabilit%C3%A9.

WPCALCUL.1 Cf. Calculabilité, Wikipédia, op. cit. : La calculabilité cherche d’une part à identifier la classe des fonctions qui peuvent être calculées à l’aide d’un algorithme et d’autre part à appliquer ces concepts à des questions fondamentales des mathématiques. Une bonne appréhension de ce qui est calculable et de ce qui ne l’est pas permet de voir les limites des problèmes que peuvent résoudre les ordinateurs.

WPCALCUL.2 Cf. Calculabilité, Wikipédia, op. cit. : Intuitivement, une fonction f est une fonction calculable s’il existe une méthode précise qui, étant donné un argument x, permet d’obtenir l’image f(x) en un nombre fini d’étapes. Plusieurs formalisations mathématiques de ce que peut être une méthode de calcul existent et on peut montrer qu’un grand nombre d’entre elles (fonctions récursives, machine de Turing, lambda-calcul, machine à compteurs, automate cellulaire, etc.) sont équivalentes, c’est-à-dire qu’elles définissent exactement les mêmes fonctions calculables. Formellement, une fonction calculable est donc une fonction calculable selon l’une de ces définitions, par exemple le lambda-calcul.

WPCALCUL.3 Cf. Calculabilité, Wikipédia, op. cit. : Turing définit un nombre réel calculable comme étant un nombre dont l’expression décimale est calculable avec des moyens finis. Autrement dit, il existe une machine de Turing qui permet d’énumérer la suite de tous les chiffres de ce nombre (en un temps infini).

WPCALCUL.4 Cf. Calculabilité, Wikipédia, op. cit. : Gregory Chaitin a introduit un nombre Ω qui a, entre autres, la particularité d’être parfaitement défini, mais dont la suite des décimales ne peut pas être donnée par une fonction calculable.

WPCALCUL.5 Cf. Calculabilité, Wikipédia, op. cit. : Ada Lovelace, en plus d’être la première programmeuse au monde, suggère que la machine est un calculateur universel, préfigurant la notion de calculabilité.

WPCALCUL.6 Cf. Calculabilité, Wikipédia, op. cit. : De plus, à l’époque de la crise des fondements des mathématiques, David Hilbert s’oppose fermement à l’idée que certaines questions scientifiques restent sans réponse. Il croit au tiers exclu ; un principe logique qui affirme qu’une proposition est soit démontrable, soit sa négation est démontrable. Pour régler le problème de ces fondements, il rédige un programme (qu’on appelle aujourd’hui programme de Hilbert) dont il établit les prémices en 1900 dans l’introduction à sa liste de problèmes. Il développe ensuite ce programme dans les années 1920 avec l’aide de Paul Bernays et Wilhelm Ackermann. Son idée est que tant que ce que l’on manipule est fini, les mathématiques sont sûres. Pour justifier l’utilisation d’objets abstraits ou idéaux, en particulier infinis, il suffit de montrer que la théorie qui les utilise est cohérente, mais bien sûr cette cohérence doit elle-même être démontrée par des moyens finis. On appelle cette approche le “formalisme”.

WPCALCUL.7 Cf. Calculabilité, Wikipédia, op. cit. : Kurt Gödel assiste à une conférence de David Hilbert sur la complétude et la cohérence des systèmes mathématiques lorsqu’il est encore étudiant. Il obtient son doctorat en 1929 grâce à sa thèse où il établit la complétude du calcul des prédicats du premier ordre (en termes intuitifs, ce théorème nous apporte que tout énoncé vrai est démontrable), résultat connu sous le nom de théorème de complétude de Gödel. Ce théorème va dans le sens de Hilbert. Cependant, en 1931, il publie ses célèbres théorèmes d’incomplétude. Il y montre que pour toute théorie axiomatique non contradictoire de l’arithmétique, il existe des énoncés arithmétiques vrais qui ne sont pas démontrables dans cette théorie. Autrement dit, Gödel marque un tournant dans l’histoire de la logique puisqu’il anéantit la possibilité d’une démonstration de la cohérence des mathématiques énoncée vingt ans auparavant dans le programme de Hilbert.

WPCALCUL.8 Cf. Calculabilité, Wikipédia, op. cit. : Turing, quant à lui, caractérise un peu plus tard en 1936, dans son article “On Computable Numbers, with an Application to the Entscheidungsproblem”, ce qu’est un procédé calculable. Pour cela, il imagine non pas une machine matérielle, mais un “être calculant” qui peut être un appareil logique très simple ou un humain bien discipliné appliquant des règles. On appellera cette machine, la machine de Turing. Dans le cours de son raisonnement, il démontre que le problème de l’arrêt d’une machine de Turing ne peut être résolu par algorithme : il n’est pas possible de décider avec un algorithme (c’est-à-dire avec une machine de Turing) si une machine de Turing donnée s’arrêtera. Son article présente également la notion de nombre réel calculable puisqu’il déduit de l’indécidabilité du problème de l’arrêt que l’on peut définir des nombres réels qui ne sont pas calculables. Turing introduit ainsi les concepts de programme et de programmation. Kleene et Turing démontrent en 1938 que le lambda-calcul de Church, les fonctions générales récursives (modèle dit de Herbrand-Gödel) et les machines de Turing ont des capacités équivalentes. Cette équivalence démontre ensuite qu’un certain nombre de formalisations mathématiques de la notion de traitement par des processus mécaniques ont des aptitudes en tous points semblables à l’intuition de Church. Cette constatation aboutit à la thèse de Church (appelée aussi thèse de Church-Turing).

WPCOMPUT Computationnalisme

Computationnalisme, Wikipédia, https://fr.wikipedia.org/wiki/Computationnalisme.

WPCOMPUT.1 Cf. Computationnalisme, Wikipédia, op. cit. : Le computationnalisme est une théorie fonctionnaliste en philosophie de l’esprit qui, pour des raisons méthodologiques, conçoit l’esprit comme un système de traitement de l’information et compare la pensée à un calcul (en anglais, computation) et, plus précisément, à l’application d’un système de règles. Par computationnalisme, on entend la théorie développée en particulier par Hilary Putnam et Jerry Fodor, et non le cognitivisme en général.

WPCOMPUT.2 Cf. Computationnalisme, Wikipédia, op. cit. : En anglais, la computation se réfère à la calculabilité, c’est-à-dire au fait de passer d’une entrée à une sortie par le biais d’un algorithme déterminé. Le computationnalisme n’est pas une thèse ontologique sur la nature de l’esprit : il ne prétend pas que toute pensée se réduit à un calcul de ce style, mais qu’il est possible d’appréhender certaines fonctions de la pensée selon ce modèle, qu’elles soient conscientes ou infraconscientes (par exemple les processus de vision, selon l’approche des neurosciences computationnelles développé par David Marr au début des années 1980).

WPCOMPUT.3 Cf. Computationnalisme, Wikipédia, op. cit. : Deux noyaux théoriques ont aussi été essentiels à la formation de la théorie computationnaliste : d’une part, le formalisme mathématique développé au début du XXe siècle, qui permet en gros de concevoir les mathématiques comme la manipulation de symboles à partir de règles formelles (axiomatique de Hilbert) ; d’autre part, la calculabilité (et la machine de Turing). À l’aide de ces deux ensembles théoriques, on peut passer du noyau sémantique à la simple syntaxe mathématique, et de celle-ci à l’automatisation, sans jamais nier l’existence de la sémantique (c’est-à-dire du sens).

WPCOMPUT.4 Cf. Computationnalisme, Wikipédia, op. cit. : C’est par le biais, d’une part, du formalisme mathématique, développé à la fin du XIXe siècle par Gauss, Peano, Frege et Hilbert, et d’autre part de la calculabilité, que le computationnalisme traite ce problème. En effet, le formalisme réussit, en élaborant une axiomatique, à exclure ou à codifier les intuitions sémantiques du mathématicien (par exemple l’intuition à la source du postulat sur la parallèle d’Euclide). Le formalisme considère ainsi, en grossissant le trait, que les mathématiques existent en dehors de toute intention et de toute pensée. Ils fonctionnent à l’aide de symboles qui demandent à être manipulés selon des règles formelles. Le deuxième aspect mathématique décisif dans la théorie computationnaliste, c’est la définition des fonctions calculables par Alan Turing, en 1936. En élaborant le modèle abstrait de la machine de Turing, celui-ci montrait que toute opération n’impliquant que des schémas syntaxiques pouvait être dupliqué mécaniquement. On parle aussi de la thèse de Church-Turing. Ainsi, la formalisation mathématique montre comment les propriétés sémantiques des symboles peuvent parfois être codés selon des règles syntaxiques, tandis que la machine de Turing montre comment la syntaxe peut être relié à un processus causal, qui permet de concevoir un mécanisme capable d’évaluer toute fonction formalisable. La formalisation relie la sémantique à la syntaxe, et la machine de Turing la syntaxe au mécanisme.

WPCOMPUT.5 Cf. Computationnalisme, Wikipédia, op. cit. : L’hypothèse du “mécanisme numérique” (“digital mecanism”) a été développée par Bruno Marchal, en y adjoignant 2 hypothèses d’une autre nature : d’une part, la thèse de Church, pierre d’angle de l’informatique théorique ; d’autre part, ce qu’il appelle le réalisme arithmétique, c’est-à-dire le fait que la vérité arithmétique est intrinsèque, “d’une ontologie non substantielle”, dixit Marchal.

WICOMPUT.6 Cf. Computationnalisme, Wikipédia, op. cit. : le computationnalisme postule qu’on peut assimiler la pensée à un système d’application de règles, ce qui permet en retour d’identifier des fonctions informatiques complexes comme étant un équivalent de pensée.

WPCOMPUT.7 Cf. Computationnalisme, Wikipédia, op. cit. : Un autre argument a été formulé par Hubert Dreyfus dans What Computers Can’t Do (1972). Fin connaisseur de Heidegger et de la phénoménologie, Dreyfus souligne ainsi la différence centrale qui distingue le processus cognitif utilisé lorsqu’un novice apprend une compétence et lorsqu’un expert agit. Ainsi, un joueur d’échec débutant applique un système de règles (par exemple, avancer le pion de deux cases ou occuper le centre). Mais un champion d’échecs n’applique pas de règles : il “voit” le “coup juste”. L’application de règles, au cœur du computationnalisme, serait ainsi le propre des processus cognitifs limités. Il est difficile, en particulier, de transformer une compétence experte en algorithme, lorsque cette compétence tire ses ressources d’une connaissance générale étrangère au domaine du problème visé.

WPCOMPUT.8 Cf. Computationnalisme, Wikipédia, op. cit. : Donald Knuth suggère que le conscient est de nature séquentielle (nous ne pouvons analyser clairement qu’une chose à la fois) et l’inconscient de nature parallèle. Il y voit une raison du grand succès de la programmation chez les nerds, qui sont mal à l’aise face aux phénomènes ne relevant pas de la pure logique.

WPCOMMAC Computing Machinery and Intelligence

Computing Machinery and Intelligence, Wikipédia, https://en.wikipedia.org/wiki/Computing_Machinery_and_Intelligence

WPCOMMAC.1 Cf. Computing Machinery and Intelligence, Wikipédia, op. cit. : “Computing Machinery and Intelligence” is a seminal paper written by Alan Turing on the topic of artificial intelligence. The paper, published in 1950 in Mind, was the first to introduce his concept of what is now known as the Turing test to the general public. Turing’s paper considers the question “Can machines think?” Since the words “think” and “machine” cannot be defined in a clear way that satisfies everyone, Turing suggests we “replace the question by another, which is closely related to it and is expressed in relatively unambiguous words.” To do this, he must first find a simple and unambiguous idea to replace the word “think”, second he must explain exactly which “machines” he is considering, and finally, armed with these tools, he formulates a new question, related to the first, that he believes he can answer in the affirmative.

WPCOMMAC.2 Cf. Computing Machinery and Intelligence, Wikipédia, op. cit. : Turing is no longer asking whether a machine can “think”; he is asking whether a machine can act indistinguishably from the way a thinker acts.

WPCOMMAC.3 Cf. Computing Machinery and Intelligence, Wikipédia, op. cit. : Turing also notes that we need to determine which “machines” we wish to consider. He points out that a human clone, while man-made, would not provide a very interesting example. Turing suggested that we should focus on the capabilities of digital machinery – machines which manipulate the binary digits of 1 and 0, rewriting them into memory using simple rules.

WPCOMMAC.4 Cf. Computing Machinery and Intelligence, Wikipédia, op. cit. : according to Ada Lovelace, machines are incapable of independent learning. “The Analytical Engine has no pretensions whatever to originate anything. It can do whatever we know how to order it to perform. It can follow analysis; but it has no power of anticipating any analytical relations or truths.” Turing suggests that Lovelace’s objection can be reduced to the assertion that computers “can never take us by surprise” and argues that, to the contrary, computers could still surprise humans, in particular where the consequences of different facts are not immediately recognizable. Turing also argues that Lady Lovelace was hampered by the context from which she wrote, and if exposed to more contemporary scientific knowledge, it would become evident that the brain’s storage is quite similar to that of a computer.

WPCOMMAC.5 Cf. Computing Machinery and Intelligence, Wikipédia, op. cit. : Modern neurological research has shown that the brain is not digital. Even though neurons fire in an all-or-nothing pulse, both the exact timing of the pulse and the probability of the pulse occurring have analog components. Turing acknowledges this, but argues that any analog system can be simulated to a reasonable degree of accuracy given enough computing power. (Philosopher Hubert Dreyfus would make this argument against “the biological assumption” in 1972.)

WPCOMMAC.6 Cf. Computing Machinery and Intelligence, Wikipédia, op. cit. : An examination of the development in artificial intelligence that has followed reveals that the learning machine did take the abstract path suggested by Turing as in the case of Deep Blue, a chess playing computer developed by IBM and one which defeated the world champion Garry Kasparov (though, this too is controversial) and the numerous computer chess games which can outplay most amateurs. As for the second suggestion Turing makes, it has been likened by some authors as a call to finding a simulacrum of human cognitive development. And such attempts at finding the underlying algorithms by which children learn of the features of the world around them are only beginning to be made.

WPCONNEX Connexionisme

Connexionisme, Wikipédia, https://fr.wikipedia.org/wiki/Connexionnisme.

WPCONNEX.1 Cf. Connexionisme, Wikipédia, op. cit. : Le connexionnisme est une approche utilisée en sciences cognitives, neurosciences, psychologie et philosophie de l’esprit. Le connexionnisme modélise les phénomènes mentaux ou comportementaux comme des processus émergents de réseaux d’unités simples interconnectées. Le plus souvent les connexionnistes modélisent ces phénomènes à l’aide de réseaux de neurones. Il s’agit d’une théorie qui a émergé à la fin des années 1980 en tant qu’alternative au computationnalisme (Putnam, Fodor, etc.) alors dominant.

WPCONNEX.2 Cf. Connexionisme, Wikipédia, op. cit. : Le principe de base du connexionnisme est que les phénomènes mentaux peuvent être décrits à l’aide de réseaux d’unités simples interconnectées. La forme des connexions et des unités peut varier selon les modèles. Par exemple, les unités d’un réseau peuvent représenter des neurones et les connexions peuvent représenter des synapses. Un autre type de modèle pourrait faire que chaque unité du réseau soit un mot et que chaque connexion soit un indicateur de la similarité sémantique.

WPCURHOW Correspondance de Curry-Howard

Correspondance de Curry-Howard, Wikipédia, https://fr.wikipedia.org/wiki/Correspondance_de_Curry-Howard.

WPCURHOW.1 Cf. Correspondance de Curry-Howard, Wikipédia, op. cit. : La correspondance de Curry-Howard, appelée également isomorphisme de Curry-de Bruijn-Howard, correspondance preuve/programme ou correspondance formule/type, est une série de résultats à la frontière entre la logique mathématique, l’informatique théorique et la théorie de la calculabilité. Ils établissent des relations entre les démonstrations formelles d’un système logique et les programmes d’un modèle de calcul.

WPCURHOW.2 Cf. Correspondance de Curry-Howard, Wikipédia, op. cit. : La correspondance de Curry-Howard a joué un rôle important en logique, car elle a établi un pont entre théorie de la démonstration et informatique théorique.

WPCRIFON Crise des fondements

Crise des fondements, Wikipédia, https://fr.wikipedia.org/wiki/Crise_des_fondements.

WPCRIFON.1 Cf. Crise des fondements, Wikipédia, op. cit. : En mathématiques, la crise des fondements, aiguë au tournant du XXe siècle, est la situation où des solutions concurrentes sont proposées pour asseoir la méthodologie des mathématiques sur une base rigoureuse.

WPCRIFON.2 Cf. Crise des fondements, Wikipédia, op. cit. : En 1879, Frege clarifie le raisonnement logique. Cette formalisation permet de dégager les trois caractéristiques qu’une théorie mathématique devrait avoir : cohérence : impossibilité de démontrer une proposition et son contraire ; complétude : pour tout énoncé, ou bien il est démontrable, ou bien son opposé est démontrable à l’intérieur de la théorie ; décidabilité : il existe une procédure de décision permettant de tester tout énoncé de la théorie. Avec Georg Cantor, la théorie des ensembles met à l’avant-plan les ensembles infinis, objets aux propriétés particulières qui demandent une nouvelle approche.

WPCRIFON.3 Cf. Crise des fondements, Wikipédia, op. cit. : Vers la fin du XIXe siècle et au début du XXe siècle, plusieurs mathématiciens ont tenté de construire les mathématiques sur des bases solides : Frege, Ernst Zermelo, David Hilbert et Bertrand Russell, entre autres. Cette construction était rendue nécessaire après la découverte de problèmes dans la théorie des ensembles permettant des paradoxes comme le paradoxe de Russell, qui compromettaient la cohérence même des mathématiques et la laissant sous la menace du principe d’explosion. La capacité des mathématiques à représenter le monde par exemple au travers des Sciences physiques était alors sérieusement en danger: de tels paradoxes ne permettaient plus aucune prédiction par le calcul de l’évolution d’un système physique, puisque n’importe quel calcul contradictoire et incompatible devenait possible. David Hilbert (1899) rafraîchit la géométrie euclidienne, alors que les géométries non-euclidiennes sont explorées. Surtout, il propose en 1898 de réduire l’arithmétique à la logique. Son but est de montrer que les nombres sont des objets qui se déduisent d’un système d’axiomes non-contradictoires. Il précise son projet en 1922 en posant l’Entscheidungsproblem (problème de la décision). Il demande s’il existe une procédure (un algorithme) permettant de vérifier si une expression formelle peut se déduire d’un système d’axiomes donnés. Cela aboutit en 1928 à un programme de recherche qui s’articule autour de trois questions : les mathématiques sont-elles complètes, cohérentes, et décidables ? Trois écoles se forment au début du XXe siècle pour tenter de formaliser la logique et la métamathématique : logiciste : menée par Russell et Whitehead (à partir de 1903) ; formaliste : menée par David Hilbert (1904-) ; intuitionniste : menée par Brouwer (1907-). Russell et Whitehead, s’appuyant sur la logique et plusieurs axiomes, tentent de construire de façon cohérente les mathématiques. Leur travail, complexe et incomplet, culmine avec Principia Mathematica (1910-1913). L’école formaliste voit les mathématiques comme le résultat de définitions et d’axiomes qui permettent de les construire de façon quasi-mécanique. Finalement, l’école intuitionniste remet en cause certaines méthodes de la logique classique. Parmi les systèmes proposés, la théorie ZFC, chronologiquement une des premières, reste la plus prisée au XXIe siècle. Kurt Gödel avec ses théorèmes d’incomplétude (1931) a démontré que dès qu’une théorie est assez riche pour rendre compte de l’arithmétique, elle ne peut à la fois être complète, décidable et démontrablement cohérente.

WPCYBERN Cybernétique

Cybernétique, Wikipédia, https://fr.wikipedia.org/wiki/Cybern%C3%A9tique.

WPCYBERN.1 Cf. Cybernétique, Wikipédia, op. cit. : La cybernétique est l’étude des mécanismes d’information des systèmes complexes, explorés en vue d’être standardisés lors des conférences Macy et décrits en 1947 par Norbert Wiener dans ce but. […] Les contours parfois flous de cet ensemble de recherches s’articulent toutefois autour du concept clé de rétroaction (en anglais feedback) ou mécanisme téléologique. Leur but était de donner une vision unifiée des domaines naissants de l’automatique, de l’électronique et de la théorie mathématique de l’information, en tant que “théorie entière de la commande et de la communication, aussi bien chez l’animal que dans la machine”. […] L’ambition développée par la cybernétique a pourtant constitué un creuset formidable pour l’élaboration des sciences cognitives, de l’intelligence artificielle, des thérapies systémiques de l’école de Palo Alto, ou encore des théories biologiques de l’auto-organisation.

WPCYBERN.2 Cf. Cybernétique, Wikipédia, op. cit. : La thermodynamique, souvent citée en référence par Wiener, est probablement la science préexistante qui s’apparente le plus à la cybernétique. On citera en particulier Rudolf Clausius qui développe le concept d’entropie de 1850 à 1865. En 1894, Ludwig Boltzmann fait le lien entre l’entropie et l’information en remarquant que l’entropie est liée à de l’information à laquelle on n’a pas accès.

WPCYBERN.3 Cf. Cybernétique, Wikipédia, op. cit. : La pensée atomiste, fille du structuralisme, va aussi faire son chemin dans le domaine des sciences et contribuer aux progrès de schématisation (réduction) de la diversité du monde à la combinatoire d’éléments simples, plus faciles à appréhender par les systèmes informatiques. On peut citer parmi les travaux importants le théorème d’incomplétude de Kurt Gödel (1931) et les travaux sur la Machine de Turing d’Alan Turing (1936).

WPCYBERN.4 Cf. Cybernétique, Wikipédia, op. cit. : La cybernétique est aussi une suite de la phénoménologie, en tant qu’elle ausculte les phénomènes pour en saisir l’autonomie et la particularité, notamment par la forme pour ensuite passer à un autre type d’analyse : modélisation, mécanique…

WPCYBERN.5 Cf. Cybernétique, Wikipédia, op. cit. : La première cybernétique s’établit dans le cadre des conférences Macy qui réunissent entre 1942 et 1953 un groupe interdisciplinaire de mathématiciens, logiciens, anthropologues, psychologues et économistes qui s’étaient donné pour objectif d’édifier une science générale du fonctionnement de l’esprit. Parmi les participants les plus illustres, on trouve le neurophysiologiste Arturo Rosenblueth, les mathématiciens John von Neumann et Norbert Wiener, l’ingénieur Julian Bigelow le neurophysiologiste Warren McCulloch, le logicien Walter Pitts, le psychanalyste Lawrence Kubie et les anthropologues Gregory Bateson et Margaret Mead. Ce qui rapproche les différents participants est leur intérêt commun pour les mécanismes de causalité circulaire (notamment le concept de feedback) qu’ils étudient dans leurs disciplines respectives.

WPCYBERN.6 Cf. Cybernétique, Wikipédia, op. cit. : En 1948, Wiener définit la cybernétique comme une science qui étudie exclusivement les communications et leurs régulations dans les systèmes naturels et artificiels.

WPCYBERN.7 Cf. Cybernétique, Wikipédia, op. cit. : À partir de 1949, un autre groupe interdisciplinaire, le Ratio Club, commence une série de rencontres informelles pour discuter de sujets ayant trait à la cybernétique. On compte parmi eux W. Ross Ashby, William Grey Walter, Alan Turing et Georges R. Boulanger, mathématicien qui fut président de l’Association internationale de cybernétique.

WPCYBERN.8 Cf. Cybernétique, Wikipédia, op. cit. : La cybernétique désigne d’abord un moyen de connaissance, qui étudie l’information au sens de la physique, dans la définition qu’en donne Norbert Wiener : “De même que l’entropie est une mesure de désorganisation, l’information fournie par une série de messages est une mesure d’organisation”. Dans cette acception première, la cybernétique est une approche phénoménologique qui étudie l’information, sa structure et sa fonction dans les interactions systémiques. Ce qui peut être traduit par la science générale de la régulation et des communications dans les systèmes naturels et artificiels. La cybernétique décrite par Norbert Wiener est un moyen d’expliquer et de comprendre tous les mécanismes rencontrés avec quelques briques logiques simples : La boîte noire : un élément relié à d’autres, dont on ne se soucie pas de savoir ce qu’il contient (ou son fonctionnement d’après sa structure interne, inaccessible de façon momentanée ou définitive), mais dont on déduit la fonction apparente à partir de l’étude de ses entrées/sorties. L’émetteur, qui agit sur l’environnement, donc envoie de l’information, sorte de porte de sortie. Le récepteur, qui en intègre depuis l’environnement, donc capte les informations, comme une porte d’entrée de la boîte noire. Le flux d’information : ce qui est transmis, donc envoyé et effectivement reçu, autrement dit l’information efficace. La rétroaction (feedback) : c’est l’information en retour de l’état. Le feedback est mis en évidence par cette approche car il est indispensable pour concevoir une logique d’autorégulation. On voit donc émerger des boucles de rétroaction, mécanismes circulaires qui mettent en évidence des systèmes. Si les systèmes sont mis en évidence par cette cybernétique (parfois dite du premier ordre), ils ne le sont d’abord que par voie de conséquence d’une étude strictement limitée aux échanges d’information et à l’évolution de ces échanges dans le temps. Plus tard se constituera un paradigme propre à l’étude des systèmes en tant que tels, la systémique. Portés par les participants du mouvement cybernétique, pour la plupart des auteurs majeurs dans leur discipline, les concepts de la cybernétique se diffusent rapidement. La cybernétique marque le moment d’une rupture épistémologique majeure qui a profondément influencé tous les domaines de la science et ses retombées sont innombrables.

WPCYBERN.9 Cf. Cybernétique, Wikipédia, op. cit. : Marvin Minsky présente la première cybernétique comme un tronc commun qui se serait divisé en trois branches : la “simulation cognitive” à la Allen Newell et Herbert Simon, l’“intelligence artificielle” et la “seconde cybernétique” ou théorie des systèmes auto-organisateurs. […] Alors que la première cybernétique étudie comment les systèmes maintiennent l’homéostasie (morphostase) par des mécanismes d’autorégulation, la “deuxième cybernétique” du psychiatre W. Ross Ashby et des biologistes Humberto Maturana et Francisco Varela étudie comment les systèmes évoluent et créent des nouvelles structures (morphogenèse). Ashby parle d’auto-organisation, Maturana et Varela d’autopoïèse. Cette étude des systèmes éloignés de leur point d’équilibre se rapproche des travaux sur les structures dissipatives du prix Nobel de chimie belge Ilya Prigogine. Au lieu de se demander comment se maintient un certain équilibre, on observe comment un nouvel équilibre peut émerger d’une situation de déséquilibre. Prigogine a montré que contrairement à ce que l’on croyait, dans certaines conditions, en s’éloignant de son point d’équilibre, le système ne va pas vers sa mort ou son éclatement mais vers la création d’un nouvel ordre, d’un nouvel état d’équilibre. Les situations extrêmes recèlent la possibilité de créer une nouvelle structure. On voit ici la possibilité de recréer du vivant, de l’organiser là où il n’y avait plus que du chaos. […] La cybernétique de deuxième ordre vise à l’élaboration d’une méthode de description “universelle” commune aux différents champs de la science. […] Pour W. Ross Ashby, “la cybernétique se situe comme une approche indépendante de la nature des éléments qu’elle étudie”.

WPCYBERN.10 Cf. Cybernétique, Wikipédia, op. cit. : Pourtant, au-delà des querelles d’école entre la cybernétique et la systémique issue des travaux de Ludwig von Bertalanffy, on peut, à la suite de Gregory Bateson, considérer ces deux mouvements de pensée comme faisant partie d’un ensemble d’idées relativement unifié. Ainsi, avec l’assimilation des théories cybernétiques par la systémique, on a été amené à comprendre les mécanismes d’autorégulation des systèmes comme des processus de feedback négatif visant à empêcher une déviation. Les systèmes cybernétiques visent à maintenir un état stable viable d’interaction au sein d’environnements changeants via un processus stochastique d’essais et erreurs.

WPCYBERN.11 Cf. Cybernétique, Wikipédia, op. cit. : Dans son champ d’application, la cybernétique peut signifier le moyen d’organiser les échanges pour les rendre efficaces, et poussée à l’extrême le moyen de contrôler plus efficacement.

WPDECIDA Décidabilité

Décidabilité, Wikipédia, https://fr.wikipedia.org/wiki/D%C3%A9cidabilit%C3%A9.

WPDECIDA.1 Cf. Décidabilité, Wikipédia, op. cit. : En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique. L’indécidabilité est la négation de la décidabilité. Dans les deux cas, il s’agit de formaliser l’idée qu’on ne peut pas toujours conclure lorsque l’on se pose une question, même si celle-ci est sous forme logique.

WPDECIDA.2 Cf. Décidabilité, Wikipédia, op. cit. : Une proposition (on dit aussi énoncé) est 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 de cette théorie. Pour distinguer cette notion d’indécidabilité de la notion d’indécidabilité algorithmique (voir ci-dessous), on dit aussi que l’énoncé est indépendant du système d’axiomes.

WPDECIDA.3 Cf. Décidabilité, Wikipédia, op. cit. : En logique classique, d’après le théorème de complétude, une proposition est indécidable dans une théorie s’il existe des modèles de la théorie où la proposition est fausse et des modèles où elle est vraie. On utilise souvent des modèles pour montrer qu’un énoncé est indépendant d’un système d’axiomes (dans ce cadre, on préfère employer indépendant plutôt qu’indécidable). La propriété utilisée dans ce cas n’est pas le théorème de complétude mais sa réciproque, très immédiate, appelée théorème de correction.

WPDECIDA.4 Cf. Décidabilité, Wikipédia, op. cit. : Une théorie mathématique pour laquelle tout énoncé est décidable est dite complète, sinon elle est dite incomplète.

WPDECIDA.5 Cf. Décidabilité, Wikipédia, op. cit. : Le théorème d’incomplétude de Gödel nous garantit que toute théorie axiomatique cohérente, et suffisamment puissante pour représenter l’arithmétique de Peano (l’arithmétique usuelle), est incomplète, pourvu qu’elle soit axiomatisée de façon que l’on puisse décider, au sens algorithmique (voir ci-dessous), si un énoncé est ou non un axiome.

WPDECIDA.6 Cf. Décidabilité, Wikipédia, op. cit. : Un problème de décision est dit décidable s’il existe un algorithme, une procédure mécanique qui se 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. Par exemple, le problème de l’arrêt est indécidable. On peut formaliser la notion de fonction calculable par algorithme, ou par procédure mécanique, de diverses façons, par exemple en utilisant les machines de Turing.

WPDEMMAX Démon de Maxwell

Démon de Maxwell, Wikipédia, https://fr.wikipedia.org/wiki/D%C3%A9mon_de_Maxwell.

WPDEMMAX.1 Cf. Démon de Maxwell, Wikipédia, op. cit. : Le démon de Maxwell est une expérience de pensée imaginée par James Clerk Maxwell en 1867, pour suggérer que la seconde loi de la thermodynamique n’est vraie que de manière statistique. Cette loi établit l’irréversibilité de phénomènes de physique statistique et notamment des transferts thermiques, se traduisant par une augmentation continue de l’entropie. Par exemple, si on laisse ouverte la porte d’un réfrigérateur éteint, la température du réfrigérateur et de la pièce vont s’équilibrer, et cela de manière irréversible sans apport d’énergie. Or, l’expérience du démon de Maxwell propose un processus permettant de revenir à un état de température inégal, sans dépenser d’énergie, et en diminuant l’entropie, ce qui est en principe impossible selon la seconde loi de la thermodynamique. Ce paradoxe a suscité, et suscite encore, un grand nombre d’études et de débats depuis son énoncé en 1871. Pendant soixante-deux ans, son étude n’a pas tellement progressé, jusqu’à ce que Leó Szilárd propose en 1929 un modèle physique du démon de Maxwell permettant d’étudier précisément et formellement le processus. Vingt ans plus tard, en 1949, Léon Brillouin propose une solution du paradoxe mettant l’accent sur la nécessité pour le démon d’acquérir de l’information, et mettant en évidence que cette acquisition augmente l’entropie du système et sauve la seconde loi. Après avoir été adoptée par la plus grande partie de la communauté scientifique, cette solution a de plus en plus été remise en question, notamment par l’établissement de modèles de "démons" automatiques, où l’acquisition d’information ne joue pas un rôle déterminant. Le lien fait par Brillouin entre l’entropie et la théorie de l’information a également été critiqué. Un nouveau tournant a lieu en 1961, quand Rolf Landauer – suivi de Charles Bennett – met en évidence l’importance de la mémorisation de l’information et surtout de la nécessité d’effacer cette mémoire pour réaliser un cycle thermodynamique complet. L’effacement de la mémoire ayant un coût en entropie, cela rétablit le second principe de la thermodynamique. Des études plus modernes mettant en jeu des versions quantiques du démon de Maxwell, effectuées notamment par Wojciech Hubert Zurek dans les années 1980 confirment le principe de Landauer. Toutefois, de nouveaux modèles d’expériences de pensée remettant en cause le second principe continuent à être proposés dans les années 2000, soit ne nécessitant pas d’effacement d’information, soit n’utilisant pas du tout le concept d’information, ni même de démon, mais tirant parti de conditions spécifiques comme des géométries non euclidiennes, l’intrication quantique ou des champs de force.

WPFONMAT Fondements des mathématiques

Fondements des mathématiques, Wikipédia, https://fr.wikipedia.org/wiki/Fondements_des_math%C3%A9matiques.

WPFONMAT.1 Cf. Fondements des mathématiques, Wikipédia, op. cit. : Les fondements des mathématiques sont les principes sur lesquels est établie cette science.

WPFONMAT.2 Cf. Fondements des mathématiques, Wikipédia, op. cit. : Le logicisme a été prôné notamment par Gottlob Frege et Bertrand Russell. La mathématique pure présente deux caractéristiques : la généralité de son discours – la considération des particuliers existants est exclue – et la déductibilité du discours mathématique – les inférences qui structurent le discours mathématique sont des implications formelles (elles affirment non pas les propositions elles-mêmes, mais la nécessité de leur connexion). En ce que le discours mathématique ne prétend qu’à une vérité formelle, il est possible de réduire les mathématiques à la logique, les lois logiques étant les lois du “vrai”. […] Le logicisme a rencontré néanmoins, à ses débuts, de réelles difficultés en tant qu’il s’engage ontologiquement par rapport aux classes. La théorie des classes avait conduit à des paradoxes logiques maintenant résolus mais qui avaient mis au jour la nécessité de clarifier les axiomes.

WPFONMAT.3 Cf. Fondements des mathématiques, Wikipédia, op. cit. : Le formalisme soutenu par David Hilbert : les mathématiques se présentent comme une pure construction de l’esprit. La tâche des mathématiciens est de déduire des théorèmes à partir d’axiomes qui ne sont ni vrais ni faux. La validité ne repose plus que sur la structure des énoncés, et non sur la nature de ce dont ils parlent. La vérité des mathématiques est réduite à leur cohérence interne, la non-contradiction des propositions. Le débat sur cette conception formaliste a été relancé par le théorème d’incomplétude de Gödel qui affirme que tout système formel cohérent et récursif contenant l’arithmétique, possède une proposition qui n’est ni démontrable, ni réfutable ; de plus, cette proposition est cependant “vraie” au sens intuitif du terme : elle formalise en effet l’affirmation selon laquelle la théorie est cohérente, ce qu’on a supposé dès le départ.

WPFONMAT.4 Cf. Fondements des mathématiques, Wikipédia, op. cit. : L’intuitionnisme défendu de manière paradigmatique par Brouwer : les mathématiques ont un fondement intuitif, c’est-à-dire que tous les objets des mathématiques sont des constructions de l’esprit humain. Selon la conception intuitionniste un nombre réel peut être représenté comme une suite infinie de décimales à condition de disposer d’un algorithme qui peut calculer chacune de ces décimales. Cette position a des conséquences importantes notamment sur le plan logique : en logique intuitionniste, on ne peut pas éliminer la double négation (ce que fait la logique classique) : “non non p” ne se réduit pas à “p” ; sinon on pourrait démontrer l’existence d’objets sans pour autant construire ceux-ci. Il s’en suit que “non p ou p” n’est pas un théorème. Brouwer concevait l’intuitionnisme comme un positionnement philosophique sur les mathématiques et a accueilli avec scepticisme sa formalisation donnée ultérieurement par Arend Heyting.

WPFONMAT.5 Cf. Fondements des mathématiques, Wikipédia, op. cit. : L’œuvre de Hilbert est très représentative de la crise des fondements qui s’est produite en mathématiques pendant le XIXe et au début du XXe siècle. Hilbert, comme d’autres logiciens et mathématiciens de son temps, s’est rendu compte que la géométrie euclidienne était incomplète, pas au sens où l’axiome des parallèles n’y est pas déductible, mais parce que tous les géomètres depuis Euclide se servent dans leurs preuves d’axiomes qui n’avaient jamais été explicités. À la suite des travaux de Pasch, Hilbert a donné une formulation presque complète de la géométrie euclidienne, dans son livre Les Fondements de la géométrie, pour laquelle aucun axiome géométrique n’était laissé dans l’ombre. Ce programme de fondation de la géométrie n’était cependant pas achevé pour deux raisons. D’une part, les règles de raisonnement admises étaient encore laissées dans l’ombre. D’autre part, un des axiomes de la géométrie, relatif à la continuité de l’espace, posait des problèmes d’interprétation associés à ceux de la définition des nombres réels et de la théorie des ensembles de Cantor.

WPFONMAT.6 Cf. Fondements des mathématiques, Wikipédia, op. cit. : L’analyse, que l’on peut aussi appeler calcul infinitésimal, ou calcul différentiel et intégral, repose maintenant sur la définition de l’ensemble des nombres réels. Depuis les découvertes de Newton et Leibniz, il avait fallu sortir du cadre des Éléments d’Euclide. Les mathématiciens du XIXe siècle, notamment Cauchy et Weierstrass, pour l’analyse proprement dite, puis Dedekind et Cantor ont donné une formulation précise de principes qui permettent de raisonner avec rigueur et exactitude sur les nombres réels. Ceux-ci sont définis par Dedekind comme des couples d’ensembles de nombres rationnels, les coupures de Dedekind. Peano a donné des axiomes et des méthodes formelles pour développer d’une façon logiquement rigoureuse l’arithmétique et celle-ci suffit pour fonder la théorie des nombres rationnels. La théorie des ensembles de Cantor, qui n’était pas vraiment formalisée, semblait cependant le cadre idéal, paradisiaque selon l’expression de Hilbert, pour fonder l’analyse et plus généralement les mathématiques. Frege, de son côté avait donné des règles formelles précises et explicites pour une théorie logique qui devait permettre de fonder les mathématiques. On pouvait espérer une base solide. Mais cette base n’a pas tardé à montrer ses faiblesses. La découverte du paradoxe de Burali-Forti (l’ensemble de tous les ordinaux est bien ordonné, ce bon ordre est supérieur à tous les ordinaux, donc à son propre ordinal), puis celle du paradoxe de Russell, proche sur le principe mais nettement plus simple (l’ensemble des ensembles qui n’appartiennent pas à eux-mêmes est un ensemble, il ne peut ni s’appartenir, ni ne pas s’appartenir à lui-même), montrent l’incohérence de ces deux théories. (Russell a donné son paradoxe initialement pour la théorie de Frege). Des solutions pour éviter ces paradoxes furent rapidement trouvées. L’une, initiée par Russell, et développée dans les Principia Mathematica, stratifie les prédicats grâce à la notion de type : on ne peut plus écrire qu’un ensemble n’appartient pas à lui-même. L’autre, initiée par Zermelo, restreint la définition des ensembles par compréhension, c’est-à-dire par une propriété de ses éléments : la propriété de ne pas appartenir à soi-même ne définit plus un ensemble. Mais pouvait-on s’assurer que l’on ne puisse pas dériver de nouveaux paradoxes dans ces théories ?

WPFONMAT.7 Cf. Fondements des mathématiques, Wikipédia, op. cit. : Pour répondre à la crise des fondements des mathématiques, David Hilbert avait conçu un programme dont il établit les prémisses en 1900 dans l’introduction à sa célèbre liste de problèmes, le second problème étant justement celui de la cohérence de l’arithmétique. Il développe ce programme avec ses collaborateurs, parmi lesquels Paul Bernays et Wilhelm Ackermann, essentiellement dans les années 1920. L’idée est grossièrement la suivante. Tant que l’on manipule le fini, les mathématiques sont sûres. L’arithmétique élémentaire (en un sens qui doit se préciser) est sûre. Pour justifier l’utilisation d’objets abstraits ou idéaux, en particulier infinis, il suffit de montrer que la théorie qui les utilise est cohérente, mais bien sûr cette cohérence doit elle-même être démontrée par des moyens finitaires. On peut alors affirmer l’existence de ces objets. C’est la position formaliste (à ne pas confondre avec le finitisme qui considère que seules les constructions directement finitaires ont un sens). Le système dans lequel on pourrait formaliser les mathématiques finitaires n’est pas clair. À l’époque, il semble que Hilbert pensait, sans l’avoir explicitement formalisé, à un système plus faible que l’arithmétique de Peano, l’arithmétique primitive récursive : toutes les définitions de fonctions récursives primitives sont dans le langage, la récurrence est restreinte aux formules sans quantificateurs (disons aux égalités pour faire simple), donc très immédiate. Peu importe en fait : le second théorème d’incomplétude de Gödel, montre que l’on ne pourra même pas prouver dans la théorie arithmétique en question sa propre cohérence, et donc certainement pas celle de théories plus fortes qui assureraient la fondation des mathématiques. Le programme de Hilbert n’est donc pas réalisable, en tout cas pas sans une révision drastique. Des logiciens comme Gentzen, et Gödel lui-même, ont pensé à rétablir ce programme en étendant la notion de méthodes finitaires, celles-ci ne pouvant cependant pas être définies une fois pour toutes par une théorie toujours à cause du second théorème d’incomplétude. Ainsi, Gentzen a donné en 1936 une preuve de cohérence de l’arithmétique de Peano dans un système forcément plus fort, où l’on raisonne par induction sur un ordre bien fondé (dénombrable mais plus grand que l’ordre des entiers), mais où l’induction est cependant restreinte à des formules sans quantificateurs, donc plus “immédiate”. Si l’intérêt mathématique des méthodes mises en œuvre par Gentzen ne fait aucun doute, l’interprétation de ses preuves de cohérence, en tant que preuves “absolues” (ce sont bien sûr indubitablement des preuves de cohérence relative) reste très discutable. Il reste que, malgré son échec, le programme de Hilbert a joué un rôle décisif dans le développement de la logique mathématique moderne.

WPFONMAT.8 Cf. Fondements des mathématiques, Wikipédia, op. cit. : mathématiques actuelles sont basées sur la notion d’ensemble. En fait, tout objet mathématique ou presque peut être défini comme un ensemble. […] Avec de telles définitions, ou d’autres semblables, toutes les connaissances mathématiques peuvent être prouvées à l’intérieur d’une théorie des ensembles. Leurs axiomes peuvent être considérés comme les principaux fondements des mathématiques (avec les règles de déduction du calcul des prédicats au premier ordre).

WPFONMAT.9 Cf. Fondements des mathématiques, Wikipédia, op. cit. : La théorie axiomatique des ensembles “standard” comporte neuf axiomes. Ces axiomes ont été énoncés par Zermelo (1908) et complétés dans les années 1920 par Fraenkel et Skolem. Ils sont dits de Zermelo-Fraenkel et comprennent l’axiome du choix, d’où le sigle ZFC souvent employé pour désigner cette théorie. L’œuvre de l’association Bourbaki a été développée dans ce cadre axiomatique.

WPFONMAT.10 Cf. Fondements des mathématiques, Wikipédia, op. cit. : La théorie des classes, de von Neumann, Gödel et Bernays (NGB). C’est une extension de ZFC qui lui est presque équivalente. Tous les théorèmes de ZFC sont des théorèmes de NGB. Inversement, tous les théorèmes de NGB qui ne mentionnent que les notions fondamentales de ZFC (c’est-à-dire les ensembles et non les classes) sont des théorèmes de ZFC. NGB convient mieux que ZFC pour formuler la théorie des catégories.

WPFONMAT.11 Cf. Fondements des mathématiques, Wikipédia, op. cit. : Parmi les mathématiciens, certains se contentent des axiomes ZF, et refusent l’axiome du choix (C), car ils considèrent que certaines de ses implications sont contre-intuitives. Certains mathématiciens refusent même ZF et la logique classique qui en est la base, car ils considèrent que tout doit être construit explicitement ; c’est la raison pour laquelle on les appelle constructivistes ou intuitionnistes.

WPFONMAT.12 Cf. Fondements des mathématiques, Wikipédia, op. cit. : La théorie des types de Whitehead et Russell, exposée principalement dans les Principia Mathematica. Son formalisme est lourd (des dizaines de pages pour prouver des propositions qui peuvent paraître évidentes) et ses principes imposent beaucoup d’interdits entre les divers types dans le souci de ne pas reproduire l’équivalent du paradoxe de Russell. Outre sa grande importance historique parce qu’elle est la première formulation axiomatique, rigoureuse et cohérente des principes généraux des mathématiques, elle a, grâce à l’informatique, repris de la vigueur à la fin du siècle précédent et au début de celui-ci et devient une discipline phare de la logique mathématique contemporaine.

WPGEPOSO General Problem Solver

General Problem Solver, Wikipédia, https://fr.wikipedia.org/wiki/General_Problem_Solver.

WPGEPOSO.1 Cf. General Problem Solver, Wikipédia, op. cit. : Le General Problem Solver (GPS) est un programme informatique créé en 1959 par Herbert Simon, Cliff Shaw et Allen Newell dans le but de construire un solveur de problèmes universel. N’importe quel problème formalisé peut en principe être résolu par GPS, par exemple des preuves de théorèmes, des problèmes géométriques et des parties d’échecs. GPS était le premier programme à séparer sa base de données (tables) de sa stratégie de résolution de problèmes. GPS est implémenté dans le langage informatique IPL.

WPINFORM Informatique

Informatique, Wikipédia, https://fr.wikipedia.org/wiki/Informatique.

WPINFORM.1 Cf. Informatique, Wikipédia, op. cit. : L’informatique est un domaine d’activité scientifique, technique et industriel concernant le traitement automatique de l’information par l’exécution de programmes informatiques par des machines : des systèmes embarqués, des ordinateurs, des robots, des automates, etc.

WPINFORM.2 Cf. Informatique, Wikipédia, op. cit. : Le terme “informatique” résulte de l’association du terme “information” au suffixe “-ique” signifiant “qui est propre à”. Comme adjectif, il s’applique à l’ensemble des traitements liés à l’emploi des ordinateurs et systèmes numériques. Comme substantif, il désigne les activités liées à la conception et à la mise en œuvre de ces machines. Des questions de télécommunications comme le traitement du signal ou la théorie de l’information, aussi bien que des problèmes mathématiques comme la calculabilité s’y rattachent.

WPINFORM.3 Cf. Informatique, Wikipédia, op. cit. : Pour Donald Knuth, cependant, les Américains ont délibérément écarté le mot informatique, non pour un problème de marque mais pour des raisons sémantiques ; les ordinateurs ne traitent pas de l’information, mais des données, dont le sens informatif est parfaitement indifférent. En 1966, l’Académie française consacre l’usage officiel du mot pour désigner la “science du traitement de l’information”.

WPINFORM.4 Cf. Informatique, Wikipédia, op. cit. : Dans l’usage contemporain, le substantif “informatique” devient un mot polysémique qui désigne autant le domaine industriel en rapport avec l’ordinateur (au sens de calculateur fonctionnant avec des algorithmes), que la science du traitement des informations par des algorithmes. Les expressions “science informatique”, “informatique fondamentale” ou “informatique théorique” désignent sans ambiguïté la science, tandis que “technologies de l’information” ou “technologies de l’information et de la communication” désignent le secteur industriel et ses produits.

WPINFORM.5 Cf. Informatique, Wikipédia, op. cit. : L’amélioration de l’expressivité des langages de programmation a permis la mise en œuvre d’algorithmes toujours plus sophistiqués, appliqués à des données de plus en plus variées. La miniaturisation des composants et la réduction des coûts de production, associées à une augmentation de la demande en traitements des informations de toutes sortes (scientifiques, financières, commerciales, etc.), ont eu pour conséquence une diffusion de l’informatique dans tous les secteurs économiques, ainsi que dans la vie quotidienne des individus.

WPINFORM.6 Cf. Informatique, Wikipédia, op. cit. : Le terme technologies de l’information et de la communication désigne un secteur d’activité et un ensemble de biens qui sont des applications pratiques des connaissances scientifiques en informatique ainsi qu’en électronique numérique, en télécommunication, en sciences de l’information et de la communication et en cryptologie.

WPINFORM.7 Cf. Informatique, Wikipédia, op. cit. : Les appareils en électronique numérique utilisent tous un système logique. Les entrées et sorties des composants électroniques n’ont que deux états ; l’un correspondant à vrai, l’autre à faux. On démontre qu’en assimilant vrai au nombre 1 et faux au nombre 0, on peut établir les règles logiques qui fondent un système de numération binaire. Les appareils représentent toute l’information sous cette forme. Les appareils informatiques se décomposent en quatre ensembles qui servent respectivement à entrer des données, les stocker, les traiter, puis, les faire ressortir de l’appareil, selon les principes de la machine de Turing et l’architecture de von Neumann. Les données circulent entre les pièces des différentes unités par des lignes de communication, les bus. Le processeur est la pièce centrale qui anime l’appareil en suivant les instructions des programmes qui sont enregistrés à l’intérieur.

WPINFTHE Informatique théorique

Informatique théorique, Wikipédia, https://fr.wikipedia.org/wiki/Informatique_th%C3%A9orique.

WPINFTHE.1 Cf. Informatique théorique, Wikipédia, op. cit. : L’informatique théorique est l’étude des fondements logiques et mathématiques de l’informatique. C’est une branche de la science informatique. Plus généralement, le terme est utilisé pour désigner des domaines ou sous-domaines de recherche centrés sur des vérités universelles (axiomes) en rapport avec l’informatique. L’informatique théorique se caractérise par une approche par nature plus mathématique et moins empirique de l’informatique et ses objectifs ne sont pas toujours directement reliés à des enjeux technologiques. De nombreuses disciplines peuvent être regroupées sous cette dénomination diffuse dont la théorie de la calculabilité, l’algorithmique et la théorie de la complexité, la théorie de l’information, l’étude de la sémantique des langages de programmation, la logique mathématique, la théorie des automates et des langages formels.

WPINFTHE.2 Cf. Informatique théorique, Wikipédia, op. cit. : Les logiciens Bertrand Russel, David Hilbert et George Boole furent des précurseurs de l’informatique théorique. Mais cette branche de l’informatique a surtout vu le jour à partir des travaux d’Alan Turing et Alonzo Church en 1936, qui ont introduit les modèles formels de calculs (les machines de Turing et le lambda calcul). Ils ont montré l’existence de machines universelles capables de simuler toutes les machines du même type, par exemple les machines de Turing universelles. En 1938, Claude Shannon montre que l’algèbre booléenne explique le comportement des circuits avec des relais électromécaniques. En 1948, Claude Shannon publie A Mathematical Theory of Communication, fondateur de la théorie de l’information. En 1949, il annonce les fondements de la théorie de la complexité des circuits.

WPINFTHE.3 Cf. Informatique théorique, Wikipédia, op. cit. : La théorie des langages et des automates est un sujet important dans les années 1950, car il permet de comprendre l’expressivité des langages. Les machines à états finis et les automates à pile ont été définis. Michael Oser Rabin et Dana Stewart Scott ont étudié le pouvoir expressif et les limites de ces modèles.

WPINFTHE.4 Cf. Informatique théorique, Wikipédia, op. cit. : En 1964, Noam Chomsky définit la hiérarchie de Chomsky. Plusieurs classes de langages (langages rationnels, langages algébriques, langages avec contextes, langages récursivement énumérables) correspondent à des types de machines théoriques différentes (automates finis, automates à pile, machine de Turing à mémoire linéaire, machine de Turing). Pleins de variantes de ces classes de langages et machines sont étudiés. Hartmanis, Lewis et Stearns et d’autres classifient les langages selon le temps et/ou la mémoire qu’il faut pour les calculer. Ce sont les balbutiements de la théorie de la complexité.

WPINFTHE.5 Cf. Informatique théorique, Wikipédia, op. cit. : Durant les années 1970, la théorie de la complexité se développe. Les classes de complexité P et NP sont définis ; la NP-complétude est définie indépendamment par Stephen Cook et Leonid Levin. Richard Karp a démontré l’importance des langages NP-complets. La question P = NP est posée et les chercheurs conjecturaient que l’on pourrait la résoudre via la correspondance entre machines de Turing et circuits. Se développent aussi les méthodes formelles pour vérifier les programmes. On définit des sémantiques formelles aux langages de programmation. Se développement aussi des connections entre le modèle de base de données relationnelles et le calcul des relations, afin de réaliser des requêtes dans des bases de données de manière efficace. Ces années ont été florissantes également en algorithmique. Donald Knuth a beaucoup influencé le développement de l’algorithmique ainsi que Aho, Hopcroft et Ullman.

WPINFTHE.6 Cf. Informatique théorique, Wikipédia, op. cit. : Les années 1980 et 1990 sont propices au développement du calcul parallèle et des systèmes distribués.

WPINFTHE.7 Cf. Informatique théorique, Wikipédia, op. cit. : Il n’est pas facile de cerner précisément ce que l’on entend par “informatique théorique”. Le terme renvoie plutôt à une façon d’aborder les questions informatiques sous un angle plus mathématique et formel, en faisant souvent abstraction des aspects plus pratiques de l’informatique. En ce sens, l’informatique théorique est parfois considérée comme une branche des mathématiques discrètes. Ses objectifs se caractérisent généralement par une volonté d’identifier en principe les possibilités et les limites des ordinateurs. Le Special Interest Group on Algorithms and Computation Theory (SIGACT), regroupement affilié à l’Association for Computing Machinery (ACM) et voué au soutien à la recherche en informatique théorique en donne une définition assez large qui comprend des domaines aussi divers que l’algorithmique et les structures de données, la théorie de la complexité, le parallélisme, le VLSI, l’apprentissage automatique, la bio-informatique, la géométrie algorithmique, la théorie de l’information, la cryptographie, l’informatique quantique, la théorie algorithmique des nombres et de l’algèbre, la sémantique des langages de programmation, les méthodes formelles, la théorie des automates et l’étude de l’aléatoire en informatique.

WPINFTHE.8 Cf. Informatique théorique, Wikipédia, op. cit. : Cette discipline [l’algorithmique] tente de découvrir, d’améliorer et d’étudier de nouveaux algorithmes permettant de résoudre des problèmes avec une plus grande efficacité.

WPINFTHE.9 Cf. Informatique théorique, Wikipédia, op. cit. : Certains programmes sensibles nécessitent une parfaite fiabilité et de ce fait des outils mathématiques à mi-chemin entre l’algorithmique, la modélisation et l’algèbre sont développés afin de permettre de vérifier formellement les programmes et algorithmes.

WPINFTHE.10 Cf. Informatique théorique, Wikipédia, op. cit. : La théorie de l’information résulte initialement des travaux de Ronald A. Fisher. Ce statisticien théorise l’information dans sa théorie des probabilités et des échantillons. Techniquement, “l’information” est égale à la valeur moyenne du carré de la dérivée du logarithme de la loi de probabilité étudiée. À partir de l’inégalité de Cramer, la valeur d’une telle “information” est proportionnelle à la faible variabilité des conclusions résultantes. En d’autres termes, Fisher met l’information en relation avec le degré de certitude. D’autres modèles mathématiques ont complété et étendu de façon formelle la définition de l’information. Claude Shannon et Warren Weaver renforcent le paradigme. Ingénieurs en télécommunication, leurs préoccupations techniques les ont conduits à vouloir mesurer l’information pour en déduire les fondamentaux de la Communication (et non une théorie de l’information). Dans Théorie Mathématique de la Communication en 1948, ils modélisent l’information pour étudier les lois correspondantes : bruit, entropie et chaos, par analogie générale aux lois d’énergétique et de thermodynamique. Leurs travaux complétant ceux d’Alan Turing, de Norbert Wiener et de Von Neuman (pour ne citer que les principaux) constituent le socle initial des “Sciences de l’information”. La théorie de l’information s’appuie principalement sur deux notions caractéristiques que sont la variation d’incertitude et l’entropie (“désordre” au sens d’absence d’ordre et donc d’information dans l’ensemble considéré, d’où indétermination). Déclinant ces principes et ceux d’autres sciences dures, les technologies s’occupent de la façon d’implémenter, agencer et réaliser des solutions pour répondre aux besoins des sociétés humaines. Certains chercheurs tentent de tirer des parallèles entre les concepts d’entropie en physique et d’entropie en informatique afin d’obtenir une formulation informatique de la cosmologie et de la réalité physique de notre monde qui, selon certains, pourraient trouver des clés dans des outils mathématiques que sont les automates cellulaires.

WPINFTHE.11 Cf. Informatique théorique, Wikipédia, op. cit. : La théorie des graphes permet de modéliser de nombreux problèmes discrets : calculs de trajets, allocations de ressource, problèmes SAT… On peut citer le théorème des quatre couleurs comme résultat classique de cette branche de l’informatique.

WPINFTHE.12 Cf. Informatique théorique, Wikipédia, op. cit. : La théorie de la calculabilité a pour objet la caractérisation des fonctions qu’un algorithme peut calculer. En effet, il est possible de montrer qu’il existe des fonctions qui ne sont pas calculables par un ordinateur, et il est dès lors intéressant de savoir lesquelles le sont. Le problème du castor affairé ou la fonction d’Ackermann sont des exemples classiques d’objets étudiés dans ce domaine.

WPINFTHE.13 Cf. Informatique théorique, Wikipédia, op. cit. : La théorie des langages, souvent liée à la théorie des automates, s’intéresse à la reconnaissance d’ensemble de mots sur un vocabulaire donné. Elle est utilisée dans les algorithmes de traitement de la langue naturelle par exemple : traduction automatique, indexation automatique de documents, etc. ainsi que dans ceux des langues artificielles comme les langages de programmation : compilation, interprétation.

WPINFTHE.14 Cf. Informatique théorique, Wikipédia, op. cit. : La logique formelle est un outil fondamental de l’informatique, on y trouve notamment la théorie des types, le lambda calcul et la réécriture comme outils de base de la programmation fonctionnelle et des assistants de preuve.

WPINFUBI Informatique ubiquitaire

Informatique ubiquitaire, Wikipédia, https://fr.wikipedia.org/wiki/Informatique_ubiquitaire.

WPINFUBI.1 Cf. Informatique ubiquitaire, Wikipédia, op. cit. : L’informatique ubiquitaire (ou plus succinctement “ubicomp”) est la troisième ère de l’histoire de l’informatique, qui succède à l’ère des ordinateurs personnels et celle des ordinateurs centraux. Dans cette ère, l’utilisateur a à sa disposition une gamme de petits appareils informatiques tels que le téléphone multifonction ou l’assistant personnel, et leur utilisation fait partie de sa vie quotidienne. Ces appareils facilitent l’accès à l’information pour tout le monde, n’importe où et n’importe quand. Les utilisateurs ont alors la possibilité de s’échanger des données facilement, rapidement et sans effort, quelle que soit leur position géographique. Cette omniprésence de l’accès à l’information a un fort impact sur la société et modifie les habitudes de travail et de vie privée. La Commission européenne utilise les mots “intelligence ambiante” pour décrire le milieu créé par les appareils. Les États-Unis privilégient les mots “informatique ubiquitaire”, tandis que le Japon parle de société des réseaux omniprésents.

WPLOGINT Logique intuitionniste

Logique intuitionniste, Wikipédia, https://fr.wikipedia.org/wiki/Logique_intuitionniste.

WPLOGINT.1 Cf. Logique intuitionniste, Wikipédia, op. cit. : La logique intuitionniste est une logique qui diffère de la logique classique par le fait que la notion de vérité est remplacée par la notion de preuve constructive. […] La logique intuitionniste établit, entre autres, un distinguo entre “être vrai” et “ne pas être faux” (formulation plus faible) car ¬¬P → P n’est pas non plus démontrable en logique intuitionniste.

WPLOGINT.2 Cf. Logique intuitionniste, Wikipédia, op. cit. : Brouwer a prôné une mathématique qui rejetterait le tiers exclu et n’accepterait que l’existentiel constructif. […] Elle a été ensuite formalisée, sous le nom de logique intuitionniste, par ses élèves V. Glivenko et Arend Heyting, ainsi que par Kurt Gödel et Andreï Kolmogorov. L’interprétation de Brouwer-Heyting-Kolmogorov ou simplement interprétation BHK est essentiellement la mise en évidence du caractère constructif de l’implication intuitionniste : Quand un mathématicien intuitionniste affirme a ⇒ b, il veut dire qu’il fournit un procédé de “construction” d’une démonstration de b à partir d’une démonstration de a. Autrement dit, une preuve de a ⇒ b est une fonction qui transforme une preuve de a en une preuve de b. Cette interprétation calculatoire trouvera son aboutissement dans un des plus importants résultats de l’informatique théorique : la correspondance de Curry-Howard dont le leitmotiv est “prouver, c’est programmer”. Il y a isomorphisme entre les règles de déduction de la logique intuitionniste et les règles de typage du lambda-calcul. En conséquence, une preuve d’une proposition P est assimilable à un (lambda-)terme de type P. Dès lors, la logique intuitionniste (couplée à la théorie des types) acquiert un statut prépondérant en logique et en informatique théorique, en faisant d’elle historiquement la première des logiques constructives. Ce résultat fondateur engendrera de multiples travaux dérivés ; notamment son extension à la logique d’ordre supérieur qui nécessite l’emploi de types dépendants (le calcul des constructions, par exemple, est la base théorique du logiciel Coq qui est donc, à la fois, un assistant de preuves (constructives), et un outil de création de programmes certifiés).

WPLOGMAT Logique mathématique

Logique mathématique, Wikipédia, https://fr.wikipedia.org/wiki/Logique_math%C3%A9matique.

WPLOGMAT.1 Cf. Logique mathématique, Wikipédia, op. cit. : La logique mathématique est née à la fin du XIXe siècle de la logique au sens philosophique du terme ; elle est l’une des pistes explorées par les mathématiciens de cette époque afin de résoudre la crise des fondements provoquée par la complexification des mathématiques et l’apparition des paradoxes. Ses débuts sont marqués par la rencontre entre deux idées nouvelles : la volonté chez Frege, Russell, Peano et Hilbert de donner une fondation axiomatique aux mathématiques ; la découverte par George Boole de l’existence de structures algébriques permettant de définir un “calcul de vérité”. La logique mathématique se fonde sur les premières tentatives de traitement formel des mathématiques, dues à Leibniz et Lambert (fin XVIIe siècle - début XVIIIe siècle). Leibniz a en particulier introduit une grande partie de la notation mathématique moderne (usage des quantificateurs, symbole d’intégration, etc.). Toutefois on ne peut parler de logique mathématique qu’à partir du milieu du XIXe siècle, avec les travaux de George Boole (et dans une moindre mesure ceux d’Auguste De Morgan) qui introduit un calcul de vérité où les combinaisons logiques comme la conjonction, la disjonction et l’implication, sont des opérations analogues à l’addition ou la multiplication des entiers, mais portant sur les valeurs de vérité faux et vrai (ou 0 et 1) ; ces opérations booléennes se définissent au moyen de tables de vérité. Le calcul de Boole véhiculait l’idée apparemment paradoxale, mais qui devait s’avérer spectaculairement fructueuse, que le langage mathématique pouvait se définir mathématiquement et devenir un objet d’étude pour les mathématiciens. Toutefois il ne permettait pas encore de résoudre les problèmes de fondements. Dès lors, nombre de mathématiciens ont cherché à l’étendre au cadre général du raisonnement mathématique et on a vu apparaître les systèmes logiques formalisés ; l’un des premiers est dû à Frege au tournant du XXe siècle.

WPLOGMAT.2 Cf. Logique mathématique, Wikipédia, op. cit. : Le programme de Hilbert a suscité de nombreux travaux en logique dans le premier quart du siècle, notamment le développement de systèmes d’axiomes pour les mathématiques : les axiomes de Peano pour l’arithmétique, ceux de Zermelo complétés par Skolem et Fraenkel pour la théorie des ensembles et le développement par Whitehead et Russell d’un programme de formalisation des mathématiques, les Principia Mathematica. C’est également la période où apparaissent les principes fondateurs de la théorie des modèles : notion de modèle d’une théorie, théorème de Löwenheim-Skolem.

WPLOGMAT.3 Cf. Logique mathématique, Wikipédia, op. cit. : En 1929 Kurt Gödel montre dans sa thèse de doctorat son théorème de complétude qui énonce le succès de l’entreprise de formalisation des mathématiques : tout raisonnement mathématique peut en principe être formalisé dans le calcul des prédicats. Ce théorème a été accueilli comme une avancée notable vers la résolution du programme de Hilbert, mais un an plus tard, Gödel démontrait le théorème d’incomplétude (publié en 1931) qui montrait irréfutablement l’impossibilité de réaliser ce programme. Ce résultat négatif n’a toutefois pas arrêté l’essor de la logique mathématique. Les années 1930 ont vu arriver une nouvelle génération de logiciens anglais et américains, notamment Alonzo Church, Alan Turing, Stephen Kleene, Haskell Curry et Emil Post, qui ont grandement contribué à la définition de la notion d’algorithme et au développement de la théorie de la complexité algorithmique (théorie de la calculabilité, théorie de la complexité des algorithmes). La théorie de la démonstration de Hilbert a également continué à se développer avec les travaux de Gerhard Gentzen qui a produit la première démonstration de cohérence relative et initié ainsi un programme de classification des théories axiomatiques. Le résultat le plus spectaculaire de l’après-guerre est dû à Paul Cohen qui démontre en utilisant la méthode du forcing l’indépendance de l’hypothèse du continu en théorie des ensembles, résolvant ainsi le 1er problème de Hilbert. Mais la logique mathématique subit également une révolution due à l’apparition de l’informatique ; la découverte de la correspondance de Curry-Howard, qui relie les preuves formelles au lambda-calcul de Church et donne un contenu calculatoire aux démonstrations, va déclencher un vaste programme de recherche.

WPLOGMAT.4 Cf. Logique mathématique, Wikipédia, op. cit. : En logiques classique et intuitionniste, on distingue deux types d’axiomes : les axiomes logiques qui expriment des propriétés purement logiques comme A ∨ ¬ A (principe du tiers exclu, valide en logique classique mais pas en logique intuitionniste) et les axiomes extra-logiques qui définissent des objets mathématiques ; par exemple les axiomes de Peano définissent les entiers de l’arithmétique tandis que les axiomes de Zermelo-Fraenkel définissent les ensembles. Quand le système possède des axiomes extra-logiques, on parle de théorie axiomatique. L’étude des différents modèles d’une même théorie axiomatique est l’objet de la théorie des modèles.

WPMETFOR Méthode formelle

Méthode formelle (informatique), Wikipédia, https://fr.wikipedia.org/wiki/M%C3%A9thode_formelle_(informatique).

WPMETFOR.1 Cf. Méthode formelle, Wikipédia, op. cit. : En informatique, les méthodes formelles sont des techniques permettant de raisonner rigoureusement, à l’aide de logique mathématique, sur des programmes informatiques ou du matériel électronique, afin de démontrer leur validité par rapport à une certaine spécification. Elles sont basées sur les sémantiques des programmes, c’est-à-dire sur des descriptions mathématiques formelles du sens d’un programme donné par son code source (ou parfois, son code objet).

WPNUMERI Numérique

Numérique, Wikipédia, https://fr.wikipedia.org/wiki/Num%C3%A9rique.

WPNUMERI.1 Cf. Numérique, Wikipédia, op. cit. : On dit numérique une information qui se présente sous forme de nombres associés à une indication de la grandeur à laquelle ils s’appliquent, permettant les calculs, les statistiques, la vérification des modèles mathématiques. Numérique s’oppose à analogique. Les ordinateurs développés depuis la seconde moitié du XXe siècle ont évolué à partir de machines à calculer programmables. Ils traitent désormais des données qu’on a pris l’habitude de désigner comme numériques. Par synecdoque, on dit numérique tout ce qui fait appel à des systèmes électroniques basés sur des fonctions logiques. À la base de l’informatique, on démontre que toute opération arithmétique peut se développer en opérations logiques, en représentant les nombres entiers dans le système binaire, tandis que la plupart des tâches peuvent s’effectuer par des algorithmes qui traitent ces données. La culture numérique désigne les relations sociales dans les circonstances où dominent les médias basés sur ces systèmes.

WPNUMERI.2 Cf. Numérique, Wikipédia, op. cit. : Les ordinateurs ont évolué à partir de machines à calculer programmables. Ils traitent par l’arithmétique et la logique des données dans laquelle la part des nombres représentant des grandeurs n’a cessé de décroître, au profit de ceux qui pointent vers des symboles et des algorithmes. Les programmeurs sont ainsi passés du calcul numérique au traitement de texte, le développant plus tard avec la correction orthographique et aujourd’hui avec la traduction automatique. […] Simultanément, le secteur des télécommunications a développé la conversion des signaux électriques en suites de nombres, dans le but d’améliorer l’efficacité des transmissions. La théorie de l’information associée à cette transformation indique que tout message peut être codé sous forme numérique. Après sa conversion en données numériques, les ordinateurs peuvent traiter l’information qui décrit les supports de ces messages. […] L’adjectif “numérique” distingue le son numérique, la photographie numérique, la vidéo numérique et le cinéma numérique de leurs versions plus anciennes fonctionnant avec des procédés analogiques.

WPNUMERI.3 Cf. Numérique, Wikipédia, op. cit. : L’adjectif “numérique” vient du latin “numerus” (“nombre”, “multitude”) et signifie “représentation par nombres”. On oppose ainsi le calcul numérique (l’arithmétique) au calcul littéral (par lettres, ou algèbre) et au calcul analogique. Devenu substantif, “numérique” désigne maintenant les technologies de l’information et de la communication, et “numérisation”, le basculement des spécialités vers ces technologies. […] Digital est anglais spécifique au traitement informatique, sans l’ambiguïté que numérique a en français entre son usage mathématique et statistique et son application aux ordinateurs.

WPNUMERI.4 Cf. Numérique, Wikipédia, op. cit. : Une donnée numérique est une suite de caractères et de nombres qui constituent une représentation discrète d’un objet.

WPNUMERI.5 Cf. Numérique, Wikipédia, op. cit. : Le mot “numérique” est “en train de devenir un mot passe-partout qui sert à définir un ensemble de pratiques qui caractérisent notre quotidien et dont nous avons peut-être encore du mal à saisir la spécificité”. Gérard Berry, constatant que le mot “numérique” a supplanté le mot “informatique” dans le discours politique et dans les médias, estime que pourtant “on ne peut comprendre le monde numérique dans sa totalité sans comprendre suffisamment ce qu’est son cœur informatique”.

WPNUMERI.6 Cf. Numérique, Wikipédia, op. cit. : la circulation massive d’informations lisibles par des machines stimule le contrôle de ces échanges, et indirectement des personnes qui les utilisent, par les grandes organisations étatiques et privées, capables d’extraire de ces immenses flux de données des indices pertinents de leur comportement.

WPOMECHA Oméga de Chaitin

Oméga de Chaitin, Wikipédia, https://fr.wikipedia.org/wiki/Om%C3%A9ga_de_Chaitin.

WIOMECHA.1 Cf. Oméga de Chaitin, Wikipédia, op. cit. : En théorie algorithmique de l’information, une constante Oméga de Chaitin (nombres définis et étudiés par Gregory Chaitin) caractérise de manière univoque et mathématiquement précise un nombre réel, qui possède la particularité d’être aléatoire et de ne pas être calculable au sens de Turing : un algorithme donné ne permet de calculer qu’un nombre fini de ses décimales. Jusqu’à la définition de ce nombre, il n’existait pas d’exemple mathématiquement précis et “concret” de suite aléatoire. Techniquement, il est défini comme étant la probabilité qu’un programme auto-délimité, généré aléatoirement, finisse par s’arrêter. Les programmes en question sont associés à une machine de Turing universelle ou à un modèle de calcul donné. Il existe donc une infinité de constantes de Chaitin, chacune associée soit à une machine de Turing universelle donnée, soit à un modèle de calcul. Cette définition permet également de coder, sous la forme la plus compacte possible, la solution du problème de l’arrêt pour tous les programmes d’un modèle de calcul donné. Comme il est possible de traduire la plupart des problèmes mathématiques en termes de programme informatique qui s’arrête ou non, la connaissance d’un nombre Oméga permet – en principe – de démontrer un grand nombre de théorèmes ou de conjectures mathématiques, dont certains encore non résolus à ce jour comme l’hypothèse de Riemann. Ces nombres apportent un éclairage sur l’incomplétude des mathématiques, mise au jour par le célèbre théorème de Gödel, ainsi que des éléments d’appréciation en ce qui concerne sa signification et sa portée.

WPPHIANA Philosophie analytique

Philosophie analytique, Wikipédia, https://fr.wikipedia.org/wiki/Philosophie_analytique.

WPPHIANA.1 Cf. Philosophie analytique, Wikipédia, op. cit. : L’expression “philosophie analytique” désigne un mouvement philosophique qui se fonda dans un premier temps sur la nouvelle logique contemporaine, issue des travaux de Gottlob Frege et Bertrand Russell à la fin du XIXe siècle et au début du XXe siècle, pour éclairer les grandes questions philosophiques. Sa démarche s’appuie sur une analyse logique du langage cherchant à mettre en évidence les erreurs de raisonnement que celui-ci peut induire et faisant ainsi de la “clarification logique de la pensée” le but de la philosophie selon le mot de Carnap.

WPPHIANA.2 Cf. Philosophie analytique, Wikipédia, op. cit. : À l’origine, la philosophie analytique s’oppose à l’hégélianisme, et plus largement aux courants issus de l’idéalisme allemand. En effet, après Emmanuel Kant, l’idéalisme allemand domine la philosophie occidentale à travers les réflexions et les œuvres de Fichte, de Schelling et de Hegel. La philosophie britannique devint elle-même de plus en plus hégélienne (F. H. Bradley, Thomas Hill Green…). Parallèlement, l’allemand Gottlob Frege pense en dehors de l’idéalisme de ses compatriotes et souhaite reprendre le projet de caractéristique universelle de Leibniz sous le nom de logicisme.

WPPHIANA.3 Cf. Philosophie analytique, Wikipédia, op. cit. : Le positivisme logique distinguait entre les énoncés analytiques, vrais de par leur signification intrinsèque (par exemple, “les célibataires sont non mariés”) ; les énoncés synthétiques a posteriori, dont une vérification empirique est possible ; enfin, les énoncés qui ne sont ni analytiques, ni synthétiques a posteriori, et qui seraient donc vides de sens, parce que ni tautologiques comme les énoncés analytiques, ni “vérifiables” comme les énoncés synthétiques a posteriori (ils niaient ainsi explicitement l’existence des jugements synthétiques a priori, au cœur du projet kantien de refondation de la métaphysique sur des bases scientifiques).

WPPHIANA.4 Cf. Philosophie analytique, Wikipédia, op. cit. : Le but de l’approche analytique est d’éclaircir les problèmes philosophiques en examinant et clarifiant le langage dont on se sert pour les formuler. Cette méthode compte parmi ses apports majeurs la logique moderne, la mise au jour du problème du sens et de la dénotation dans la construction de la signification, le théorème d’incomplétude de Kurt Gödel, la théorie des descriptions définies de Russell, la théorie de la réfutabilité de Karl Popper, la théorie sémantique de la vérité de Alfred Tarski.

WPPHIANA.5 Cf. Philosophie analytique, Wikipédia, op. cit. : L’origine de la philosophie analytique se trouve dans le développement, par Frege, du calcul des prédicats qui a permis d’étendre la formalisation logique à un plus grand nombre d’énoncés. De même, Russell et Whitehead se donnaient pour buts, dans leur Principia Mathematica : de montrer que les mathématiques et la logique peuvent être réduites à la logique mathématique ; de montrer que le résultat logique est un langage idéal.

WPPHIANA.6 Cf. Philosophie analytique, Wikipédia, op. cit. : Les défenseurs de la philosophie analytique font valoir que celle-ci possède un objectif de clarté et de précision au niveau de la description des problèmes philosophiques, qui rapproche ainsi la philosophie de la méthodologie des disciplines scientifiques. Cette clarté dans la description des problèmes et la formulation des solutions permet d’éviter l’ambiguïté et les difficultés d’interprétation souvent reprochées à la philosophie “littéraire”. La philosophie analytique se caractérise également par une approche concrète, “par problèmes”. Il en résulte ainsi la description précise de problèmes philosophiques, clairement identifiés, et pour lesquels il convient de rechercher une solution. Parmi ces problèmes, on peut citer notamment : le paradoxe du menteur, le paradoxe de Hempel, etc. Les critiques de la philosophie analytique pensent que ce n’est là qu’une simple injonction normative à la clarté et la rigueur et que cela décrit plus une tradition, des périodiques, des lectures et références communes, des exemples et problèmes récurrents, qu’une véritable “méthode” scientifique. De plus, la réduction logique est jugée trop superficielle, alors que la philosophie continentale estime remonter aux conditions mêmes du métaphysique, i.e., selon Heidegger, à une ouverture à l’être qui précéderait toute catégorisation logico-métaphysique et qui serait donc plus fondamentale, plus profonde.

WPPRTIEX Principe du tiers exclu

Principe du tiers exclu, Wikipédia, https://fr.wikipedia.org/wiki/Principe_du_tiers_exclu.

WPPRTIEX.1 Cf. Principe du tiers exclu, Wikipédia, op. cit. : En logique formelle, le principe du tiers exclu (ou “principe du milieu exclu” ou “tertium non datur” ou “principium medii exclusï”, ou simplement le “tiers exclu”) énonce que soit une proposition est vraie, soit sa négation est vraie. […] Au début de la formalisation des mathématiques, ce principe a été tenu comme un dogme intangible.

WPPRTIEX.2 Cf. Principe du tiers exclu, Wikipédia, op. cit. : Le principe du tiers exclu a été introduit par Aristote comme complément du principe de non-contradiction. En philosophie, le principe du tiers exclu, comme le principe d’identité, a une double version, ontologique ou logique. La version ontologique rejette la notion de gradation dans l’être : il y a être, ou non-être, pas de demi-être.

WPPRTIEX.3 Cf. Principe du tiers exclu, Wikipédia, op. cit. : La “loi de l’alternative” (Robert Blanché) résulte de la conjonction du principe de non-contradiction et du principe du tiers exclu. À eux deux, ces principes participent à fonder la logique mathématique formelle dite classique. La logique intuitionniste, quant à elle, n’inclut pas le principe du tiers-exclu.

WPPRTIEX.4 Cf. Principe du tiers exclu, Wikipédia, op. cit. : Les “logiques polyvalentes” mettent en question le principe dès Lukasiewicz en 1910, qui revient à l’antique question des “futurs contingents” : si une proposition qui concerne le futur pouvait être caractérisée au présent déjà comme vraie ou fausse, on devrait admettre que le cours des événements est déterminé à l’avance. Les logiques polyvalentes contestent le principe du tiers exclu. Elles reconnaissent d’autres valeurs que le vrai et le faux, elles admettent, entre les deux, l’indéterminé, ou le possible, ou, en deçà, l’impossible (qui est un faux renforcé), et au-delà le nécessaire (degré supérieur du vrai). Heyting ne dit pas que le tiers exclu est faux, il en limite la portée. Une proposition peut être absurde ou probable, et non seulement vraie ou fausse. Brouwer puis Arend Heyting en 1930, en tant qu’intuitionnistes, critiquent les raisonnements fondés sur le tiers exclu. Ils estiment qu’on n’a pas le droit d’inférer une proposition de l’absence de démonstration de sa négation. Leur position est adoptée par les logiciens spécialistes de la théorie des types, assez nombreux, avec le développement de l’informatique.

WPPRTIEX.5 Cf. Principe du tiers exclu, Wikipédia, op. cit. : Comme la double négation, le raisonnement par l’absurde est équivalent au principe du tiers exclu.

WPPRTIEX.6 Cf. Principe du tiers exclu, Wikipédia, op. cit. : La logique intuitionniste ne stipule pas le “principe” du tiers exclu. Autrement, dit, le tiers exclu n’est pas un dogme en logique intuitionniste. En revanche, on peut montrer en logique intuitionniste que le tiers exclu est irréfutable, c’est-à-dire qu’admettre sa négation aboutirait à une contradiction, dit autrement, la négation du tiers-exclu n’est pas démontrable en logique intuitionniste.

WPPROARR Problème de l’arrêt

Problème de l’arrêt, Wikipédia, https://fr.wikipedia.org/wiki/Probl%C3%A8me_de_l%27arr%C3%AAt.

WPPROARR.1 Cf. Problème de l’arrêt, Wikipédia, op. cit. : En théorie de la calculabilité, le problème de l’arrêt est le problème de décision qui détermine, à partir d’une description d’un programme informatique, et d’une entrée, si le programme s’arrête avec cette entrée ou non. Alan Turing a montré en 1936 que le problème de l’arrêt est indécidable, c’est-à-dire qu’il n’existe pas de programme informatique qui prend comme entrée une description d’un programme informatique et un paramètre et qui, grâce à la seule analyse de ce code, répond VRAI si le programme s’arrête sur son paramètre et FAUX sinon. Une partie importante de la démonstration a été la formalisation du concept de programmes informatiques : les machines de Turing.

WPPROARR.2 Cf. Problème de l’arrêt, Wikipédia, op. cit. : De très nombreux problèmes en informatique, notamment concernant l’analyse statique de programmes, sont équivalents au problème de l’arrêt. On le montre là encore en réduisant la résolution du problème de l’arrêt à celle du problème étudié.

WPPROARR.3 Cf. Problème de l’arrêt, Wikipédia, op. cit. : Le problème de l’arrêt est en théorie décidable dans le cas d’une mémoire de taille finie, car l’ensemble des états de la mémoire, bien que très grand, est fini lui-même. […] Le nombre exponentiellement élevé de combinaisons des états d’une mémoire limite dans la pratique cette méthode à de petits programmes comportant moins d’un millier de données scalaires (les instructions n’ont pas à être examinées si elles sont dans des segments protégés contre l’écriture, et donc ne varient jamais).

WPREVNUM Révolution numérique

Révolution numérique, Wikipédia, https://fr.wikipedia.org/wiki/R%C3%A9volution_num%C3%A9rique.

WPREVNUM.1 Cf. Révolution numérique, Wikipédia, op. cit. : La “révolution numérique” (ou plus rarement “révolution technologique”, “révolution Internet” ou “révolution digitale”) le bouleversement profond des sociétés provoqué par l’essor des techniques numériques telles que l’informatique et le développement du réseau Internet. Cette mutation se traduit par une potentielle mise en réseau planétaire des individus au travers de nouvelles formes de communication telles que le courriel, les réseaux sociaux, la messagerie instantanée, les blogs et autres sites web privés et publics, commerciaux ou non. Sur le Web, la révolution numérique s’accompagne d’une originelle décentralisation dans la circulation des idées qui devient de plus en plus sujette à l’hypercentralisation des acteurs privés. La révolution numérique se caractérise aussi par le développement de l’intelligence artificielle et l’essor du domaine de la robotique et est perçue par certains intellectuels et militants comme un ensemble de faits et une construction idéologique que l’on peut remettre en cause.

WPREVNUM.2 Cf. Révolution numérique, Wikipédia, op. cit. : En France, la plus ancienne occurrence connue de l’expression “révolution numérique” remonte au numéro spécial de la revue Sciences et avenir (no 95), du 1er décembre 1993. L’expression “révolution numérique” est entrée non seulement dans le langage usuel, mais aussi dans celui des sciences humaines et l’abondante littérature reprenant cette expression peut donner l’impression d’une conception non seulement consensuelle mais unique du sujet : la “révolution numérique” serait un fait établi, institué, et rien d’autre. Pour autant, les analyses de l’historien François Jarrige démontrent l’émergence discrète, car progressive (s’élaborant au fil du XIXe et du XXe siècle), d’un mouvement de pensée technocritique et le fait que l’association des mots “révolution” et “numérique” pose des questions d’ordre philosophique, dans un contexte qui dépasse donc largement l’avènement de l’informatique, qui porte sur le progrès technique et plus largement encore sur le concept même de progrès. Selon la mouvance technocritique, “la révolution numérique” ne pourrait pas se définir uniquement comme un ensemble de faits (l’invention de l’ordinateur, l’apparition d’internet, etc.), mais aussi comme une construction idéologique, au même titre que “le progrès”. C’est donc parce que l’attention se focalise sur les faits que l’expression “révolution numérique” est répandue, mais c’est aussi parce qu’elle n’est généralement pas (ou peu souvent) identifiée comme construction idéologique qu’elle est ambigüe.

WPREVNUM.3 Cf. Révolution numérique, Wikipédia, op. cit. : Le mot “numérique” renvoie au processus de numérisation, qui consiste à reproduire techniquement les valeurs d’un phénomène physique non plus sur le mode analogique, comme on faisait avant l’avènement des technologies numériques, mais en convertissant toutes les informations qui le constituent en données chiffrables que des matériels informatiques (ordinateurs, smartphones, tablettes, etc.) peuvent ensuite traiter, ayant été conçus et fabriqués pour cela.

WPREVNUM.4 Cf. Révolution numérique, Wikipédia, op. cit. : Comme la “révolution industrielle”, deux siècles plus tôt, la “révolution numérique” est provoquée par une évolution sensible, très marquée, des techniques. Elle est en effet directement associée à la naissance puis au développement de l’informatique, c’est-à-dire au fait que toute information (caractère d’imprimerie, son, forme, couleur, puis mot, texte, photographie, film, musique, etc.) peut être numérisée, c’est-à-dire s’exprimer par une combinaison de chiffres (en l’occurrence des 0 et des 1), puis stockée, modifiée, éditée (sur des sites ou des blogs) et transmise (par mails, sur des forums, etc.) au moyen de toutes sortes d’appareils comme des ordinateurs, des tablettes ou des smartphones.

WPREVNUM.5 Cf. Révolution numérique, Wikipédia, op. cit. : Selon Marcello Vitali-Rosati et Michaël E. Sinatra, la “révolution numérique” engage à une “réinterprétation des structures conceptuelles à travers lesquelles l’homme se rapporte au monde et, surtout, structure et organise sa connaissance.” Du fait qu’elle marque l’entrée dans un nouveau paradigme de la connaissance, la numérisation des informations est souvent comparée à l’invention de l’imprimerie.

WPREVNUM.6 Cf. Révolution numérique, Wikipédia, op. cit. : Dans l’histoire de ce processus, trois tournants sont habituellement distingués : dans les années 1980, la généralisation de l’ordinateur personnel et la naissance d’Internet ; dans les années 1990, l’explosion du phénomène Internet, surnommé “le réseau des réseaux” ; dans les années 2000, l’apparition du smartphone, ordinateur tenant dans la main et pouvant être utilisé pratiquement partout sur la planète. Ces innovations permettant aux échanges de s’opérer sous une forme électronique, les barrières géographiques et culturelles cessent d’être aussi contraignantes que par le passé. Cette mutation bouleverse l’ensemble des règles géopolitiques mondiales (mondialisation), l’économie planétaire (avènement de la Nouvelle économie) et, plus radicalement, la façon dont les individus perçoivent le monde, se comportent avec autrui et se considèrent eux-mêmes.

WPREVNUM.7 Cf. Révolution numérique, Wikipédia, op. cit. : Le sociologue Jacques Ellul, à la fois spécialiste de la révolution et penseur technocritique, affirme que, dès lors que la technique prend une part croissante dans l’histoire de l’humanité, la révolution n’est plus qu’un mythe

WPREVNUM.8 Cf. Révolution numérique, Wikipédia, op. cit. : L’expression “révolution numérique” accole deux termes d’origines très différentes : le mot “révolution” définit l’idée d’une émancipation des individus au prix d’un bouleversement politique organisé et théorisé mais se déroulant de façon rapide et mouvementée, voire violente ; le mot “numérique” renvoie quant à lui à une évolution de la technique (les informations se transmettent non plus par des signaux analogiques mais précisément par des signaux numériques) mais cette mutation s’opère "progressivement", au fil des avancées scientifiques et techniques, et sans concertation préalable avec le milieu politique.

WPREVNUM.9 Cf. Révolution numérique, Wikipédia, op. cit. : L’expression “révolution numérique” désigne donc à la fois un ensemble de faits réels et une idéologie. D’une part, en effet “le numérique” désigne objectivement le processus de numérisation d’un nombre sans cesse croissant d’informations ; lequel processus se traduit par l’évolution de toutes sortes d’outils qui transforment les liens sociaux de façon spectaculaire : ces outils sont de plus en plus nombreux ; ils sont de plus en plus performants, la capacité de calcul d’un smartphone est supérieure à celle d’un micro-ordinateur du début des années 1980 ; ils semblent de plus en plus “intelligents”, capables d’assumer plusieurs fonctions logiques différentes (voir intelligence artificielle) ; ils sont de plus en plus petits et invisibles, pouvant être introduits sous la peau ou dans nos corps (voir miniaturisation et nanotechnologies) ; ils semblent de plus en plus “naturels”, se fondant dans l’environnement ambiant (voir domotique) et dans les habitudes (voir interaction homme-robot) ; ils fonctionnent en réseau, permettant à leurs utilisateurs de surmonter aisément des situations complexes (voir réseau informatique) ; ils confèrent du pouvoir à leurs utilisateurs : filmer/enregistrer autrui à son insu ou le géolocaliser, percevoir le virtuel, via des écrans, comme on perçoit le réel (voir réalité augmentée) ; ils sont de plus en plus autonomes (voir rétroaction), pouvant même communiquer entre eux (voir Internet des objets) ; ils pourraient éventuellement apprendre par eux-mêmes et ainsi égaler les humains (voir apprentissage profond) voire les surpasser (voir singularité technologique) ; ils pourraient, par cette autonomisation croissante, amorcer une transformation radicale et irréversible de la condition humaine (voir cyborg), la fin de l’humanisme et l’avènement du transhumanisme. D’autre part, les analystes technocritiques estiment que qualifier cette évolution de “révolution”, au seul motif qu’elle est très rapide, constitue un glissement sémantique injustifié : “le numérique” a beau modifier le lien social de façon spectaculaire, il ne “révolutionne” en rien l’ordre politique et économique ; il le renforce même au contraire et le stimule. Ces analystes considèrent que, faute d’une “révolution intellectuelle” – à savoir une expertise de ce que Jacques Ellul appelle le “système technicien” –, le système capitaliste ne peut que se renforcer et les “géants du web” continuer de grandir et influer sur les comportements.

WPREVNUM.10 Cf. Révolution numérique, Wikipédia, op. cit. : Les premiers ordinateurs étaient de simples machines à calculer : les informations qu’ils avaient à traiter étaient exclusivement des nombres. Comprendre l’histoire du numérique nécessite donc de saisir l’histoire du calcul. Très tôt, les humains ont conçu et fabriqué des outils les aidant à calculer (abaque, boulier…). Mais c’est à partir du XVIIIe siècle qu’ils ne cessent de les perfectionner, quand s’amorce (en Angleterre puis en France) la Révolution industrielle. Alors que la société s’était bâtie sur une économie à dominante agraire et artisanale, elle s’urbanise de façon croissante, devenant de plus en plus commerciale et industrielle. Dans le but de rendre la production toujours plus efficace, les machines sont conçues et fabriquées à un rythme exponentiel. Au fur et à mesure que la société se mécanise, émerge l’idée selon laquelle la machine ne doit pas seulement aider les hommes, mais aussi, autant que possible, les remplacer. Le goût pour les automates, qui se développe à cette époque, traduit un désir plus ou moins conscient : celui que toutes les étapes d’un processus de production (conception, fabrication, maintenance, commercialisation, etc.) soient prises en charge par une “machinerie intelligente”, c’est-à-dire habilitée à traiter un maximum d’information automatiquement et à la place de l’homme. Il est donc d’usage de considérer “la révolution numérique” comme le prolongement logique de la révolution industrielle.

WPREVNUM.11 Cf. Révolution numérique, Wikipédia, op. cit. : Dans la deuxième moitié du siècle, deux philosophes, l’Allemand Gottfried Wilhelm Leibniz et l’Anglais Thomas Hobbes, émettent l’hypothèse que la pensée peut se formuler de façon systématique par le biais d’un langage mathématique. Le premier imagine un langage assimilant l’argumentation à un calcul, afin qu’“il n’y ait pas plus de besoin de se disputer entre deux philosophes qu’entre deux comptables”. Selon Hobbes, “la raison n’est rien d’autre que le fait de calculer”. Mais c’est un autre philosophe, le Français Blaise Pascal, qui entreprend de concrétiser ces principes en inventant la pascaline dès 1642 : la toute première machine à calculer dont le fonctionnement permet de traiter un algorithme.

WPREVNUM.12 Cf. Révolution numérique, Wikipédia, op. cit. : En 1801, Joseph Marie Jacquard, avec son métier à tisser à cartes perforées, fait émerger le concept de programmation. En 1834, le mathématicien anglais Charles Babbage, associant les inventions de Pascal et de Jacquard, conçoit la machine analytique (véritable ancêtre de l’ordinateur) alimentée par l’énergie à vapeur. Dans les années 1840 et 1850, Ada Lovelace et George Boole développent des théories permettant non seulement de traiter des opérations mathématiques de manière automatique, mais également de traduire des concepts en équations.

WPREVNUM.13 Cf. Révolution numérique, Wikipédia, op. cit. : Mesurant l’ampleur de cette mutation et de son impact sur les mentalités, Jacques Ellul publie, en 1954, La Technique ou l’Enjeu du siècle qui constitue la toute première approche anthropologique du phénomène technicien. Selon lui, le développement de l’automation conduit la technique à se développer de façon autonome : celle-ci échappe à tout contrôle des hommes dès lors qu’ils s’obstinent à croire qu’elle n’est qu’un moyen neutre à leur service.

WPREVNUM.14 Cf. Révolution numérique, Wikipédia, op. cit. : Pour Ellul, l’informatique constitue le nœud de ce système. Elle ne constitue pas un “problème en soi”, mais le fait que l’on ne considère pas qu’elle n’est qu’un ensemble de représentations du réel et non le réel lui-même crée une césure entre monde réel et monde virtuel qui, in fine, menace la liberté de l’humanité tout entière si celle-ci ne la repère pas : “L’informatique n’est pas une technique comme une autre, elle porte l’ensemble technicien à sa perfection en mettant tous ses éléments en interconnexion. Ce faisant, elle transforme complètement le rapport au réel, en déréalisant tout, en transformant toute chose en signe à consommer, en rendant toute réalité ‘autre qu’elle-même’ : abstraite, lointaine et sans contenu.”

WPREVNUM.15 Cf. Révolution numérique, Wikipédia, op. cit. : “Avant, nous allions sur Internet, maintenant, nous sommes dedans. Nous avons adopté les nouvelles technologies et elles ont tout bouleversé : les démocraties et les dictatures, la paix et la guerre, les États et les sociétés civiles. Elles servent à la fois d’outils de libération et d’oppression, de partage et d’exclusion. La révolution numérique apporte peut-être autant de changements que l’avènement de l’agriculture. Plus de deux milliards d’humains sont aujourd’hui connectés à Internet, faisant basculer dans le champ politique la question numérique, jusqu’ici cantonnée à la technique et à l’économie. La crise donne aux hommes de nouvelles occasions de se révolter, les réseaux leur offrent de nouveaux moyens de le faire. […] L’avenir appartient à ceux qui s’en saisissent, non à ceux qui le refusent.” [Jean Rognetta, Julie Jammot, Frédéric Tardy, La république des réseaux. Périls et promesses d’une révolution numérique, Fayard, 2012. 4e page de couverture.]

WPREVNUM.16 Cf. Révolution numérique, Wikipédia, op. cit. : Le phénomène “révolution numérique” participe du phénomène “progrès technique” qui, au XXe siècle, a provoqué différentes réactions, parmi lesquelles celle d’Herbert Marcuse, pour qui la “technoscience” est un processus n’ayant d’autre finalité que de servir le capitalisme

WPSEMAXI Sémantique axiomatique

Sémantique axiomatique, Wikipédia, https://fr.wikipedia.org/wiki/S%C3%A9mantique_axiomatique.

WPSEMAXI.1 Cf. Sémantique axiomatique, Wikipédia, op. cit. : La sémantique axiomatique est une approche basée sur la logique mathématique qui sert à prouver qu’un programme informatique est correct. Cette sémantique tend à considérer un programme comme un transformateur de propriétés logiques, c’est-à-dire que la signification donnée au programme est un ensemble de prédicats qui sont vérifiés par l’état de la machine (caractérisé par sa mémoire) qui a exécuté le programme, à condition qu’un autre ensemble de prédicats ait été vérifié avant exécution. L’enjeu est en général de trouver la sémantique axiomatique la plus fine possible : étant donné une spécification de sortie que l’on veut en général la plus forte (restrictive) possible, on cherche les préconditions les plus faibles (larges) qui aboutissent à ce résultat.

WPSEMAXI.2 Cf. Sémantique axiomatique, Wikipédia, op. cit. : La sémantique axiomatique est l’une des sémantiques les plus grossières (anglais : coarse-grained) que l’on rencontre pour les langages de programmation. Elle est en effet une approximation, ou abstraction de la sémantique dénotationnelle, qui voit le programme comme une fonction qui transforme la mémoire et elle-même approxime la sémantique opérationnelle qui voit le programme comme une succession d’états de la machine.

WPSELAPR Sémantique des langages de programmation

Sémantique des langages de programmation, Wikipédia, https://fr.wikipedia.org/wiki/S%C3%A9mantique_des_langages_de_programmation.

WPSELAPR.1 Cf. Sémantique des langages de programmation, Wikipédia, op. cit. : En informatique théorique, la sémantique formelle (des langages de programmation) est l’étude de la signification des programmes informatiques vus en tant qu’objets mathématiques.

WPSELAPR.2 Cf. Sémantique des langages de programmation, Wikipédia, op. cit. : Les sémantiques les plus couramment utilisées pour donner du sens à un langage de programmation sont la sémantique opérationnelle, la sémantique dénotationnelle et la sémantique axiomatique.

WPSELAPR.3 Cf. Sémantique des langages de programmation, Wikipédia, op. cit. : En sémantique opérationnelle, la signification d’un programme est la suite des états de la machine qui exécute le programme. Autrement dit un programme est considéré comme la description d’un système de transition d’états.

WPSELAPR.4 Cf. Sémantique des langages de programmation, Wikipédia, op. cit. : Initiée par Christopher Strachey et Dana Scott, la sémantique dénotationnelle est une approche dans laquelle une fonction mathématique appelée dénotation est associée à chaque programme, et représente en quelque sorte son effet, sa signification. Cette fonction prend par exemple pour argument l’état de la mémoire avant exécution, et a pour résultat l’état après exécution.

WPSELAPR.5 Cf. Sémantique des langages de programmation, Wikipédia, op. cit. : En sémantique axiomatique, le programme n’est plus qu’un transformateur de propriétés logiques sur l’état de la mémoire : si on a p vrai avant exécution, alors on a q vrai après. On ne s’intéresse plus à l’état précis de la mémoire tant que l’on sait dire si la propriété tient.

WPSUIALE Suite aléatoire

Suite aléatoire, Wikipédia, https://fr.wikipedia.org/wiki/Suite_al%C3%A9atoire.

WPSUIALE.1 Cf. Suite aléatoire, Wikipédia, op. cit. : En mathématiques, une suite aléatoire, ou suite infinie aléatoire, est une suite de symboles d’un alphabet ne possédant aucune structure, régularité, ou règle de prédiction identifiable. Une telle suite correspond à la notion intuitive de nombres tirés au hasard. La caractérisation mathématique de cette notion est extrêmement difficile, et a fait l’objet d’études et de débats tout au long du XXe siècle. Une première tentative de définition mathématique (insatisfaisante) a été réalisée en 1919 par Richard von Mises. Ce fut l’avènement de la théorie de la calculabilité, dans les années 1930, et de la théorie algorithmique de l’information qui permit d’aboutir dans les années 1970 – au terme d’une succession de travaux menés notamment par Andreï Kolmogorov, Gregory Chaitin, et Per Martin-Löf – à des définitions faisant aujourd’hui consensus (bien que toujours non tout à fait unanime). Les définitions actuellement acceptées (démontrées équivalentes) du caractère aléatoire d’une suite sont les suivantes : une suite aléatoire ne doit posséder aucune régularité “exceptionnelle et effectivement testable” (Martin-Löf 1966) ; une suite aléatoire doit posséder un “contenu informationnel incompressible” (Levin 1974, Chaitin 1975) ; une suite aléatoire doit être imprévisible, c’est-à-dire qu’aucune “stratégie effective” ne peut mener à un “gain infini” si l’on “parie” sur les termes de la suite (Schnorr (en) 1971). Chacun des termes employés dans les définitions ci-dessus possède une définition mathématique rigoureuse. L’ensemble des suites aléatoires, sur un alphabet quelconque peut être représenté par celles n’utilisant que les chiffres “0” ou “1” qui peuvent elles-mêmes être mises en relation bijective avec l’ensemble des nombres réels dont le développement numérique écrit en notation binaire est constitué de chiffres “aléatoires”. De fait, la quasi-totalité des études et définitions mathématiques concernant les suites aléatoires sont effectuées en utilisant la traduction de la suite en un nombre réel, compris entre 0 et 1, écrit en binaire, donnant ainsi une simple suite de 0 et de 1. Bien que très fructueuses sur le plan théorique, et menant à d’intéressants corollaires et propriétés, ces définitions sont en fait peu applicables en pratique pour tester le caractère aléatoire d’une véritable suite. Malgré tout, ces définitions commencent à trouver des applications théoriques dans les domaines de la physique, de la biologie ou de la philosophie.

WPSUIALE.2 Cf. Suite aléatoire, Wikipédia, op. cit. : La théorie algorithmique de l’information, développée par Ray Solomonoff et Andreï Kolmogorov dans les années 1960, a rendu possible de définir, de manière absolue, la notion de contenu en information d’une suite : il s’agit de la complexité de Kolmogorov. Cette mesure est définie comme étant la longueur du plus petit programme nécessaire pour engendrer la suite. Il est démontré que cette mesure ne dépend pas fondamentalement de la machine utilisée pour coder et exécuter le programme, à une constante additive près, ce qui justifie son caractère absolu. “Sur la base de ces considérations, il peut apparaître naturel de définir une suite sans régularité, ou suite finie aléatoire, comme une suite qui pour être calculée demande en gros un programme aussi long qu’elle même.”

WPSUIALE.3 Cf. Suite aléatoire, Wikipédia, op. cit. : Le caractère peu ou très aléatoire d’une suite de symboles dépend du contexte (cryptographie, compression de données, tests et autres) et explique la multiplicité des approches pour définir un hasard parfait.

WPSYSAXI Système axiomatique

Système axiomatique, Wikipédia, https://fr.wikipedia.org/wiki/Syst%C3%A8me_axiomatique.

WPSYSAXI.1 Cf. Système axiomatique, Wikipédia, op. cit. : En mathématiques, un système axiomatique est un ensemble d’axiomes dont certains ou tous les axiomes peuvent être utilisés logiquement pour dériver des théorèmes. Une théorie consiste en un système axiomatique et tous ses théorèmes dérivés. Un système axiomatique complet est un type particulier de système formel. Une théorie formelle signifie généralement un système axiomatique, par exemple formulé dans la théorie des modèles. Une démonstration formelle est une interprétation complète d’une démonstration mathématique dans un système formel.

WPSYSAXI.2 Cf. Système axiomatique, Wikipédia, op. cit. : Un système axiomatique est dit être cohérent s’il ne contient aucune contradiction, à savoir la capacité à dériver à la fois une affirmation et son refus des axiomes du système. Dans un système axiomatique, un axiome est appelé indépendant s’il n’est pas un théorème qui peut être dérivé d’autres axiomes du système. Un système est dit indépendant si tous ses axiomes sous-jacents sont indépendants. Bien que l’indépendance n’est pas une condition nécessaire pour un système, la cohérence l’est. Un système axiomatique est dit complet si toute proposition, ou sa négation, est dérivable.

WPSYSAXI.2 Cf. Système axiomatique, Wikipédia, op. cit. : Un modèle pour un système axiomatique est un ensemble bien défini, qui attribue une signification aux termes non définis présentés dans le système, d’une manière qui est correcte avec les relations définies dans le système. L’existence d’un modèle concret prouve la cohérence d’un système. Un modèle est dit concret si les significations assignées sont des objets et des relations du monde réel, par opposition à un modèle abstrait, qui repose sur d’autres systèmes axiomatiques.

WPSYSAXI.3 Cf. Système axiomatique, Wikipédia, op. cit. : La méthode axiomatique consiste à déclarer les définitions et propositions de manière que chaque nouveau terme puisse être formellement éliminé par les termes qui nécessitent des notions primitives (axiomes) précédemment introduites pour éviter une régression à l’infini. Une position commune à l’égard de la méthode axiomatique est le logicisme. Dans leur livre Principia Mathematica, Alfred North Whitehead et Bertrand Russell ont tenté de démontrer que toute théorie mathématique pouvait être réduite à une certaine collection d’axiomes. Plus généralement, la réduction d’un ensemble de propositions à une collection particulière d’axiomes sous-tend le programme de recherche du mathématicien.

WPSYSAXI.4 Cf. Système axiomatique, Wikipédia, op. cit. : Les axiomes Zermelo-Fraenkel, le résultat de la méthode axiomatique appliqués à la théorie des ensembles, ont permis la formulation “propre” des problèmes de la théorie des ensembles et ont aidé à éviter les paradoxes de la théorie naïve des ensembles. Un tel problème était l’hypothèse du continu. La théorie des ensembles de Zermelo-Fraenkel avec l’axiome du choix inclus historiquement controversée, est généralement abrégée ZFC, où C représente le Choix. De nombreux auteurs utilisent la théorie des ensembles ZF sans l’axiome du choix. Aujourd’hui ZFC est la forme standard de la théorie des ensembles axiomatique et en tant que telle, elle est la fondation la plus commune des mathématiques.

WPSYSAXI.5 Cf. Système axiomatique, Wikipédia, op. cit. : En mathématiques, l’axiomatisation est la formulation d’un système d’affirmations (à savoir, des axiomes) qui se rapportent à un certain nombre de termes primitifs afin qu’un ensemble cohérent de propositions puisse être dérivé déductivement de ces affirmations. Par la suite, la démonstration de toute proposition devrait être, en principe, retracée à ces axiomes.

WPTHINGO Théorèmes d’incomplétude de Gödel

Théorèmes d’incomplétude de Gödel, Wikipédia, https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8mes_d%27incompl%C3%A9tude_de_G%C3%B6del.

WPTHINGO.1 Cf. Théorèmes d’incomplétude de Gödel, Wikipédia, op. cit. : Le premier théorème d’incomplétude établit qu’une théorie suffisante pour y démontrer les théorèmes de base de l’arithmétique est nécessairement incomplète, au sens où il existe des énoncés qui n’y sont ni démontrables, ni réfutables (un énoncé est démontrable si on peut le déduire des axiomes de la théorie, il est réfutable si on peut déduire sa négation). On parle alors d’énoncés indécidables dans la théorie. Le second théorème d’incomplétude est à la fois un corollaire et une formalisation d’une partie de la preuve du premier. Il traite le problème des preuves de cohérence d’une théorie : une théorie est cohérente s’il existe des énoncés qui n’y sont pas démontrables (ou, ce qui revient au même, si on ne peut y démontrer A et non A) […]. Le second théorème affirme alors que si la théorie est cohérente cet énoncé ne peut pas en être conséquence, ce que l’on peut résumer par : “une théorie cohérente ne démontre pas sa propre cohérence”.

WPTHINGO.2 Cf. Théorèmes d’incomplétude de Gödel, Wikipédia, op. cit. : Dans n’importe quelle théorie récursivement axiomatisable, cohérente et capable de “formaliser l’arithmétique”, on peut construire un énoncé arithmétique qui ne peut être ni démontré ni réfuté dans cette théorie.

WPTHINGO.3 Cf. Théorèmes d’incomplétude de Gödel, Wikipédia, op. cit. : Ainsi les théorèmes de Gödel ont pour corollaire, au sens mathématique du terme, l’impossibilité de réaliser le programme de Hilbert.

WPTHINGO.4 Cf. Théorèmes d’incomplétude de Gödel, Wikipédia, op. cit. : Le second problème de la célèbre liste que Hilbert présenta en 1900 à Paris était celui de la démonstration de la cohérence de l’arithmétique. L’arithmétique joue un rôle particulier dans le programme car, même si Hilbert n’a jamais défini précisément ce qu’il entendait par théorie finitaire, il semble clair qu’à ses yeux l’arithmétique en était une. Il était donc important à ses yeux de démontrer la cohérence de l’arithmétique par des moyens internes, c’est-à-dire sans employer de principe mathématique plus fort que la récurrence sur les entiers ; comme on l’a déjà vu, le second théorème d’incomplétude montre que c’est impossible. Curieusement cela n’a pas empêché les logiciens de continuer à chercher ; ainsi Gerhard Gentzen donna en 1936 une preuve de cohérence de l’arithmétique qui utilisait un principe d’induction plus fort que la récurrence sur les entiers, et Gödel lui-même produisit plusieurs constructions, notamment l’interprétation Dialectica, conduisant à des preuves de cohérence de l’arithmétique. Mentionnons également Alonzo Church dont le lambda-calcul fut initialement conçu pour développer des preuves élémentaires de cohérence. Ainsi, cette recherche de démonstrations de cohérence, apparemment rendue vaine par les théorèmes d’incomplétude, fut au contraire extrêmement fructueuse en posant les bases de la théorie de la démonstration moderne.

WPTHINGO.5 Cf. Théorèmes d’incomplétude de Gödel, Wikipédia, op. cit. : Les théorèmes d’incomplétude traitent du rapport fondamental en logique entre vérité et prouvabilité et surtout établissent de façon formelle que ces deux concepts sont profondément différents.

WPTHINGO.6 Cf. Théorèmes d’incomplétude de Gödel, Wikipédia, op. cit. : Ainsi, d’après des travaux de Gödel, puis de Paul Cohen, l’axiome du choix et l’hypothèse du continu sont des énoncés indécidables dans ZF la théorie des ensembles de Zermelo et Fraenkel, le second étant d’ailleurs indécidable dans ZFC (ZF plus l’axiome du choix).

WPTHINGO.7 Cf. Théorèmes d’incomplétude de Gödel, Wikipédia, op. cit. : Il y a un lien étroit entre décidabilité algorithmique d’une théorie, l’existence d’une méthode mécanique pour tester si un énoncé est ou non un théorème, et complétude de cette théorie.

WPTHINGO.8 Cf. Théorèmes d’incomplétude de Gödel, Wikipédia, op. cit. : En 1931, Gödel connaît un modèle de calcul que l’on dirait maintenant Turing-complet, les fonctions récursives générales, décrit dans une lettre que Jacques Herbrand lui a adressée, et qu’il a lui-même précisé et exposé en 1934. Cependant il n’est pas convaincu à l’époque d’avoir décrit ainsi toutes les fonctions calculables. À la suite de travaux de Kleene, Church, et Turing, ces deux derniers ont énoncé indépendamment en 1936 la thèse de Church : les fonctions calculables sont les fonctions récursives générales.

WPTHINGO.9 Cf. Théorèmes d’incomplétude de Gödel, Wikipédia, op. cit. : La preuve par Gödel de son premier théorème d’incomplétude utilise essentiellement deux ingrédients : le codage par des nombres entiers du langage et des fonctions qui permettent de le manipuler, ce que l’on appelle l’arithmétisation de la syntaxe ; un argument diagonal qui, en utilisant l’arithmétisation de la syntaxe, fait apparaître un énoncé similaire au paradoxe du menteur : l’énoncé de Gödel est équivalent, via codage, à un énoncé affirmant sa propre non prouvabilité dans la théorie considérée.

WPTHINGO.10 Cf. Théorèmes d’incomplétude de Gödel, Wikipédia, op. cit. : À l’époque actuelle, quiconque connait un peu d’informatique n’a aucun mal à imaginer que l’on puisse représenter les énoncés d’une théorie par des nombres. Cependant il faut également manipuler ces codages dans la théorie. La difficulté réside dans les restrictions du langage : une théorie du premier ordre avec essentiellement l’addition et la multiplication comme symboles de fonction. C’est la difficulté que Gödel résout pour montrer que la prouvabilité peut être représentée par une formule dans la théorie.

WPTHALIN Théorie algorithmique de l’information

Théorie algorithmique de l’information, Wikipédia, https://fr.wikipedia.org/wiki/Th%C3%A9orie_algorithmique_de_l%27information.

WPTHALIN.1 Cf. Théorie algorithmique de l’information, Wikipédia, op. cit. : La théorie algorithmique de l’information, initiée par Kolmogorov, Solomonov et Chaitin dans les années 1960, vise à quantifier et qualifier le contenu en information d’un ensemble de données, en utilisant la théorie de la calculabilité et la notion de machine universelle de Turing. Cette théorie permet également de formaliser la notion de complexité d’un objet, dans la mesure où l’on considère qu’un objet (au sens large) est d’autant plus complexe qu’il faut beaucoup d’informations pour le décrire, ou – à l’inverse – qu’un objet contient d’autant plus d’informations que sa description est longue. La théorie algorithmique de l’information est fondée sur cette équivalence : la description d’un objet est formalisée par un algorithme (autrement dit une machine de Turing), et sa complexité (autrement dit son contenu en information) est formalisé par certaines caractéristiques de l’algorithme : sa longueur ou son temps de calcul. Ces fondements sont différents de ceux de la théorie de l’information de Shannon : cette dernière n’utilise pas la notion de calculabilité et n’a de sens que par rapport à un ensemble statistique de données. Cependant, les deux théories sont compatibles et des liens formels entre elles peuvent être établis. Tandis que la théorie de l’information de Shannon a eu de nombreuses applications en informatique, télécommunications, traitement de signal et neurosciences computationnelles, la théorie algorithmique de l’information a été utilisée avec succès dans les domaines de la biologie, de la physique et même de la philosophie.

WPTHALIN.2 Cf. Théorie algorithmique de l’information, Wikipédia, op. cit. : L’idée principale de la théorie algorithmique de l’information est qu’une chose est d’autant plus complexe, ou contient d’autant plus d’information, qu’elle est difficile à expliquer, c’est-à-dire fondamentalement longue à expliquer.

WPTHALIN.3 Cf. Théorie algorithmique de l’information, Wikipédia, op. cit. : Ainsi, un objet sera d’autant plus compliqué qu’on ne peut le décrire plus brièvement qu’une liste exhaustive de ses propriétés… Ce dernier cas constitue le cas limite d’une complexité maximale.

WPTHEAXI Théorie axiomatique

Théorie axiomatique, Wikipédia, https://fr.wikipedia.org/wiki/Th%C3%A9orie_axiomatique.

WPTHEAXI.1 Cf. Théorie axiomatique, Wikipédia, op. cit. : Les Éléments d’Euclide sont considérés comme le premier exemple de théorie axiomatique, même si quelques axiomes étaient restés implicites. La notion moderne de théorie axiomatique s’est développée au cours du XIXe siècle et du début du XXe siècle, d’une part à cause de la découverte au XVIIe siècle du calcul infinitésimal, qui nécessitait d’autres fondements aux mathématiques que ceux des Éléments d’Euclide, d’autre part à cause du développement de la géométrie et de l’algèbre moderne (voir aussi le programme d’Erlangen).

WPTHEAXI.2 Cf. Théorie axiomatique, Wikipédia, op. cit. : Une théorie récursivement axiomatisable est une théorie qui peut être axiomatisée de façon qu’il soit possible de reconnaître de façon purement mécanique les axiomes parmi les énoncés du langage de la théorie. C’est le cas des théories utilisées pour formaliser tout ou partie des mathématiques usuelles, comme l’arithmétique de Peano ou la théorie des ensembles de Zermelo-Fraenkel. Intuitivement on demanderait même aux systèmes d’axiomes plus que cela : on doit pouvoir vérifier “sans avoir à réfléchir” qu’un certain énoncé est un axiome. C’est ce que l’on capture de façon imparfaite, en disant que cette vérification est mécanique, c’est-à-dire que l’on pourrait la confier à une machine, un ordinateur. Un ordinateur est capable de vérifications qui n’ont rien d’immédiat pour un être humain, à plus forte raison si l’ordinateur est purement théorique, telle la machine de Turing, que l’on utilise pour formaliser ces notions. […] Une condition est que les énoncés du langage de la théorie elle-même puissent être reconnus de façon mécanique, on dit que le langage est récursif. […] Un cas particulier évident de théorie récursivement axiomatisable est celui des théories finiment axiomatisables, c’est-à-dire des théories pour lesquelles on peut donner un nombre fini d’axiomes. Ainsi la théorie des groupes, la théorie des corps sont finiment axiomatisables.

WPTHEAXI.3 Cf. Théorie axiomatique, Wikipédia, op. cit. : Une théorie récursivement axiomatisable et complète est récursive (c’est-à-dire décidable au sens algorithmique).

WPTHEINF Théorie de l’information

Théorie de l’information, Wikipédia, https://fr.wikipedia.org/wiki/Th%C3%A9orie_de_l%27information.

WPTHEINF.1 Cf. Théorie de l’information, Wikipédia, op. cit. : La théorie de l’information, sans précision, est le nom usuel désignant la théorie de l’information de Shannon, qui est une théorie probabiliste permettant de quantifier le contenu moyen en information d’un ensemble de messages, dont le codage informatique satisfait une distribution statistique précise. Ce domaine trouve son origine scientifique avec Claude Shannon qui en est le père fondateur avec son article A Mathematical Theory of Communication publié en 1949. Parmi les branches importantes de la théorie de l’information de Shannon, on peut citer : le codage de l’information, la mesure quantitative de redondance d’un texte, la compression de données, la cryptographie. Dans un sens plus général, une théorie de l’information est une théorie visant à quantifier et qualifier la notion de contenu en information présent dans un ensemble de données. À ce titre, il existe une autre théorie de l’information : la théorie algorithmique de l’information, créée par Kolmogorov, Solomonov et Chaitin au début des années 1960.

WPTHEINF.2 Cf. Théorie de l’information, Wikipédia, op. cit. : L’information est un concept physique nouveau qui a surgi dans un champ technologique. Le concept théorique d’information a été introduit à partir de recherches théoriques sur les systèmes de télécommunication. L’origine de ces recherches remonte aux études entreprises dès la fin du XIXe siècle, en physique et en mathématique par Boltzmann et Markov sur la notion de probabilité d’un événement et les possibilités de mesure de cette probabilité. Plus récemment, avant la Seconde Guerre mondiale, les contributions les plus importantes sont dues à la collaboration des mathématiciens et des ingénieurs des télécommunications, qui ont été amenés à envisager les propriétés théoriques de tout système de signaux utilisé par les êtres, vivants ou techniques, à des fins de communication. À la suite des travaux de Hartley (1928), Shannon (1948) détermine l’information comme grandeur mesurable, sinon observable – car nul n’a jamais vu l’information – et celle-ci devient la poutre maîtresse de la théorie de la communication qu’il élabore avec Warren Weaver. Cette théorie est née de préoccupations techniques pratiques. La société Bell cherche à transmettre les messages de la façon à la fois la plus économique et la plus fiable. Aussi le cadre originel de la théorie est celui d’un système de communications où un émetteur transmet un message à un récepteur à travers un canal matériel/énergétique donné. Émetteur et récepteur ont par hypothèse un répertoire commun, un code qui contient les catégories de signaux utilisables. Ainsi le message codé est transmis, de l’émetteur au récepteur à travers le canal, sous forme de signes ou signaux portés par de la matière/énergie. Ainsi, le concept d’information a été l’objet d’une théorie que la postérité a choisi d’appeler “théorie de l’information” alors qu’il s’agissait, à proprement parler, d’une théorie mathématique de la communication de l’information ; or cette expression est exactement celle de Shannon et Weaver. Cette source de confusion est régulièrement rappelée dans la littérature. On dit, en pareil cas, que l’expression abrégée a été retenue par l’usage ; l’emploi du sigle TMCI clarifierait pourtant bien la situation. Cette théorie mathématique appliquée aux techniques de la télécommunication a été élaborée plus spécialement par Claude Shannon, ingénieur à la Compagnie des Téléphones Bell et reste jusqu’à nos jours la base du concept dit scientifique d’information. Cependant, cette théorie ne pourrait s’appuyer ni sur la forme matérielle/énergétique, ni sur le contenu cognitif des messages émis : leur contenu sémantique est laissé de côté, de même que leur contenant physique, pour ne s’intéresser qu’aux aspects mathématiques et communicationnels. Dans sa conception originale, la théorie de l’information de Shannon s’est limitée à analyser les moyens à mettre en œuvre dans les techniques de télécommunication pour transmettre l’information le plus rapidement possible et avec le maximum de sécurité. Elle s’est donc efforcée de développer des méthodes susceptibles de minimiser la probabilité d’erreur dans la reconnaissance du message. Une notion fondamentale sera nécessaire pour développer ces méthodes : la mesure de l’information, au sens mathématique du terme. Pour Shannon, l’information présente un caractère essentiellement aléatoire. Un événement aléatoire est par définition incertain. Cette incertitude est prise comme mesure de l’information. Une information sera donc uniquement définie par sa probabilité (I = - log p). Donc l’information est la mesure de l’incertitude calculée à partir de la probabilité de l’événement. Shannon a donc confondu la notion d’information et de mesure d’incertitude. Il faut remarquer que dans cette définition l’information est bien synonyme de mesure d’incertitude. Dans cet ordre d’idée, plus une information est incertaine, plus elle est intéressante, et un événement certain ne contient aucune information. En théorie de l’information de Shannon, il s’agit donc de raisonner en probabilité et non en logique pure. L’information de Shannon se mesure en unités binaires dites bits. Le bit peut être défini comme un événement qui dénoue l’incertitude d’un récepteur placé devant une alternative dont les deux issues sont pour lui équiprobables. Plus les éventualités que peut envisager ce récepteur sont nombreuses, plus le message comporte d’événements informatifs, plus s’accroît la quantité de bits transmis. Il est clair que nul récepteur ne mesure en bits l’information obtenue dans un message. C’est seulement le constructeur d’un canal de télécommunication qui a besoin de la théorie, et mesure l’information en bits pour rendre la transmission de message la plus économique et la plus fiable. La notion d’information d’après Shannon est nécessairement associée à la notion de “redondance” et à celle de “bruit”. Par exemple, en linguistique l’information n’est ni dans le mot, ni dans la syllabe, ni dans la lettre. Il y a des lettres voire des syllabes qui sont inutiles à la transmission de l’information que contient le mot : il y a dans une phrase, des mots inutiles à la transmission de l’information. La théorie de Shannon appelle redondance tout ce qui dans le message apparaît comme en surplus. Aussi est-il économique de ne pas transmettre la redondance. L’information chemine à travers un canal matériel/énergétique : fil téléphonique, onde radio, etc. Or, dans son cheminement, l’information rencontre du bruit. Le bruit est constitué par les perturbations aléatoires de toutes sortes qui surgissent dans le canal de transmission et tendent à brouiller le message. Le problème de la dégradation de l’information par le bruit est donc un problème inhérent à sa communication. Ici, l’idée de redondance présente une face nouvelle ; alors qu’elle apparaît comme un surplus inutile sous l’angle économique, elle devient, sous l’angle de la fiabilité de la transmission un fortifiant contre le bruit, un préventif contre les risques d’ambiguïté et d’erreur à la réception.

WPTHEINF.3 Cf. Théorie de l’information, Wikipédia, op. cit. : Très vite de multiples applications de la théorie de l’information de Shannon sont apparues dans le domaine des sciences humaines : les modèles mathématiques élaborés ont permis de préciser certains concepts utilisés couramment dans les analyses linguistiques structurales, en même temps qu’ils faisaient apparaître les limites inhérentes à ce type d’analyse et provoquaient des recherches nouvelles (en traduction automatique et en psycho-linguistique). Tandis que se développait un champ scientifique nouveau : la cybernétique. Cependant, une caractéristique majeure de la théorie de Shannon est de donner à la notion d’information (telle que définie par cette théorie) un statut physique à part entière. Effectivement, l’information acquiert les caractères fondamentaux de toute réalité physique organisée : abandonnée à elle-même, elle ne peut évoluer que dans le sens de sa désorganisation, c’est-à-dire l’accroissement d’entropie ; de fait, l’information subit, dans ses transformations (codage, transmission, décodage, etc.), l’effet irréversible et croissant de la dégradation. Par conséquent Shannon définit comme entropie d’information la mesure H (K = - K log p). De façon étonnante, l’équation par laquelle Shannon définit l’entropie de l’information coïncide, mais de signe inverse, avec l’équation de Boltzmann-Gibbs définissant l’entropie S en thermodynamique (S = - K log p). Cet épisode important a été abondamment commenté. Certains, comme Couffignal, ont soutenu que la coïncidence est sans signification : l’application de la fonction de Shannon à la thermodynamique et à l’information serait un hasard de rencontre de l’application d’une même formule mathématique, sans plus. Certes, il peut y avoir rencontre de deux équations de probabilité provenant d’univers différents. À l’inverse, Brillouin avait prétendu établir une relation logique entre le H de Shannon et le S de Boltzmann, ce que retiennent la plupart des chercheurs qui appliquent la théorie aux disciplines non mathématiques, la biologie en particulier. Selon ce point de vue, il est possible d’inscrire l’information telle que définie par Shannon dans la physique. En effet, il existe une dualité dans le concept d’information reliant l’information à la matière/énergie véhiculant cette information. L’information telle que définie par Shannon s’enracine ainsi dans la physique d’une part, dans les mathématiques d’autre part, mais sans qu’on puisse la réduire aux maîtres-concepts de la physique classique : masse et énergie. Comme le dit Wiener : “l’information n’est ni la masse, ni l’énergie, l’information est l’information”, ce qui laisse la porte ouverte à des conceptions diverses, à commencer par celle d’un troisième constituant de l’univers, après la matière et l’énergie précisément !

WPTHEINF.4 Cf. Théorie de l’information, Wikipédia, op. cit. : La théorie mathématique de l’Information résulte initialement des travaux de Ronald Aylmer Fisher. Celui-ci, statisticien, définit formellement l’information comme égale à la valeur moyenne du carré de la dérivée partielle (δ) du logarithme naturel de la loi de probabilité étudiée. […] À partir de l’inégalité de Cramer, on déduit que la valeur d’une telle information est proportionnelle à la faible variabilité des conclusions résultantes. En termes simples, moins une observation est probable plus elle est porteuse d’information. Par exemple, lorsque le journaliste commence le journal télévisé par la phrase “Bonsoir”, ce mot, qui présente une forte probabilité, n’apporte que peu d’information. En revanche, si la première phrase est, par exemple “La France a peur Ce lien renvoie vers une page d’homonymie”, sa faible probabilité fera que l’auditeur apprendra qu’il s’est passé quelque chose, et, partant, sera plus à l’écoute. D’autres modèles mathématiques ont complété et étendu de façon formelle la définition de l’information. Claude Shannon et Warren Weaver renforcent le paradigme. Ils sont ingénieurs en télécommunication et se préoccupent de mesurer l’information pour en déduire les fondamentaux de la Communication (et non une théorie de l’information). Dans Théorie Mathématique de la Communication en 1948, ils modélisent l’information pour étudier les lois correspondantes : bruit, entropie et chaos, par analogie générale aux lois d’énergétique et de thermodynamique. Leurs travaux complétant ceux d’Alan Turing, de Norbert Wiener et de John von Neumann (pour ne citer que les principaux) constituent le socle initial de la théorie du signal Ce lien renvoie vers une page d’homonymie et des “Sciences de l’Information”. […] C’est au départ le logarithme naturel qui est utilisé. On le remplacera pour commodité par le logarithme à base 2, correspondant à une information qui est le bit. Les considérations d’entropie maximale permettront à l’inférence bayésienne de définir de façon rationnelle ses distributions a priori. L’informatique constituera une déclinaison technique automatisant les traitements (dont la transmission et le transport) d’information. L’appellation “Technologies de l’Information et de la Communication” recouvre les différents aspects (systèmes de traitements, réseaux, etc.) de l’informatique au sens large. Les sciences de l’information dégagent du sens depuis des données en s’appuyant sur des questions de corrélation, d’entropie et d’apprentissage (voir Data mining). Les technologies de l’information, quant à elles, s’occupent de la façon de concevoir, implémenter et déployer des solutions pour répondre à des besoins identifiés. Adrian Mc Donough dans Information economics définit l’information comme la rencontre d’une donnée (data) et d’un problème. La connaissance (knowledge) est une information potentielle. Le rendement informationnel d’un système de traitement de l’information est le quotient entre le nombre de bits du réservoir de données et celui de l’information extraite. Les data sont le cost side du système, l’information, le value side. Il en résulte que lorsqu’un informaticien calcule la productivité de son système par le rapport entre la quantité de données produites et le coût financier, il commet une erreur, car les deux termes de l’équation négligent la quantité d’information réellement produite. Cette remarque prend tout son sens à la lumière du grand principe de Russell Ackoff qui postule qu’au-delà d’une certaine masse de données, la quantité d’information baisse et qu’à la limite elle devient nulle. Ceci correspond à l’adage “trop d’information détruit l’information”. Ce constat est aggravé lorsque le récepteur du système est un processeur humain, et pis encore, le conscient d’un agent humain. En effet, l’information est tributaire de la sélection opérée par l’attention, et par l’intervention de données affectives, émotionnelles, et structurelles absentes de l’ordinateur. L’information se transforme alors en sens, puis en motivation. Une information qui ne produit aucun sens est nulle et non avenue pour le récepteur humain, même si elle est acceptable pour un robot. Une information chargée de sens mais non irriguée par une énergie psychologique (drive, cathexis, libido, ep, etc.) est morte. On constate donc que dans la chaîne qui mène de la donnée à l’action (données → information → connaissance → sens → motivation), seules les deux premières transformations sont prises en compte par la théorie de l’information classique et par la sémiologie. Kevin Bronstein remarque que l’automate ne définit l’information que par deux valeurs : le nombre de bits, la structure et l’organisation des sèmes, alors que le psychisme fait intervenir des facteurs dynamiques tels que passion, motivation, désir, répulsion, etc. qui donnent vie à l’information psychologique.

WPTHEINF.5 Cf. Théorie de l’information, Wikipédia, op. cit. : L’une des caractéristiques fondamentales de cette théorie est l’exclusion de la sémantique. La théorie de l’information est indifférente à la signification des messages. Le sens d’un message peut pourtant être considéré comme essentiel dans la caractérisation de l’information. Mais le point de vue de la théorie de l’information se limite à celui d’un messager dont la fonction est de transférer un objet. La théorie de l’information de Shannon est toujours relative à un ensemble de données, une famille de chaînes de caractères, caractérisée par une loi de distribution bien précise. Elle donne donc un contenu en information en moyenne, ce qui en fait une théorie probabiliste, particulièrement bien adaptée au contexte de la transmission de donnée, et dans ce cadre cette théorie a produit des résultats importants. En revanche, elle n’est pas en mesure de quantifier le contenu en information d’une chaine prise isolément, un brin d’ADN par exemple, alors que la théorie algorithmique de l’information en est capable jusqu’à un certain point. Mais cette dernière théorie possède également ses propres limitations. C’est pourquoi il ne faut pas considérer que la notion d’information est entièrement cernée par la théorie de l’information de Shannon, ou la théorie algorithmique de l’information, mais que cette notion a besoin d’une variété de modélisations formelles pour s’exprimer. L’information de Fisher semble ainsi parfois avantageusement remplacer l’information de Shannon dans la mesure où elle est une quantification locale et non globale de l’information contenue dans une distribution. Cela dit, les deux notions sont liées et peuvent dans diverses applications mener aux mêmes résultats.

WPTHEENS Théorie des ensembles de von Neumann-Bernays-Gödel

Théorie des ensembles de von Neumann-Bernays-Gödel, Wikipédia, https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_ensembles_de_von_Neumann-Bernays-G%C3%B6del.

WPTHEENS.1 Cf. Théorie des ensembles de von Neumann-Bernays-Gödel, Wikipédia, op. cit. : La théorie des ensembles de von Neumann-Bernays-Gödel, abrégée en NBG ou théorie des classes, est une théorie axiomatique essentiellement équivalente à la théorie ZFC de Zermelo-Fraenkel avec axiome du choix (et avec les mêmes variantes possibles), mais dont le pouvoir expressif est plus riche. Elle peut s’énoncer en un nombre fini d’axiomes, et donc sans schéma, au contraire de ZFC (voir schéma d’axiomes de compréhension et schéma d’axiomes de remplacement). Ceci n’est possible que grâce à une modification du langage de la théorie, qui permet de parler directement de classe, une notion par ailleurs utile en théorie des ensembles et qui apparaissait déjà, de façon assez informelle, dans les écrits de Georg Cantor dès avant 1900. La théorie des classes a été introduite en 1925 par John von Neumann, mais celui-ci avait pris des fonctions pour objets primitifs. Elle est reformulée en termes de théorie des ensembles et simplifiée par Paul Bernays vers 1929. Kurt Gödel en donne une version inspirée de celle de Bernays, pour sa preuve de cohérence relative de l’axiome du choix et de l’hypothèse du continu par les constructibles, lors de conférences à Princeton en 1937-1938 (publiées en 1940).

WPTHEENS.2 Cf. Théorie des ensembles de von Neumann-Bernays-Gödel, Wikipédia, op. cit. : Cependant, bien que Gödel l’ait adoptée pour la première démonstration significative de cohérence relative, celle de l’axiome du choix et de l’hypothèse du continu, les théoriciens des ensembles préfèrent utiliser le langage de la théorie ZF : en permettant de parler d’une nouvelle notion, celle de classe, on ne peut que compliquer ce genre de preuves, où l’on raisonne sur la théorie. La théorie NBG est encore invoquée, en tant que théorie pour formaliser les mathématiques, quand on a besoin de classes propres par exemple en théorie des catégories.

WPTHEMOD Théorie des modèles

Théorie des modèles, Wikipédia, https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_mod%C3%A8les.

WPTHEMOD.1 Cf. Théorie des modèles, Wikipédia, op. cit. : La théorie des modèles est une branche de la logique mathématique qui traite de la construction et de la classification des structures. Elle définit en particulier les modèles des théories axiomatiques, l’objectif étant d’interpréter les structures syntaxiques (termes, formules, démonstrations…) dans des structures mathématiques (ensemble des entiers naturels, groupes, univers…) de façon à leur associer des concepts de nature sémantique (comme le sens ou la vérité).

WPTHEMOD.2 Cf. Théorie des modèles, Wikipédia, op. cit. : Plus tard, Hilbert fera une conférence à Paris où il donnera une signification numérique à tous les termes de la géométrie euclidienne dans le but de démontrer l’indépendance des axiomes de la géométrie euclidienne vis-à-vis des autres axiomes. Deux des pionniers de la théorie des modèles sont Leopold Löwenheim et Thoralf Skolem qui démontrent un puissant théorème d’existence de modèles de toutes sortes de “tailles” (cardinaux). Mais une étape importante de l’histoire de cette théorie est la définition de la vérité par Alfred Tarski, dans un article intitulé Le concept de vérité dans les langages formalisés, publié en 1933. Le but de Tarski est de donner une définition de la vérité en accord avec le langage courant et de préciser la théorie de la correspondance. Pour que les antinomies logiques soient évitées, il propose de définir le “vrai” et le “faux” dans un méta-langage. Par exemple, il distingue la proposition "il neige" de l’observation du fait qu’il neige effectivement dans le monde réel. Pour cela, Tarski introduit le concept de satisfaisabilité, au sens que la proposition "il neige" est satisfaite par la réalité (en tant que “modèle” de la formule) seulement dans le cas où il neige. L’objectif de cet exemple est de montrer la différence entre l’objet linguistique et son interprétation qui permet de juger la proposition. Pour ce faire, il introduit l’étude formelle de la sémantique du calcul des prédicats. Il a cependant fallu attendre les années 1950 et 60 pour que la théorie des modèles devienne une discipline à part entière. Parmi ses pionniers figurent Tarski, R. L. Vaught et M. Morley. Aujourd’hui la théorie des modèles est l’une des branches les plus importantes de la logique.

WPTHEMOD.3 Cf. Théorie des modèles, Wikipédia, op. cit. : Le théorème de complétude de Gödel assure qu’en logique classique du premier ordre, la réciproque est vraie : toute théorie non contradictoire possède au moins un modèle. Il clôt des recherches qui remontent au théorème de Löwenheim-Skolem que toute théorie (dans un langage dénombrable du premier ordre), qui a un modèle infini, a aussi un modèle de n’importe quelle cardinalité infinie.

WPTHEMOD.4 Cf. Théorie des modèles, Wikipédia, op. cit. : Une formule vraie dans tout modèle est dite universellement valide (en particulier, une tautologie en est une). Si la formule possède n variables propositionnelles atomiques, il suffit en fait de vérifier la vérité de la formule dans les 2n modèles possibles donnant les diverses valeurs de vérité aux n propositions atomiques pour prouver que cette formule est une tautologie. Le nombre de modèles étant fini, il en résulte que le calcul des propositions est décidable : il existe un algorithme permettant de décider si une formule est une tautologie ou non. Par ailleurs, le théorème de complétude du calcul des propositions établit l’équivalence entre être une tautologie et être prouvable dans un système de déduction adéquat.

WPTHEMOD.5 Cf. Théorie des modèles, Wikipédia, op. cit. : On dit d’une théorie qu’elle est catégorique si tous ses modèles sont isomorphes (rappel : deux modèles M et M’ sont isomorphes s’il existe un homomorphisme bijectif de M dans M’). L’intérêt de manipuler des théories catégoriques réside dans leur univocité : on peut dire d’elles qu’elles caractérisent véritablement les objets dont elles énoncent les lois. Tous les énoncés valides (resp. non valides) dans un modèle donné le sont également dans tout autre modèle. À l’inverse, une théorie non-catégorique a ceci de gênant qu’elle contient des énoncés vrais (resp. faux) de ses objets qui ne le sont pas nécessairement dans un autre modèle.

WPTHEMOD.6 Cf. Théorie des modèles, Wikipédia, op. cit. : Les modèles présentés jusqu’ici sont des modèles de la logique classique. Mais il existe d’autres logiques, par exemple la logique intuitionniste qui est une logique qui construit les démonstrations à partir des prémisses. Il existe pour cette logique une théorie des modèles, les modèles de Kripke avec un théorème de complétude : une formule est démontrable en logique intuitionniste si et seulement si elle est vraie dans tout modèle de Kripke.

WPTHETYP Théorie des types

Théorie des types, Wikipédia, https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_types.

WPTHETYP.1 Cf. Théorie des types, Wikipédia, op. cit. : En mathématiques, logique et informatique, une théorie des types est une classe de systèmes formels, dont certains peuvent servir d’alternatives à la théorie des ensembles comme fondation des mathématiques. Grosso modo, un type est une “caractérisation” des éléments qu’un terme qualifie. En théorie des types, chaque terme possède un type et les opérations décrites par le système imposent des restrictions sur le type des termes qu’elles combinent. La théorie des types est très liée à (et recoupe parfois) l’étude des systèmes de types qui sont utilisés dans certains langages de programmation afin d’éviter certains bugs. Cependant, historiquement les théories des types ont été introduites pour empêcher des paradoxes de la logique formelle et l’expression “théorie des types” renvoie souvent à ce contexte plus large. Deux théories des types qui émergent peuvent servir de fondations pour les mathématiques ; ce sont le λ-calcul typé d’Alonzo Church et la théorie des types intuitionniste de Per Martin-Löf. Quoi qu’il en soit, les théories des types créées par les logiciens trouvent une application majeure comme systèmes axiomatiques de la majorité des assistants de preuve du fait de la correspondance de Curry-Howard liant démonstrations et programmes.

WPTHETYP.2 Cf. Théorie des types, Wikipédia, op. cit. : D’un point de vue de la théorie mathématique : les types ont été pour la première fois théorisés par Bertrand Russell comme réponse à sa découverte du paradoxe ébranlant la théorie naïve des ensembles de Gottlob Frege. Cette théorie des types est développée dans l’ouvrage Principia Mathematica de Russell et Whitehead. Elle permet de contourner le paradoxe de Russell en introduisant tout d’abord une hiérarchie de types, puis en assignant un type à chaque entité mathématique. Les objets d’un certain type ne peuvent être construits qu’à partir d’objets leur pré-existant (situés plus bas dans la hiérarchie), empêchant ainsi les boucles infinies et les paradoxes de surgir et de casser la théorie. Pour ce qui concerne le sous-domaine des mathématiques nommé la logique mathématique – mais c’est aussi très utile dans le domaine de l’informatique, dans des sous-domaines nommés théorie des grammaires, théorie de la compilation, et système de réécriture, voire plus récemment dans le domaine de la transcompilation – on utilise les types dans le cadre de la théorie des types. Dans le langage courant, “théorie des types” est à comprendre dans le contexte des systèmes de réécriture. L’exemple le plus connu est le lambda calcul d’Alonzo Church. Sa Theory of Types a permis de passer du calcul non-typé originel, incohérent du fait du paradoxe de Kleene-Rosser, à un calcul correct. Church a démontré que ce système pouvait servir de fondement des mathématiques ; on le décrit comme une logique d’ordre supérieur. D’autres théories des types marquantes sont la théorie des types intuitionniste de Per Martin-Löf qui est utilisée comme fondement dans certaines branches des mathématiques constructivistes et pour des assistants de preuve tels que Agda ou Idris. Le calcul des constructions de Thierry Coquand et ses extensions sont utilisés notamment par Coq et Matita. Il s’agit d’une recherche active, comme le démontrent les récents développements en théorie des types homotopiques.

WPTHETYP.3 Cf. Théorie des types, Wikipédia, op. cit. : Le concept de type a plusieurs domaines d’applications : les théories des ensembles qui, suivant l’intuition de Russell, classent les ensembles en différents types ; la logique pour laquelle on cherche à donner un contenu calculatoire aux propositions et aux démonstrations par la correspondance de Curry-Howard ; la théorie des modèles, où un type est un ensemble de formules particulier ; les langages de programmation, surtout les langages fonctionnels typés ; les systèmes de démonstration sur ordinateur ; la linguistique, à travers le concept de catégorie syntaxique.

WPTURCOM Turing-complet

Turing-complet, Wikipédia, https://fr.wikipedia.org/wiki/Turing-complet.

WPTURCOM.1 Cf. Turing-complet, Wikipédia, op. cit. : En informatique et en logique, un système formel est dit complet au sens de Turing ou Turing-complet (par calque de l’anglais Turing complete) s’il possède un pouvoir expressif au moins équivalent à celui des machines de Turing. Dans un tel système, il est donc possible de programmer n’importe quelle machine de Turing. Cette notion est rendue pertinente par la thèse de Church, qui postule l’existence d’une notion naturelle de calculabilité. Ainsi, le pouvoir expressif des machines de Turing coïncide avec celui des fonctions récursives, du lambda calcul, ou encore des machines à compteurs.

WPTURCOM.2 Cf. Turing-complet, Wikipédia, op. cit. : De même qu’un modèle de calcul, un langage informatique est dit Turing-complet s’il permet de représenter toutes les fonctions calculables au sens de Turing et Church (nonobstant la finitude de la mémoire des ordinateurs).

WPTURCOM.3 Cf. Turing-complet, Wikipédia, op. cit. : Certains langages dédiés au traitement de problèmes spécifiques ne sont pas Turing-complets. […] Cependant, ces derniers sont en pratique capables de calculer tout ce qui est intéressant, en d’autres termes ils peuvent mettre en œuvre toutes les fonctions dont nous pourrions avoir besoin dans la vie pratique ; les calculs qui leur échappent, soit ont une complexité au-delà de l’imaginable et du réalisable, soit ne se terminent pas. La compilation doit alors démontrer la terminaison des programmes, ou nécessiter une interaction avec le programmeur pour certaines démonstrations, mais c’est le prix à payer pour une qualité de code qui est correct par construction.