Interprétations du calcul itératif clos

N. Lygeros




Dans une série d'articles minimaux par leur efficacité démonstrative (Closed Iterative Calculus, Three Generators of Minimal Writing Space Computations, Quadratic Sequential Computations et Sequential Computation of Linear Mapping on a Field) Serge Burckel a jeté les bases de ce qu'il nomme le calcul itératif clos. Cette approche qui tire sa source de préoccupations informatiques, est explicite et effective du point de vue algorithmique. Quant à sa problématique générale, elle se résume en une idée : comment calculer avec une mémoire minimale.

En considérant des recouvrements sur { 0, 1}n pour tout n, Serge Burckel a montré qu'il était possible d'effectuer des calculs sans utilisation de variables supplémentaires et que la séquence des calculs était bornée et n'utilise qu'au plus n² opérations. De plus, lorsque le recouvrement est linéaire et ce pour tout corps K, la borne est cette fois égale à 2*n. Et ce dernier résultat lui permet d'obtenir un théorème de décomposition des matrices carrées sur K. Une conséquence directe de cela offre un outil de simplification dans le domaine de l'algèbre linéaire puisque la démonstration d'une propriété sur des matrices de K = { 0, 1} peut être remplacée par celle de la propriété sur la matrice identité et sa préservation par l'addition de deux lignes.

Si nous interprétons l'ensemble de ces résultats en théorie de l'information via leur aspect cognitif nous pouvons dire que toute l'information de la solution finale est dans le problème initial. En effet l'univers du calcul étant clos et ne nécessitant pas de variables supplémentaires, ne peut être affecté par les modifications du calcul itératif. Nous sommes donc dans une situation analogue à la théorie des séquents ou la méthode de résolution dans le calcul propositionnel lorsque nous traitons une tautologie.

Une autre manière d'interpréter ces résultats, c'est de les plonger dans un cadre bien connu de leur inventeur à savoir la théorie des noeuds. Alors le problème initial devient le noeud trivial enchevêtré et la solution finale le noeud trivial. La suite des opérations n'est qu'une séquence de mouvements qui n'affecte aucunement la nature du noeud. Et nous retrouvons ainsi l'idée de l'information conservée qui montre que la mémoire initiale est suffisante puisqu'il n'est pas nécessaire de se souvenir de l'état passé pour aller à l'état futur. L'état présent comprend toute l'information. Ainsi l'entité mathématique est sa propre solution mais donnée sous la forme d'un problème.

En réalité cette idée est encore plus profonde lorsque nous l'examinons au niveau quantique. Car même s'il est vrai que cette approche serait très utile pour les calculs quantiques cela ne représente qu'un épiphénomène. L'idée de conservation d'information à toute étape de l'évolution des interactions se retrouve dans la réfutation du paradoxe EPR via les inégalités de Bell et les expériences d'Aspect. Ainsi le calcul itératif clos apparaît comme un modèle formel du comportement quantique. Sans pour autant que cela veuille dire qu'ils ont la même complexité théorique. Car l'un des buts du calcul itératif clos, c'est la recherche de la complexité minimale dans un cadre mémoire donné. Aussi cette préoccupation n'est pas nécessairement celle du monde quantique. Cependant comme le calcul quantique est fortement linéaire sur le corps des nombres complexes, il ne serait pas surprenant que le monde quantique ait un comportement analogue sans être identique. Ainsi le modèle formel qui constitue le calcul itératif clos pourrait être encore plus fondamental dans le sens où il pourrait coder la séquence des processus nécessaires à la réalisation d'une interaction quantique complexe.







free counters


Opus