El-Found

Équations diophantienne indécidabilité et omega

De nombreux travaux ont été effectués à partir de la preuve de Gödel, et ceux-ci ont montré que les problèmes ayant trait à la calculabilité sont équivalents aux problèmes arithmétiques sur les nombres entiers. Plusieurs noms viennent à l'esprit. Julia Robinson, Hilary Putnam et Martin Davis ont réalisés des travaux parmi les plus importants et le résultat fondamental a été trouvé en 1970 par Youri Matyassevitch. Il a construit une équation diophantienne, c'est-à-dire une équation algébrique qui met en œuvre uniquement des nombres entiers et un certain nombre de variables. Une de ces variables, appelons-la K, joue le rôle d'un paramètre. C'est une équation polynomiale avec des coefficients entiers et toutes les inconnues doivent également être des nombres entiers ; voilà la définition d'une équation diophantienne. Comme déjà dit, l'une de ces inconnues est un paramètre, et l'équation de Matyassevitch possède une solution pour une valeur particulière du paramètre K si et seulement si le Kième programme d'ordinateur s'arrête. Matyassevitch a montré en 1970 que ce problème est équivalent à celui de décider si un programme quelconque s'arrête. Le halting problem de Turing est donc exactement aussi difficile que le dixième problème de Hilbert. Il est rigoureusement aussi difficile de décider si un programme quelconque s'arrêtera que de décider si une équation diophantienne quelconque possède une solution. Il n'existe par conséquent aucun algorithme qui permette de réaliser cela, et ainsi, le dixième problème de Hilbert ne peut pas être résolu; tel est le résultat obtenu par Matyassevitch en 1970

Chaïtin est parvenu à une équation diophantienne exponentielle possédant un paramètre. L'expression "équation diophantienne exponentielle" signifie simplement que les variables peuvent être des exposants. C'est une différence avec Matyassevitch qui a montré que le dixième problème de Hilbert n'est pas résoluble en se servant d'équations diophantiennes polynomiales, ce qui signifie que les exposants y sont toujours des nombres entiers naturels constants. Chaïtin autorise quant à lui des expressions telles que XY. On ne sait pas encore si cela est véritablement nécessaire. Il se pourrait que l'on puisse arriver à un résultat similaire avec une équation diophantienne polynomiale. C'est une question ouverte, 'elle n'a pas encore été réglée. Pour l'instant, il a obtenu une équation diophantienne exponentielle possédant dix-sept mille variables. Cette équation tient sur deux cent pages et une des variables est un paramètre.

Il s'agit d'une équation où chaque constante est un nombre entier naturel et où toutes les variables sont également des nombres naturels positifs (autrement dit, ce sont des entiers non-négatifs). L'une de ces variables est donc un paramètre, et l'on peut modifier la valeur de ce paramètre qui peut être égal à 1, 2, 3, 4, 5, etc. On se demande alors si cette équation possède un nombre fini ou infini de solutions. L’équation est construite de telle manière qu'elle a un nombre fini de solutions si un bit particulier de Oméga vaut 0, et elle a un nombre infini de solutions si ce bit est égal à 1. Décider si, pour chacun des cas particuliers, cette équation diophantienne exponentielle possède un nombre fini ou infini de solutions est donc exactement identique à la détermination d'un bit spécifique de la probabilité d'arrêt :

0 < = p s’arrête 2 -p < 1

Chaïtin a construit cette équation de deux cent pages de telle façon qu'elle possède un nombre fini ou un nombre infini de solutions en fonction de la valeur 0 ou 1 d'un certain bit de la probabilité d'arrêt Oméga. Lorsque l'on varie le paramètre de cette équation, on obtient chacun des bits de Oméga. L'équation de Matyassevitch est construite de telle sorte qu'elle possède une solution si et seulement si un programme particulier s'arrête. Et lorsque l'on varie le paramètre de l'équation de Matyassevitch, on obtient tous les programmes d'ordinateurs.

L'équation de Matyassevitch fournit N questions arithmétiques qui possèdent une réponse de type oui/non et produit seulement log N bits d'information algorithmique. L’équation de Chaïtin conduit à N questions arithmétiques qui possèdent également une réponse de type oui/non ; elle génère par contre une information mathématique irréductible et incompressible

 

Comment ? De l’incomplétude partout !

Ici nous sommes face à une question mathématique simple: quelle est la valeur de chaque bit de  ? Est-ce que le premier bit est 0 ou 1, est-ce que le second bit est 0 ou 1 est-ce que le troisième bit est 0 ou 1… Mais les réponses n’ont pas de structures et ressemblent aux jets indépendants d’une pièce de monnaie non-faussée, bien que chaque réponse soit bien définie mathématiquement, parce que c’est le bit spécifique d’un nombre réel spécifique

