Fiche du document
29 juillet 2023
- handle: 10670/1.8mwfq4
- hal: hal-04420362
- doi: 10.1093/philmat/nkad011
Ce document est lié à :
info:eu-repo/semantics/altIdentifier/doi/10.1093/philmat/nkad011
Mots-clés
Definitions of algorithms Real computation (Type-2) Turing computability BSS Abstract State Machines Recursors Numerical analysis Formalization of mathematical concepts Computational complexitySujets proches
Natural science Sciences Science of science AlgorismCiter ce document
Philippos Papayannopoulos, « On Algorithms, Effective Procedures, and Their Definitions », HAL-SHS : philosophie, ID : 10.1093/philmat/nkad011
Métriques
Partage / Export
Résumé
I examine the classical idea of 'algorithm' as a sequential, step-by-step, deterministic procedure (i.e., the idea of 'algorithm' that was already in use by the 1930s), with respect to the following themes: (a) its relation to the notion of an 'effective procedure', (b) its different roles and uses in logic, computer science, and mathematics (focused on numerical analysis), and (c) its different formal definitions proposed by practitioners in these areas. I argue that 'algorithm' has been conceptualized and used in contrasting ways in the above areas, and discuss challenges and prospects for adopting a final foundational theory of (classical) 'algorithms'.