Comparaison du Lambda Calcul à Différentielles avec les autre de modèles de calcul sur les réels

Encadrants

• Emmanuel Hainry , LORIA, Université de Lorraine, Nancy, France
• Romain Péchoux , LORIA, Université de Lorraine, Nancy, France

Sujet

Contrairement à la théorie de la calculabilité classique, les modèles de calcul sur les réels ne connaissent pas d’équivalent de la thèse de Church-Turing. Nous connaissons ainsi des modèles de calcul sur les réels strictement plus puissants que d’autres, ainsi que des couples de modèles incomparables entre eux. Les modèles de calcul sur les réels sont pourtant similaires à des modèles discrets, ainsi, l’analyse récursive [1] utilise des machines de Turing pour calculer à n’importe quelle précision, le General Purpose Analog Computer (GPAC)[2] combine des opérateurs réels de base en circuit, le modèle de Blum Shub et Smale (BSS)[3] transforme des machines RAM en leur permettant de lire et sotcker des réels dans les registres, les machines à signaux [4] sont une version continue des automates cellulaires… Il est difficile de d’élire un des ces modèles comme le meilleur (suivant que l’on s’intéresse à la puissance de calcul, à la réalisabilité physique, à l’élégance des résultats de complexité).

Un nouveau modèle nommé TLCD, extension du lambda calcul simplement typé, a été récemment introduit par Di Gianantonio et Edalat [5]. Ce modèle permet de définir un certain nombre de fonctions différentiables (en fait lipschitziennes) en utilisant un opérateur différentiel. Le GPAC comportant lui aussi un opérateur différentiel (ou d’intégration), un parallèle entre ces deux modèles semble possible. TLCD possède aussi un opérateur de test qui pourrait l’apparenter au modèle BSS. La question se pose donc de savoir où se modèle se place dans le monde des modèles de calcul sur les réels.

Objectif

L’objectif de ce stage sera de comparer TLCD et GPAC. Toutes les fonctions générées par GPAC sont-elles définissables dans le TLCD ? Inversement, les fonctions définies avec et sans test peuvent-elles être générées par GPAC ? Qu’en est-il du temps de calcul ?

References

1. Weihrauch, K.: Computable Analysis: an Introduction. Springer (2000).

2. Shannon, C.E.: Mathematical theory of the differential analyzer. J. Math. Phys. MIT. 20, 337–354 (1941).

3. Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer (1998).

4. Durand-Lose, J.: Abstract geometrical computation 5: embedding computable analysis. Natural Computing. 10, 1261–1273 (2011).

5. Di Gianantonio, P., Edalat, A.: A language for differentiable functions. Foundations of Software Science and Computation Structures. pp. 337–352 (2013).