Towards a Definition of an Algorithm. Yanofsky, N. S arXiv, math.LO, 2006.
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 that tell when two programs are essentially the same turn out to be coherence relations that give the category of algorithms the extra structure. Universal properties of the category of algorithms are given.
@Article{Yanofsky2006,
author = {Yanofsky, Noson S},
title = {Towards a Definition of an Algorithm},
journal = {arXiv},
volume = {math.LO},
number = {},
pages = {},
year = {2006},
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 that tell when two programs are essentially the same turn out to be coherence relations that give the category of algorithms the extra structure. Universal properties of the category of algorithms are given.},
location = {},
keywords = {math.CT; math.LO}}
Downloads: 0