Menu
MapConnectionsTopicsBulgariaThe Night (K-TRIO)Marie Skłodowska-CurieFor studentsFor teachersMethodologySurprise me
H2020Individual fellowship2015–2017

Walgo · What is an Algorithm? Extensional and Intensional Equivalences between Programs

Horizon 2020 — Marie Skłodowska-Curie Actions

Duration
2015-09-01 → 2017-08-31
EU contribution
€200,195
Participants
1
Scheme
MSCA-IF-EF-ST

Lines connect the coordinator with its partners.

Results in brief

What is an Algorithm? Extensional and Intensional Equivalences between Programs

Walgo focuses on the notion of Algorithms. While it is a central notion in computer science, we do not have any scientifically sound definition of an Algorithm. Starting from a re-reading of Rice's Theorem, Walgo consider an algorithm to be an equivalence class for a specific but yet unknown equivalence (the algorithmic equivalence). In order to find this specific equivalence, or at least to get clues about it, Walgo studies all equivalences between programs and uses standard mathematical tols to discover properties of this well defined set. Walgo thus hopes to shed some light on the notion of Algorithm and direct future research toward more precise goals.

Data: CORDIS, © European Union

Project objective

Programs and Functons both have a mathematically sound definition. Every programmer has an informal idea of what an Algorithm is, yet no formal definition exists and this idea is likely to differ from one person to the other. Despite their lack of definition, Algorithms are central in Computer Science. Thus, finding a correct definition is a major modern challenge.This question is not new and has already been studied by many. It is unlikely that we can close it within a two years timeframe. Yet we have identified two novel ideas to attack the problem along three tracks of increasing difficulty thus ensuring results that will drive a future long term project.The main idea is to avoid a direct confrontation with the definition of Algorithm. We consider ""being the same algorithm"" as an equivalence between programs and we study the set of all possible equivalences. This will allow the use of the full mathematical arsenal, from set and order theory to algebra and topology, and guide future researches. The second idea is to allow algorithms to be an infinite object, thus opening more possibilities.The Researchers already has a permanent Lecturer position. The fellowship will create the condition for defending the Habilitation thesis and thus reach a position of full professorship with a long term research program based on the results obtained.""

Original text from CORDIS.

Participants

  • KOBENHAVNS UNIVERSITET · KOBENHAVNCoordinatorDenmark

Links

Data: CORDIS, © European Union