H2020Индивидуална стипендия2015–2017

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

„Хоризонт 2020“ — Действия „Мария Склодовска-Кюри“

Период: 2015-09-01 → 2017-08-31
Финансиране от ЕС: 200 195 €
Участници: 1
Схема: MSCA-IF-EF-ST

Линиите свързват координатора с партньорите.

Накратко на български

Алгоритмите се изследват чрез търсене на математическо определение за това кога две различни програми изпълняват една и съща задача. Това помага за по-точното разбиране на концепцията за алгоритъм и определяне на целите в бъдещите компютърни изследвания.

Този кратък обзор е генериран от изкуствен интелект

Кратко обяснение, генерирано от езиков модел по текста на CORDIS. Оригиналът е по-долу.

Резултати накратко

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.

Текст от CORDIS, на английски · Данни: CORDIS, © Европейски съюз

Цел на проекта

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

Оригинален текст от CORDIS (на английски).

Участници

KOBENHAVNS UNIVERSITET · KOBENHAVNКоординаторДания