Towards a definition of an algorithm
From MaRDI portal
Abstract: We define an algorithm to be the set of programs that implement or express that algorithm. The set of all programs is partitioned into equivalence classes. Two programs are equivalent if they are essentially the same program. The set of equivalence classes forms the category of algorithms. Although the set of programs does not even form a category, the set of algorithms form a category with extra structure. The conditions we give that describe when two programs are essentially the same turn out to be coherence relations that enrich the category of algorithms with extra structure. Universal properties of the category of algorithms are proved.
Recommendations
Cited in
(16)- A new perspective on intermediate algorithms via the Riemann-Hilbert correspondence
- Complexity bounds for container functors and comonads
- On a categorical approach to the study of algorithmic algebras
- Axiomatization and characterization of BSP algorithms
- The complexities of nonperturbative computations
- Zipf's law and L. Levin probability distributions
- scientific article; zbMATH DE number 1687041 (Why is no real title available?)
- A computational definition of the notion of vectorial space
- Galois theory of algorithms
- When are Two Algorithms the Same?
- Program separation and definitional higher order programming
- scientific article; zbMATH DE number 2155189 (Why is no real title available?)
- Elementary algorithms and their implementations
- scientific article; zbMATH DE number 5064388 (Why is no real title available?)
- The dependence of computability on numerical notations
- From Dyson-Schwinger equations to quantum entanglement
This page was built for publication: Towards a definition of an algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3006116)
