Déterminisme (Calculabilité)

Le déterminisme comme notion mathématique vit le jour avec la formalisation des mathématiques à la fin du XIX^e siècle et au début du XX^e siècle et devint une notion centrale de la calculabilité avec l'apparition de la théorie des automates au milieu du XX^e siècle. L'apparition de l'informatique quantique à la fin du XX^e siècle et celle de la conception forte de la thèse de Church-Turing, baptisée thèse de Church–Turing–Deutsch (en), 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

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 synthétiques a priori. À l'époque, il était difficile de comprendre que ces propositions sont des algorithmes, 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), 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 tout 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^[1]. 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

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^[2]. Nous remarquerons que cette machine peut être toute machine réalisant une expérience scientifique déterministe^[3]. 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é

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

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

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 à ce 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

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

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^[4] ; 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)^[5]. 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^[6]. 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 N, il suffirait d'attendre que le programme réalise 2^N 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^[7] ; 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

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

• 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^[10]. 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^[11], que tout phénomène physique déterministe est calculable^[12]. 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^[13]. 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^[14]. 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é

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

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

• Portail des mathématiques