Accueil Publimath  Aide à la recherche   Recherche Avancée   Aidez-nous à améliorer cette fiche  Vidéo d'aide
Certification IDDN Valid HTML 4.01 Transitional
Auteur(s) : Delahaye Jean-Paul

Titre : Information, complexité et hasard.
English title: Information, complexity and randomness.

Editeur : Hermès Science publications Paris, 1999 Collection : Langue Raisonnement Calcul 2e éd.
Format : 15,4 cm x 23,4 cm, 276 p. Bibliogr. p. 251-266, Index p. 267-275
ISBN : 2-7462-0026-0 EAN : 9782746200265  ISSN : 0988-0569

Type : ouvrage (au sens classique de l'édition) Langue : Français Support : papier

Public visé : élève ou étudiant, enseignant Niveau Niveau scolaire visé par l'article : master Age : 21, 22, 23

Classification : E25Métamathématique. Aspects philosophiques et éthiques des mathématiques. Épistémologie des mathématiques 

Résumé :

L'auteur essaie tout au long du livre de dégager les interactions entre le monde philosophique, intuitif et le monde mathématique. Ces interactions amènent les mathématiciens à créer de nouvelles structures (formalisations de concepts intuitifs) qui en retour éclairent le monde intuitif (celui des physiciens et des biologistes). Les supports de logique mathématique qui sont souvent utilisés sont ceux de "théorie de la démonstration (systèmes formels), théories des fonctions calculables (récursives) : thèse de Church, théorie de Kolmogorov, de Martin-Löf, théorème d'incomplétude de Gödel, théorie ZF des ensembles, conjecture "P=NP".

Le chapitre 1 présente la notion d'information, pose le problème de la connaissance rencontré par les physiciens, les biologistes (séquence du génome). On ramène les problèmes à ceux sur des suites de symboles et on essaie de trouver comment mesurer la complexité de ces suites (i.e. complexité pour connaître, calculer son n-ième élément). Après avoir parcouru les théories de l'information de Shannon et de Bennett, qu'il pense être mal adaptées aux problèmes des physiciens et des biologistes car ne les résolvant pas.

Le chapitre 2 étudie la formalisation de la notion de "suite aléatoire". Il passe en revue :
- les théories de fonctions calculables (récursives) : Church, Turing, Post, Gödel dans les années 30,
- la notion de suite infinie aléatoire au sens de Von Mises (1919),
- au sens de Kolmogorov(1965),
- au sens de Martin-Löf (1966),
- au sens de Chaitin (1975).
La thèse de Church, unanimement reconnue par les mathématiciens, propose de prendre comme définition de fonction "calculable" celle de fonction récursive. L'auteur propose de considérer que la "bonne" notion de suite aléatoire soit celle de Martin-Löf. Il étudie cependant dans le fin du chapitre d'autres approches.

Le chapitre 3 donne des classifications de la complexité des problèmes (des suites). Après avoir rappelé les définitions mathématiques des différentes notions utilisées (ensemble récursif, récursivement énumérable, approximable, compressible).il propose une classification en 5 classes disjointes.

Le chapitre 4 compare deux théories : celle de la complexité aléatoire de Kolmogorov et celle de la complexité organisée de Bennett. Il en donne les définitions, des illustrations et en étudie le bien-fondé. Il fait le lien avec la conjecture "P=NP".

Le chapitre 5 étudie les capacités d'induction d'une machine : limites et propriétés. Le chapitre est très argumenté par de nombreux exemples.

Le chapitre 6 reprend l'étude des problèmes d'indécidabilité. Il analyse d'un point de vue philosophique l'inadéquation des systèmes formels de haut niveau au monde intuitif. Il étudie en particulier le théorème de Gödel, de Ramsey, le 10ième théorème de Hilbert (résolu par Matijasevic en 70). Ce chapitre contient de nombreuses citations de logiciens contemporains sur la question.

Les chapitres 7 et 8 reviennent sur le problème de la calculabilité en physique. Il étudie la notion d'infini, de déterminisme, de discrétisation du monde, donne des variantes de la notion de récursivité Enfin il étudie la question "Le monde physique est-il récursif ?"

Le dernier chapitre 9 s'intéresse aux paradoxes sémantiques ; ce qui l'amène à fixer les limites des modélisations formelles. Il s'appuie sur la théorie ZF et la théorie des types de Russell, la théorie de la vérité de Tarski, la solution de Kripke.

Notes :
Cet ouvrage est l'objet d'une recension sous la rubrique "matériaux pour une documentation" du Bulletin de l'APMEP n° 427.
Cet ouvrage s'adresse aux étudiants en théories de l'information et de la logique correspondante et aux enseignants préoccupés des réflexions conjointes en mathématiques, informatique et philosophie.

Mots clés :


© ADIREM-APMEP -2003- ISSN 1292-8054 Mise à jour 06/10/2018
Accueil Publimath  Aide à la recherche   Recherche Avancée   Aidez-nous à améliorer cette fiche  Vidéo d'aide
Certification IDDN