Déterminisme (calculabilité)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le déterminisme comme notion mathématique vit le jour avec la formalisation des mathématiques à la fin du XIXe siècle et au début du XXe siècle et devint une notion centrale de la calculabilité avec l'apparition de la théorie des automates au milieu du XXe siècle. L'apparition de l'informatique quantique à la fin du XXe siècle et celle de la conception forte de la thèse de Church-Turing, baptisée thèse de Church–Turing–Deutsch, permet de concevoir une synthèse entre le déterminisme calculatoire et le déterminisme physique promus par l'école de la physique numérique dont la proposition « it from bit » est devenu l'emblème.

Histoire[modifier | modifier le code]

Le mystère de l'existence de correspondances entre certains phénomènes naturels et des principes mathématiques fut exprimé pour la première fois au sein de l'école pythagoricienne sous la doctrine de l'harmonie des sphères. Il fallut par contre attendre Kant pour véritablement poser le problème.

La grande question de Kant posée dans son œuvre majeure qu'est «La critique de la raison pure» concerne la possibilité d'existence de propositions mathématique synthétiques a priori. À l'époque, il était impossible de comprendre que ces propositions sont des algorithmes au sens moderne tel que défini par Church et Turing[1], ils sont synthétiques, c'est-à-dire (dans le vocable de Kant) accroissent la connaissance, dans le vocable de la calculabilité ils génèrent de l'information. Ils sont pourtant a priori, c’est-à-dire antérieurs à l'expérience (dans le vocable de Kant) et ceci est fondamental. Le résultat du calcul d'un algorithme ne peut être connu avant l'expérience de la réalisation du calcul, pourtant, il existe bel et bien avant l'expérience de ce calcul. L'analyse mathématique n'est pas une astuce pour éviter la nécessité du calcul mais pour diminuer le nombre d'étapes algorithmiques nécessaires, applicable seulement à des algorithmes compressibles comme des fonctions dérivables ; il ne faudrait pas croire, comme l'origine historique de son nom le suggère, qu'elle permet de transformer une proposition analytique en proposition synthétique.

Kant fut extrêmement ébranlé par l'adéquation des équations de la physique de Newton à la réalité phénoménologique ; comment une simple loi d'inverse de la distance et la métrique de la distance euclidienne peuvent-elles générer des ellipses ? Comment ces ellipses peuvent-elles naître de traitements mathématiques et correspondre à la réalité des orbites planétaires ? Kant en arrive à la conclusion que ceci n'est possible que par l'existence de concepts a priori comme le temps et l'espace et par l'existence des concepts purs de l'entendement comme le principe de permanence de la substance et de simultanéité, permettant la reconnaissance d'objets distincts, ainsi que du principe de causalité.

Par contre, ces concepts étant pour Kant a priori (avant toute expérience et donc innés[2]), il ne peut exister de véritable correspondance entre le noumène (le monde en soi) et le phénomène (le monde perçu). Par conséquent, le temps et l'espace ainsi que la causalité n'existe que pour l'homme et ne sont pas des réalités du monde ; la mathématique, pour Kant, est un pur produit humain et la correspondance avec le monde une mise en forme humaine. Cette conception était en place jusqu'au début de XXiem siècle et laissait la question de l'extraordinaire efficacité des mathématiques ouverte pour tous ceux qui doutaient de la non réalité du temps, de l'espace et de la causalité.

La théorie de l'évolution lamarckienne puis darwinienne permet de mettre en évidence l'erreur de Kant : a priori n'est pas synonyme d'inné. En digne successeur de la chaire de Kant, Konrad Lorenz corrigea la théorie de la connaissance de celui-ci[2]. Selon Lorenz, les concepts a priori de l'entendement comme la représentation centrale de l'espace et de la causalité furent forgés par le mécanisme de la sélection naturelle via la confrontation de la réalité avec les comportements des animaux ; la sélection naturelle ayant favorisé les organismes aptes à se représenter le mieux possible l'espace et les autres concepts a priori. Les notions d'inné et d'a priori ne sont donc plus compatibles, les concepts a priori étant le résultat de la confrontation, via l'expérience, des animaux avec la réalité tangible. Cette expérience n'étant pas réalisée par les organismes au cours de leur existence personnelle mais par la sélection naturelle au cours de l'évolution du vivant.

