principleModerate
Computer Program vs. Algorithm
Viewed 0 times
algorithmprogramcomputer
Problem
It's said that a program include algorithms, however if we refer to their definition, an algorithm is a sequence of instructions written to perform a specified task and
a computer program is also a sequence of instructions to perform a (some) tasks with computer.
Then what makes a program different from an algorithm? is it a type of algorithm too?
In fact, I look for formal definitions for an algorithm and a computer program so I can distinguish them from each other or identify algorithms within a program.
Update:I have noticed in Wikipedia by an informal definition (at least syntactically) any program is an algorithm.
An informal definition could be "a set of rules that precisely defines a sequence of operations." which would include all computer programs, including programs that do not perform numeric calculations. Generally, a program is only an algorithm if it stops eventually.
a computer program is also a sequence of instructions to perform a (some) tasks with computer.
Then what makes a program different from an algorithm? is it a type of algorithm too?
In fact, I look for formal definitions for an algorithm and a computer program so I can distinguish them from each other or identify algorithms within a program.
Update:I have noticed in Wikipedia by an informal definition (at least syntactically) any program is an algorithm.
An informal definition could be "a set of rules that precisely defines a sequence of operations." which would include all computer programs, including programs that do not perform numeric calculations. Generally, a program is only an algorithm if it stops eventually.
Solution
I'm going to give the same answer as I gave the previous time this question came up.
First, understand that there is no good formal definition of "algorithm" at the time of writing. The key word here is "formal".
However, there are smart people working on it.
What we know is that whatever an "algorithm" is, it sits somewhere between "mathematical function" and "computer program".
A mathematical function is formal notion of a mapping from inputs to outputs. 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. This function could be implemented using different algorithms (e.g. merge sort, heap sort). Each algorithm, in turn, could be implemented using different programs (even given the same programming language).
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". Any two programs which implement the same algorithm must compute the same function, but the converse is not true.
Similarly, there is an equivalence class between algorithms, where two algorithms are equivalent if they compute the same mathematical function.
The hard part in all this is trying to capture what we mean by "essentially the same thing".
There are some obvious things that we should include. For example, two programs are essentially the same if they differ only by variable renamings. Most models of programming languages have native notions of "equivalence" (e.g. beta reduction and eta conversion in lambda calculus), so we should throw those in too.
Whatever equivalence relation we pick, this gives us some structure. Algorithms form a category by virtue of the fact that they are the quotient category of programs. 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. Whenever you see interesting structure like that, you know that this line of enquiry will probably be useful.
First, understand that there is no good formal definition of "algorithm" at the time of writing. The key word here is "formal".
However, there are smart people working on it.
What we know is that whatever an "algorithm" is, it sits somewhere between "mathematical function" and "computer program".
A mathematical function is formal notion of a mapping from inputs to outputs. 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. This function could be implemented using different algorithms (e.g. merge sort, heap sort). Each algorithm, in turn, could be implemented using different programs (even given the same programming language).
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". Any two programs which implement the same algorithm must compute the same function, but the converse is not true.
Similarly, there is an equivalence class between algorithms, where two algorithms are equivalent if they compute the same mathematical function.
The hard part in all this is trying to capture what we mean by "essentially the same thing".
There are some obvious things that we should include. For example, two programs are essentially the same if they differ only by variable renamings. Most models of programming languages have native notions of "equivalence" (e.g. beta reduction and eta conversion in lambda calculus), so we should throw those in too.
Whatever equivalence relation we pick, this gives us some structure. Algorithms form a category by virtue of the fact that they are the quotient category of programs. 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. Whenever you see interesting structure like that, you know that this line of enquiry will probably be useful.
Context
StackExchange Computer Science Q#38386, answer score: 13
Revisions (0)
No revisions yet.