En fait nous n’en saurons jamais rien : ici nous n’avons que la version des jets indépendants d’une pièce de monnaie de Chaïtin.

Même si on connaissait tous les bits de rangs pairs de cela n’aiderait le moindre du monde à déterminer les bits de rangs impairs.

Et si on connaissait le premier million de bits de ,ce million d’informations supplémentaires ne permettrai pas plus d’obtenir la valeur du bit suivant.

Cela ressemble vraiment aux jets indépendants d’une pièce de monnaie, c’est maximalement aléatoire et ça a une entropie maximale.

Les physiciens sont souvent à l’aise avec l’aléatoire mais il revient en fait au noir ou blanc des mathématiques pures de Hilbert.

Ici nous avons autre chose.

Chaque bit est très précisément défini.

C’est soit 1 soit 0 .

Parce est un nombre réel spécifique dès que l’on a fixé la machine ou le langage de programmation.

La situation est si rigoureusement équilibrée entre la valeur 1 et la valeur 0 qu’il ne faut plus penser en terme de blanc ou noir pour chaque bit.

Traditionnellement si quelque chose est vraie c’est à cause d’une certaine raison, en mathématique quelque chose de vraie est appelé une preuve et le travail des mathématiciens est de rechercher les preuves et donc de rechercher les raisons qui font que quelque chose est vraie.

Mais les bits de que ce soit 0 soit 1 sont des vérités mathématiques qui sont vraies sans raison

Elles sont vraies par comme accident !

En d’autres mots, ce n’est pas seulement que Hilbert ait été légèrement dans l’erreur. Ce n’est pas que quelque chose soit légèrement faux et qu’il y ait quelques trous dans les idées mathématiques normales et qui sont des cas dégénérés comme « cette proposition est non-démontrable.

Ce n’est pas cela .

C’est pire !

Il y a des cas extrêmes où des vérités mathématiques n’ont pas de structures du tout où nous sommes face à l’inconnaissance maximale.

On a des vérités mathématiques juxtaposées, indépendantes à la manière dont les jets d’une pièce de monnaie peuvent être indépendants.

Une série d’assertions dont les vérités sont sans liens possibles.

Des vérités sans causes.

Comme par accident.

 

Résumons tout cela

Avec Gödel l’incomplétude est une surprise, il n’existe pas d’ensemble fini d’axiomes pouvant contenir toute la vérité mathématique.

Avec Turing , l’incomplétude apparaît plus naturelle.

Avec Chaïtin, en considérant la taille des programmes, l’incomplétude est inévitable.

 

Voyons comment reformuler donc que la découverte de Gödel est somme toute normale et naturelle.

Physique et indécidabilité

On sait que Newton Da Costa et Francisco Doria [« Undecidability and Incompletness in Classical Mechanics » . International Journal of Theoretical Physics, 30 (1991)] ont été capable de prouver l’existence de l’indécidabilité dans des théories physiques comme la théorie classique de l’électromagnétisme, la théorie du chaos, la physique quantique et les théorie de dite de jauge et mêm la théorie au bon comportement qu’est la mécanique classique .Leur preuve a été établie à partir d’un résultat de Richardson, qui a montré l’existence de propositions indécidables sur les fonctions à valeurs réelles, résultat qui provient d’ailleurs du célèbre théorème de Davis, Matijasevic, Robinson qui établit l’indécidabilité de l’équation de Diophante à coefficient entiers que nous avons déjà cité dans le cadre des travaux de Chaïtin.

Sont classées comme indécidables par Newton Da Costa et Francisco Doria les questions suivantes :

1.      Est-ce qu’il existe un algorithme général pour décider si un Hamiltonien donné représente une particule singulière libre ou un oscillateur harmonique ?

2.      Étant donné un Hamiltonien h, est-ce qu’il existe un algorithme capable de nous dire si l’Hamiltonien Ha du système dynamique associé est intégrable ou pas ?

3.      Étant donné un Hamiltonien h tel que Ha puisse être intégré par des quadratiques, peut-on trouver une transformation canonique adéquate pour cette intégration ?

4.      Peut-on vérifier algorithmiquement si un ensemble arbitraire de fonctions est un ensemble d’intégrales premières pour un système Hamiltonien.

Newton Da Costa et Francisco Doria ont construit une correspondance comme une sorte pont entre une algèbre de fonctions réelles bien définies et les polynômes qu’ils ont d’ailleurs appelé « Foncteur de Richardson » et qui a permis de la translation des propriétés d’indécidabilité des équations de Diophante dans le langage des fonctions élémentaires qui coïncide avec l’analyse réelle classique.