Si Kant compris que le temps, l'espace, la possibilité de distinguer des objets et la causalité sont nécessaires à l'existence de la mathématique, comment ceux-ci s'agencent pour permettre à la calculabilité d'émerger fut par contre compris beaucoup plus tard avec l'apparition de la théorie des automates.

Les lois du déterminisme[modifier | modifier le code]

La théorie des automates permis de clarifier les conditions nécessaires et suffisantes pour qu'un système puisse posséder la puissance de la machine de Turing, soit les différents attributs d'un système déterministe.

Dans le cas particulier d'un automate, le déterminisme doit être local et expérimentalement répétable, condition sine qua non de la scientificité, et il réside dans la capacité de redémarrer à tout moment la machine pour régénérer la même suite de nombres[3]. Nous remarquerons que cette machine peut être toute machine réalisant une expérience scientifique déterministe[4]. S'il est réellement impossible de créer une machine de puissance supérieure à la machine de Turing, soit pouvant fournir une suite de nombres qu'aucun ordinateur ne peut fournir, nous dirons que l'univers est turing-équivalent. Puisqu'il est possible de créer des ordinateurs dans l'univers, celui-ci est au moins turing-complet ; il en est bien évidemment de même pour l'humain qui est bel et bien capable d'exécuter un algorithme.

Puisque l'univers est turing-complet il obéit, localement, d'une façon quelconque à ces principes, reflétant la hiérarchie de Chomsky.

Le principe de causalité[modifier | modifier le code]

Ce principe qui exprime que l'état du système est strictement déterminé par son état antérieur ne permet, à lui seul, que de générer un ensemble de nombres si pauvre qu'il est généralement omis (grammaire à choix finis). Un automate ne tenant compte que de ce principe n'est qu'un enchaînement de changements d'états. Dans l'univers c'est le temps qui permet un tel enchaînement et, de façon plus forte, il n'est lui-même qu'un enchaînement de changement d'états.

Le principe cognitif[modifier | modifier le code]

Ce principe permet au système de «reconnaître» certains éléments et de changer d'état en fonction de cette reconnaissance. Il doit exister au moins deux types d'éléments distincts et reconnaissables pour que le principe soit applicable ; ceux-ci sont généralement symbolisés par l'alphabet binaire {0,1}. Un système possédant ce principe supplémentaire possède la puissance des automates finis. Traditionnellement, c'est l'existence de la force qui permet les interactions permettant à l'univers d'obéir à ce principe.

Le principe de mémorisation[modifier | modifier le code]

Le système ne doit pas être simplement en mesure de reconnaître un élément mais également d'en générer (mémoriser) dans un ordre fixe, soit de les positionner de manière à ce qu'ils soient énumérables. Si le principe cognitif est destructif et le fait de «reconnaître» l'élément le détruit, le système possède la puissance des automates à pile, dans le cas contraire celui des machines de Turing finies. Dans l'univers, c'est l'espace qui offre le support à la mémorisation, permettant de disposer la matière de façon que les objets soient énumérables. Toutes les interactions entre objets dans l'univers sont non-destructifs ; les invariants sont conservés.

Le principe de finitude[modifier | modifier le code]

Si le système possède une mémoire infinie et que le temps n'est pas une contrainte, le système génère les langages récursivement énumérables.


L'indécidabilité ou petite incomplétude[modifier | modifier le code]

