![]() Some interesting equivalence relations are known to give rise to interesting categorical structures for example, the category of primitive recursive algorithms is a universal object in the category of categories. Algorithms form a category by virtue of the fact that they are the quotient category of programs. Whatever equivalence relation we pick, this gives us some structure. beta reduction and eta conversion in lambda calculus), so we should throw those in too. ![]() Most models of programming languages have native notions of "equivalence" (e.g. For example, two programs are essentially the same if they differ only by variable renamings. There are some obvious things that we should include. The hard part in all this is trying to capture what we mean by "essentially the same thing". Similarly, there is an equivalence class between algorithms, where two algorithms are equivalent if they compute the same mathematical function. Any two programs which implement the same algorithm must compute the same function, but the converse is not true. ![]() So the best handle that we have on what an "algorithm" is, is that it's some kind of equivalence class on programs, where two programs are equivalent if they do "essentially the same thing". Each algorithm, in turn, could be implemented using different programs (even given the same programming language). ![]() This function could be implemented using different algorithms (e.g. So, for example, "sort" is a mapping between a sequence of orderable items and a sequence of orderable items of the same type, which maps each sequence to its ordered sequence. What we know is that whatever an "algorithm" is, it sits somewhere between "mathematical function" and "computer program".Ī mathematical function is formal notion of a mapping from inputs to outputs. However, there are smart people working on it. I'm going to give the same answer as I gave the previous time this question came up.įirst, understand that there is no good formal definition of "algorithm" at the time of writing.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |