Presentation

Research on models of computation leads to the design of theoretical tools intended to investigate the properties of these models.

Most of these investigations require the development of notations, languages and other tools specifically tailored for the calculi themselves, their representations, the evaluation of their complexity, the analyses of their behaviour, or the verification of their validity. They also lead to the development of hardware and software tools that implement or simulate these calculi, so that they can be applied to concrete problems, based on their specificities.

This line of research is still dominated by classical models of computation such as the Turing machine, classical logic or lambda-calculus. In addition to these models, for which a lot remains to be explored, other “non-classical” models, influenced by natural phenomena noticed for instance in physics or molecular biology, are being investigated. Objects and processes from these fields have several interesting properties that can be used for the encoding of data, handling or transferring information. For example, from an algorithmic point of view, some of these objects and processes have broken the complexity barriers that hold for classical computer science, and thus broadened the class of “tractable problems”.

The CAPP group intends to become a place where both classical and non-classical computational models are designed and studied, with a focus on algorithms, programs and proofs.