Une expression correspondant au problème de l’arrêt de Turing peut alors être explicitement et algorithmiquement construite en n’utilisant exclusivement que des élément de l’analyse c’est à dire des fonctions élémentaires, des intégrales, des dérivées.

D’autres chercheurs [Karl Svozil, Calude …]arrivent aux mêmes conclusions d’indécidabilité en utilisant une transduction des phénomènes de la physique par le calcul (l’expérience physique est vue à travers une certaine équivalence avec une simulation en machine.)

C’est un constat via le calcul et cela nous semble reposer plutôt sur une position de principe mécaniste que Bruno Marchal a su dans thèse[] analyser par rapport à la position cognititiviste

Physique mesure et problème

Une première façon serait de faire appel à l’idée physique qu’on se fait de l’aléatoire où l’aléatoire se trouve associé à ce qui n’est pas significatif (en se rappelant que ce qui est significatif en physique est ce qui a trait à la mesure - que cette mesure soit directe ( sans relais de déduction) ou indirecte (avec relais de déduction)

Dans le processus de mesure directe, l’expérimentation sur le réel est ramenée à des protocoles rigoureux où certains paramètres sont contrôlés et astreints à un invariance complète si cela est possible ou à une invariance relative et il existe une relationnelle généralement simple liant les paramètres de contrôle à partir de laquelle on peut déduire complètement les valeurs globales et séparées de chacun des paramètres liés à partir d’une valeur locale de ces paramètres qui correspond à un choix unique du point temporel où se fera la mesure des valeurs de départ de ces paramètres liés.

 

Idéalement, il est supposé possible d’associer au réel un espace abstrait non nécessairement constructible (i.e. simulable par des processus finis et des ressources finies) capable d’instancier des images cohérentes du réel. A paramètres fermés et contrôlés, cette instanciaton porte généralement sur la prévision du comportement du ou des paramètres laissés libres dans l’espace de modélisation. L’inconnu peut porter sur l’espace lui même, ses dimensions, sa topologie, la possibilité ou non- d’admettre des sous-espaces ou des fermetures de sous-espaces dotés de propriétés d’invariance locales et/ou globales susceptible de formaliser des prédictions globales vraies à partir d’informations locales observées.

C’est le cas quand, par exemple où à partir de l’observation des caractéristiques attachées à un seul point matériel à un instant donné (conditions initiales) on se donne une théorie pour pouvoir décrire de proche en proche toute sa trajectoire à l’avance que l’on puisse valider par la confrontation avec les observations et mesures que l’on peut faire en n’importe quel instant ultérieur au point de départ (qui lui coïncide par définition) de la trajectoire réelle du point matériel.

Il faut aussi signaler que pour les physiciens l’univers reste égal à lui même (il n’y a pas de surgissement de matière supplémentaire du néant) d’où il découle des principes de conservation de base que tout bon modèle doit être capable de rendre.

Par analogie avec l’automatique, on peut parler d’état initial pour désigner l’observation ou la donnée des conditions initiales, atteindre un état final spécifié à l’avance définie une trajectoire qui avait été prévue. On peut dire que le problème en physique est essentiellement la détection de phénomènes physiques dont une information locale est généralement possible à obtenir et dont des comportements de type globaux ne sont déductibles d’aucun des modèles connus de la physique actuelle.

L’impossibilité, même au plan conceptuel, de contrôle du comportement de ces phénomènes en découle.

Avec ce critère, on voit que la physique connaît d’innombrables incomplétudes.

Citons les irruptions volcaniques et les phénomènes météorologiques impressionnants mais aussi plus modestement par exemple la trajectoire d’une goutte d’eau dans l’atmosphère. La prévision dans ces domaines s’appuie sur des inférences de type stochastique et dont les résultats restent bien entendu de type stochastiques.

 

Les présupposés de la démarche en physique et la mesure

Alors que dans le processus de mesure directe la prévision est directement déduite d’un modèle d’observation et d’un modèle de déduction couplés représentables en même temps directement (il est possible de concevoir des protocoles d’expérimentation à l’avance où on isole l’évolution d’un paramètre et ce sont bien des valeurs qui seront recueillies en tant que résultats de l’expérimentation et qui seront confrontées aux valeurs prévues), dans les mesures indirectes la mesure découle à la fois de l’évolution d’un ou de plusieurs paramètres et utilise des formules supposées vérifiées par ces paramètres. C’est une expérimentation contenant en imbrication une des expérimentations virtuelles dont les sorties sont des dépendances fonctionnelles des entrées; c’est une expérimentation qui capitalise l’acquis et est donc plus complexe dans la mesure où elle contient virtuellement des prédictions potentielles supposées valides. Le champ des inconnues englobe alors les lois physiques elles-mêmes introduisant une récursivité cruciale dans la démarche de la physique.

Le couple binaire traditionnel de la démarche, Problèmes, Solutions avec les sous-phases respectives d’éclatements des problèmes en sous-problèmes et de recompositions de solutions en solutions s’enrichit d’un élément ternaire médian ayant les caractéristiques à la fois des solutions et des problèmes et que l’on peut dénommer Solution-inverse et qui signifie en raccourcis :quel est le (ou la classe de ) problème qui correspond aux solutions (construites ou reconstruites)que j’observe.

La démarche traditionnelle guidant l’inférence en physique passe de l’oscillation binaire entre le connu et l’inconnu à un cycle ternaire intégrant un nouvel état hypothétique entre le connu et l’inconnu.

Il correspond alors des protocoles d’expérimentations plus complexe à réaliser dans la mesure où c’est la loi elle-même qui peut-être une variable dont il faut au préalable identifier les paramètres et le type de liaison fonctionnelle. Il y a interaction entre le modèle et les liaisons supposées entre les paramètres . La validation maximale étant requise, des techniques de filtrage utilisant les mesures expérimentales et le modèle sont nécessaire pour la construction effective d’une solution.

Cette imbrication exige alors une pertinence à-priori de la mesure.

 

Stabilité et pertinence de l’indicateur de mesure

Bien sûr la valeur de mesure permet de comparer et en général de hiérarchiser ,mais

la principale garantie de la fiabilité de la mesure repose sur le principe de la possibilité de sa réplication à l’infini qui consiste à obtenir la même valeur à chaque fois que la même expérimentation est effectuée donc, même et y compris si on refait cette expérimentation une infinité de fois, on doit obtenir une population infinie de valeurs stables autour d’une même valeur centrale qui indiquera la mesure . (On peut remarquer que la valeur représentant la mesure peut tout à fait être non-numérique pourvu que l’on puisse y déduire un certain ordre )

Cette population infinie de mesures idéalement est constituée donc d’un même nombre répété à l’infini. Dans la pratique cette population est représentée par une sous-population finie de mesures

Car on ne peut pas faire une même expérimentation une infinité de fois. De plus n’importe quel élément de la sous-population est sensé représenter la mesure. On s’attend à une constante comme élément répété à l’infini dans ce champ potentiel correspondant à la mesure d’une expérimentation idéalement répétée une infinité de fois. Des valeurs différentes dans le champ disqualifieraient la mesure qui à son tour remet en cause les conditions de l’expérimentation et peut-être même sa conception.

Ces valeurs différentes rendent donc non-représentif un élément quelconque de ce champ potentiel qui par définitif ne contient que des éléments représentatifs de la mesure de la même expérimentation.

Ne pas obtenir les mêmes résultats pour une même expérimentation, quand on la refait un nombre indéfini de foi, rend donc toute mesure faite non-significative.

Maintenant, il faut tenir compte à la fois qu’en pratique on ne peut refaire une même expérimentation une infinité de fois et que non plus on peut espérer réaliser l’égalité absolue et rigoureuse de toues ces expérimentation que l’on refait. Dans la pratique physique, Il faudra se contenter de sous-populations finies d’expérimentations et Il y aura donc des écarts entre les valeurs de mesure.

L’écart entre la plus grande valeur de la sous-population et la plus petite valeur va servir à définir une erreur de mesure qui donc idéalement pour que la mesure soit fiable au maximum doit être nulle. Car cette nullité traduit un phénomène de stabilité qui signifie qu’à chaque fois qu’une même expérimentation a été refaite la mesure obtenue a donné le même nombre. Dans la pratique, donc parce qu’on ne peut pas faire absolument et rigoureusement la même expérimentation, on s’attendra à une erreur petite. La petitesse étant une notion relative, il est bon de la ramener à l’échelle de la mesure elle-même. Autrement dit définir l’empan de crédibilité de la mesure par la mesure elle-même. Par exemple si l’erreur est de la taille de la mesure elle-même et si on l’accepte, on accepte aussi du coup 0 comme représentant de cette mesure par définition même de l‘erreur .

Ceci donc disqualifie toutes les mesures dont les erreurs et les éléments sont de même taille.

Les mesures seront dite non-significatives car les variations dans le champ sont trop importantes et sont équivalentes à des valeurs tirés au hasard sans avoir fait l’expérimentation.


Suite de l'article