Le déterminisme comme notion mathématique vit le jour avec la formalisation des mathématiques à la fin du et au début du et devint une notion centrale de la calculabilité avec l'apparition de la théorie des automates au milieu du . L'apparition de l'informatique quantique à la fin du 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

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 toutefois 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«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. : ils sont synthétiques, c'est-à-dire qu'ils accroissent la connaissance (dans le vocable de Kant) et produisent de l'information (dans le vocable de la calculabilité). 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 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 euclidienne peuvent-elles engendrer des ellipses ? Comment ces ellipses peuvent-elles naître de traitements mathématiques et correspondre à la réalité des orbites planétaires ? Kant en tire la conclusion que ceci n'est rendu 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ésBehind 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)), 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 du 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. 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 comprit 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 en revanche 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 limité à la machine et reproductible, condition sine qua non de la scientificité selon certaines acceptations épistémologiques, et il réside dans la capacité de redémarrer à tout moment la machine pour régénérer la même suite de nombresNous 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. Nous remarquerons que cette machine peut être toute machine réalisant une expérience scientifique déterministeArgument fort de la thèse de Church–Turing–Deutsch. S'il est réellement impossible de créer une machine de puissance supérieure à la machine de Turing, affirmation qui relève de la thèse de Church, soit pouvant fournir une suite de nombres qu'aucun ordinateur ne peut fournir, nous dirons que l'univers est équivalent aux machines de Turing.

Puisque l'univers est turing-complet, il obéit 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 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 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 ; 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)Robert McNaughton, Elementary Computability, Formal Languages, and Automata, Prentice Hall, 1982, chap.6, Unsolvables Problems. 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 insolubleRobert McNaughton, Elementary Computability, Formal Languages, and Automata, Prentice Hall, 1982, chap.5.5, The argument for Church's Thesis. 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 nonMing 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 ; 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éKurt Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, 1931 par Kurt Gödel en 1931, si l'univers est équivalent aux machine de Turing celui-ci est également incompletCette 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 équivalent aux machines de Turing, 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..