Lambda Calculus on the reals compared to other real models of computation

Advisors

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

Description

Contrary to discrete computation, there is no Church-Turing thesis for models of computation on the reals. Various models exist: Recursive Analysis[1] that uses Turing Machines for computing reals at any precision; the General Purpose Analog Computer[2] which combines basic continuous bricks in a fashion similar to circuits; the Blum Shub and Smale model[3] which transforms the RAM-model so that it can read and store real numbers in registers; Abstract Geometrical machines[4] inspired by cellular automata… Some comparability and incomparability results between them, but none of those models is clearly the good one.

Recently, an extension of Lambda calculus was introduced by Di Ginanatonio and Edalat[5] for capturing continuous functions with the help of a Differential operator. This model presents similarity with the GPAC as differentiation is a core operator, however it also has the ability to produce non-continuous functions with a test which can only be found in the BSS model. Where this model can be placed on the map of models of real computation is hence an open question.

The goal of this internship will be to compare this Lambda Calculus with Differential (LCD) with the GPAC. Are all functions generated by GPAC definable in LCD, and conversely. For possible simulations do they preserve computing time?

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).