La non-prédictibilité de certains systèmes physiques fut formellement démontrée en 1936 par Alan Turing dans l'article fondateur de la science informatique[5] ; un type particulier de système physique, l'ordinateur, est formellement imprédictible s'il possède une mémoire infinie. Il y démontre qu'il ne peut exister de programme pour un ordinateur permettant de déterminer si un autre programme s'arrêtera ou continuera de s'exécuter éternellement (problème de l'arrêt)[6]. Il y démontre également que l'ordinateur constitue une base formelle à la calculabilité (thèse de Church-Turing) et donc qu'aucune théorie mathématique ne pourra un jour trouver une solution à ce problème qui est formellement insoluble[7]. Historiquement, il s'agit d'une réponse au troisième problème d'Hilbert le entscheidungsproblem.

Dans le cas des ordinateurs à mémoire finie de taille , il suffirait d'attendre que le programme réalise opérations d'écriture en mémoire pour déterminer qu'il ne s'arrêtera jamais. Par contre, si le programme s'arrête, il s'arrêtera avant tout programme essayant de déterminer s'il s'arrête ou non[8] ; la prédictibilité ne nécessite pas seulement de pouvoir calculer le résultat mais également de le faire avant que celui-ci ne survienne.

L'incomplétude[modifier | modifier le code]

L'incomplétude de tout système formel fut démontré[9] par Kurt Gödel en 1931, si l'univers est turing-équivalent celui-ci est également incomplet[10].

  • La thèse de Church-Turing postule qu'il est impossible de concevoir une machine créant une suite de nombres qu'une machine de Turing (ordinateur) ne saurait créer[11]. Ce postulat est indépendant des phénomènes physiques utilisés pour concevoir la machine ; il implique, dans sa forme généralisée baptisée thèse de Church–Turing–Deutsch[12], que tout phénomène physique déterministe est calculable[13]. Dans sa forme restreinte, il ne concerne que la puissance de calcul des hommes, c'est-à-dire, leur limite de capacité cognitive de construction d'un calculateur[14]. Puisque la construction d'un calculateur plus puissant que la machine de Turing semble nécessiter des propriétés physiques exceptionnelles que l'univers ne possède pas (voir hypercalcul), ceci est un argument fort en faveur de l'hypothèse qu'il s'agisse d'une contrainte universelle et non d'une limitation des capacités cognitives humaines.
  • La théorie des automates garantit qu'il existe seulement quatre niveaux de machines constructibles, pouvant créer (ou accepter) des ensembles de nombres imbriquées, les machines supérieures pouvant créer tous les nombres des machines inférieures[15]. Nous remarquerons qu'il existe un nombre indénombrable d'ensembles de nombres et qu'il pourrait donc exister également un nombre indénombrable de types d'automates ; l'univers est extrêmement parcimonieux en cette matière.

L'incompressibilité[modifier | modifier le code]

L'incomplétude est difficile à imaginer pour une suite finie de nombres, en effet, il est toujours possible de créer un algorithme générant cette suite finie. Par contre, concevoir un algorithme plus petit (codé avec moins de bits) que la suite elle-même n'est possible que pour un ensemble très restreint de suites de nombres. La complexité de Kolmogorov (nommée d'après le mathématicien Andreï Kolmogorov), est une mesure de cette compressibilité de l'information.

Le succès de la physique tient à sa capacité à simplifier des phénomènes complexes jusqu'à les faire tenir en une petite équation. Par exemple, il est possible de modéliser l'attraction gravitationnelle entre deux corps en combinant les attractions individuelles de chacun des atomes constituants les corps et en ne considérant que le centre de masse résultant. Malheureusement, ce principe de compression de l'information ne s'applique pas pour tous les phénomènes, certains algorithmes sont incompressibles.

L'information[modifier | modifier le code]

Le principe cognitif permet de définir l’information comme ce qui permet le changement d’état d’un automate ou, de façon équivalente, l'existence d'un phénomène déterministe. Le principe de mémorisation comme une disposition quelconque d'éléments dans l’espace (la forme) comme, par exemple, une séquence quelconque de symboles réalisés par un automate ou, de façon équivalente, le produit d'un phénomène déterministe.

Cette vision duale de l’information est le reflet de la vision duale de l’automate à la fois accepteur de langage et générateur de langage. La notion d’ordre peut être définie comme étant la complexité algorithmique nécessaire pour générer une suite de symboles, le désordre optimal comme une suite incompressible ou, de manière équivalente, au résultat d’un phénomène non déterministe.

Notes et références[modifier | modifier le code]

  1. «On est sans doute tenté de croire d'abord que cette proposition 7 + 5 = 12 est une proposition purement analytique qui résulte, suivant le principe de contradiction, du concept de la somme de 7 et de 5... La proposition arithmétique est donc toujours synthétique...Les principes de la géométrie pure ne sont pas davantage analytiques.», Critique de la raison pure, Introduction, V - B 15 sq. Trad. Barni.
  2. a et b Behind the Mirror : A Search for a Natural History of Human Knowledge (1973) ; (orig.: « Die Rückseite des Spiegels. Versuch einer Naturgeschichte menschlichen Erkennens », 1973) ; L'envers du miroir : Une histoire naturelle de la connaissance, Flammarion, Paris (1975)
  3. Nous utilisons la version générateur de langage et non pas accepteur de langage à des fins pédagogiques. Il en est de même de la notion de suite de nombres, plus intuitive que «mot» et «langage». Voir Robert McNaughton, Elementary Computability, Formal Languages, and Automata, Prentice Hall, 1982, p.4,6,24,280,310
  4. Argument fort de la thèse de Church–Turing–Deutsch
  5. Alan Turing, « On Computable Numbers, with an Application to the Entscheidungsproblem », Proceedings of the London Mathematical Society,‎ (ISSN 0024-6115 et 1460-244X, DOI 10.1112/PLMS/S2-42.1.230, lire en ligne)Voir et modifier les données sur Wikidata et « [idem] : A Correction », Proc. London Math. Soc., 2e série, vol. 43,‎ , p. 544-546 (DOI 10.1112/plms/s2-43.6.544, lire en ligne)
  6. Robert McNaughton, Elementary Computability, Formal Languages, and Automata, Prentice Hall, 1982, chap.6, Unsolvables Problems
  7. Robert McNaughton, Elementary Computability, Formal Languages, and Automata, Prentice Hall, 1982, chap.5.5, The argument for Church's Thesis
  8. Ming Li,P. M. B. Vitányi, An introduction to Kolmogorov complexity and its applications, 1.7.2 Undecidability of the halting problem, Springer Science+Business Media, 2008
  9. Kurt Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, 1931
  10. Cette condition n'est pas nécessaire cela fut démontré par Alan Turing dans «Systems of logic based on ordinals», Proc. London math. soc., no.45, 1939. Si un système réalise un ensemble dénombrable de calculs non turing-calculables bien que non turing-équivalent, il demeure incomplet. Bien que les lois physiques ne semblent pas nécessiter de calcul non turing-calculable, il est possible que ce soit le cas comme la transformation de Lorenz quantique qui semble nécessiter un nombre infini de q-bits (voir The universe is probably not a quantum computer) par Moshe Rozali professeur associé du département de physique et d'astronomie de l'université canadienne de la Colombie Britannique.
  11. Robert McNaughton, Elementary Computability, Formal Languages, and Automata, Prentice Hall, 1982, chap.5, Gödel Numbering and Church's Thesis
  12. David Deutsch,Quantum theory, the Church–Turing principle and the universal quantum computer, Proceedings of the Royal Society (London) (400): 97–117, 1985
  13. Il serait également possible de séparer la conception généralisée faible concernant uniquement notre capacité physique de conception d'un ordinateur de la conception forte, pronant que l'univers est isomorphe à une machine de turing, position défendue par la physique numérique et résumée par la désormais célèbre formule «It from Bit» de John Wheeler, voir : Jaynes, E. T., Information Theory and Statistical Mechanics, Phys. Rev 106: 622, 1957
    Jaynes, E. T., 1957, Information Theory and Statistical Mechanics II,, Phys. Rev. 108: 171, 1957
    John Wheeler, Hermann Weyl and the Unity of Knowledge, 1986
    Jaynes, E. T.,Probability Theory as Logic dans Fougere, P.F., ed., Maximum-Entropy and Bayesian Methods, Boston: Kluwer
    Voir Fredkin's sur Digital Philosophy web site.
    Stephen Wolfram, website A New Kind of Science, Reviews of ANKS
    Gerard 't Hooft, Quantum Gravity as a Dissipative Deterministic System, Class. Quant. Grav., 16: 3263-79, 1999
    Seth Lloyd, The Computational Universe: Quantum gravity from quantum computation
    Juergen Schmidhuber, Computer Universes and an Algorithmic Theory of Everything
    David Deutsch, Paola Zizzi, Spacetime at the Planck Scale: The Quantum Computer View
    Johannes Koelman, It from bit: how to get rid of dark energy
    Michael S. Turner, Dark Energy and the New Cosmology
    Erik Verlinde, On the Origin of Gravity and the Laws of Newton, 2010
  14. Forme originale de la thèse, voir thèse de Church-Turing
  15. Daniel I.A. Cohen, Introduction to computer theory, John Wiley & Sons, Inc., 1986, chap.30, The Chomsky Hierarchy