9
$\begingroup$

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.

Improve this question
$\endgroup$

10 Answers 10

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you for your precise answer, just another question. If we consider any program, regardless what it does, they still get some inputs and follow some instructions, and give some results as they are executed. They even may don't solve any problem (as we call), but it is still a mapping. could they be known algorithm, I mean any program? $\endgroup$
    – Ahmad
    Feb 16, 2015 at 5:55
  • 1
    $\begingroup$ If I'm reading you correctly, you're asking if a formal definition of an "algorithm" should or should not carry the proviso that it must be "useful". I would say "no", if only because it's impossible to formalise that notion. $\endgroup$
    – Pseudonym ♦
    Feb 16, 2015 at 6:30
  • $\begingroup$ sorry! my English is not well, then you say "no" to what? you admit that it's impossible to formalise the usefulness of a program, and just by definition, any program is an algorithm? or you say it's necessary that we consider usefulness beside the algorithm? $\endgroup$
    – Ahmad
    Feb 16, 2015 at 16:57
  • 1
    $\begingroup$ I don't think that a formal definition of an "algorithm" should require it to be useful, because "useful" can't be formally defined. $\endgroup$
    – Pseudonym ♦
    Feb 16, 2015 at 22:20
  • $\begingroup$ Your answer is the most useful in this thread +1. I believe by "essentially the same thing", you mean "semantically equivalent". Also, I think all programs are essentially algorithms (as OP says), since all programs are implementations which map some input to some output, even if this mapping be implicit. As you stated, it all depends on the perspective. $\endgroup$
    – doubleOrt
    Jun 20, 2018 at 12:56
7
$\begingroup$

Ultimately, the difference is one of perspective. A program is a program: a sequence of statements in some language, perhaps a programming language or machine-level instructions. Algorithms are usually described at a higher level than machine instructions or programming language statements but just how high a level is rather flexible. For example, in some circumstances, "Sort the array, then look at the $k$th element" is a perfectly good description of an algorithm for finding the $k$th largest object in an array; in other circumstances, you might want to specify much more detail about how the sorting takes place.

As you say, an algorithm is something like "a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer." So, literally speaking, every program is an algorithm. Usually, though, we speak of programs implementing algorithms. Usually, when describing an algorithm, we avoid the low-level detail of exactly how things are implemented, assuming that a competent programmer would be able to implement it in the langauge of their choosing.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think the precise of algorithm is related to mathematics concept, lambda-calculus or Turing machine, still don't know what is that abstraction language? mathematics or a natural language with many fuzzy statements $\endgroup$
    – Ahmad
    Feb 15, 2015 at 15:51
  • 8
    $\begingroup$ @Ahmad Algorithm is an informal concept. It has no formal definition. In a sense, it's like a mathematical proof, which is different from a formal proof in a formal proof system. We believe that informal proofs can be "fleshed out" to formal proofs in any chosen (strong enough) formal proof system, just as any algorithm can be fully implemented in any (Turing-complete) programming language. $\endgroup$
    – Yuval Filmus
    Feb 15, 2015 at 19:46
5
$\begingroup$

Algorithms in the Turing-complete mindset are usually specified by input and output. Real programs do more; they

  • communicate with the user,
  • communicate with other machines,
  • react to the environment,
  • do not terminate and are still useful,

and more. These things are usually not considered in algorithms or theory of computation, but are essential for most programs.

Improve this answer
$\endgroup$
5
  • $\begingroup$ This is a very good point. But do you mean something like "usually specified as a means to map input to output"? Just specifying the input and output isn't enough: e.g., mergesort and quicksort produce the same output from any input but aren't considered to be the same algorithm. $\endgroup$
    – David Richerby
    Feb 16, 2015 at 8:47
  • $\begingroup$ @DavidRicherby I was thinking of specification in the PL sense; we don't specify anything else, so algorithms may not do anything else. Of course, we have to give more than the specification to describe a concrete algorithm. $\endgroup$
    – Raphael ♦
    Feb 16, 2015 at 8:59
  • $\begingroup$ Good points, but if we admit that in the end any program is an algorithm, I don't know how those matters you addressed are measured about an algorithm. Maybe an AI topic?! $\endgroup$
    – Ahmad
    Feb 16, 2015 at 16:59
  • $\begingroup$ Who would admit that, and why? And what do you mean by measure here? (And I certainly don't see the AI angle here.) $\endgroup$
    – Raphael ♦
    Feb 16, 2015 at 21:21
  • $\begingroup$ @Raphael I may admit it (by looking at the syntax, all programs look similar, they are sequences of instructions, or mapping of input to output), I just don't know how other features of a program (those you addressed) can be extracted from that definition. for example the difference between quick-sort and MATLAB or Windows Media Player!! $\endgroup$
    – Ahmad
    Feb 18, 2015 at 7:04
3
$\begingroup$

An algorithm is a concept or idea. It is a formal approach for solving a problem. Algorithms can be expressed, or implemented, in a variety of programming language (usually, almost any language can implement any algorithm). For some examples you should read through the Sorting Algorithms in Wikipedia.

A computer program is a specific sequence of instructions in a specific programming language. A program may contain the implementation of many algorithms. Excel is a program, but it's sorting capabilities are the manifestation of an algorithm.

Improve this answer
$\endgroup$
2
$\begingroup$

  • An algorithm is a systematic approach to solving a specific problem.

  • A program is a set of instructions for a computer to follow.

A program therefore does not even need to solve a problem. I'm sure we can all think of several programs that have caused more problems than they've solved. A program can be an implementation of many algorithms, or an algorithm can be implemented by patching together many programs. A program can even contain no algorithms. For example, the empty program which simply exits, or perhaps even a Hello World, could be considered a program with no algorithm.

Since an algorithm solves a specific problem, it is focused on a specific whole concept. An algorithm therefore provides abstract steps for processing one set of related information into a different set of derived information. A program does not require its constituents to be at all conceptually related. For example, a program can have an easter egg, but a thing properly called an algorithm should not. You can have a virus or trojan lurking in a program, but not in an algorithm. The closest an algorithm can get to this would be something like a backdoor in an encryption algorithm, where the planned flaw is part of the information relationship established by the algorithm.

And lastly, a program, as it is short for a computer program, tautologically requires a computer. An algorithm does not. If I systematically separate the shirts, pants, and socks from my laundry before putting them away, this is an algorithm. It deals with related inputs and outputs, can be described in a flow chart, and has calculable consequences in terms of efficiency (for example, the number of clothing pieces which must be compared to find matching socks).

Improve this answer
$\endgroup$
2
$\begingroup$

Here is a couple of ways to draw the line between an algorithm and a program:

Meaningful Purpose

Programs are written with a purpose and represent an attempt to achieve a goal. Algorithms may be viewed as tools to achieve that goal.

E.g. a screwdriver is an algorithm to modify the state of a screw but the screwdriver itself does not hold a purpose to do that. The purpose is in the head of the screwdriver operator who holds the program like putting up shelves.

Business logic

This point strongly relates to the purpose of a program. Since programs have purposes they inevitably have bits of real world in them like specific dates, measurements, technologies, names etc.

Algorithms on the other hand contain neither business logic nor bits of real world and instead of operating on specific values operate on variables.

E.g. in this sense you can compare a mathematical function like f(x) = x^2 which is abstract and operates on variables to a cooking recipe which contains precise values (at least one for reference).

Result

This point strongly relates to the business logic of a program. An agent (like a web browser user) consumes the result of a program not the result of an algorithm.

E.g. the consumer of a cooking recipe consumes the cake not the result of whipping cream or heating oven.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Perhaps it would be better to say that the screwdriver doesn't have the intent to turn screws? In everyday English, we would certainly say that a screwdriver does have the purpose of turning screws: turning screws is the exact thing it was designed to do. $\endgroup$
    – David Richerby
    Jan 11, 2017 at 14:26
  • $\begingroup$ Also, I'm not sure what you mean by "business logic" (many programs have nothing to do with business) or by saying that an algorithm "contains neither business logic nor bits of the real world". For example, I could perfectly well phrase a shortest-path algorithm in terms of towns and roads rather than vertices and edges. Doesn't the algorithm then "contain... bits of the real world"? $\endgroup$
    – David Richerby
    Jan 11, 2017 at 14:28
  • $\begingroup$ @DavidRicherby, you are right, my phrasing is ambiguous. What I meant is a meaningful purpose. Turning screws to turn screws is pointless just as well as sorting an array which is never used. By business logic I mean all program logic except for utility logic and technology stack boilerplate i.e. all logic that actually implements the purpose of the program i.e. the business logic of baking a cake is mixing ingredients and baking and does not include learning to mix or bake (which is reused utility logic in this case). $\endgroup$
    – Robert Mugattarov
    Jan 11, 2017 at 16:08
  • $\begingroup$ @DavidRicherby, as for bits of real world, I mean actualization i.e. a program unlike an algorithm has to communicate in some way with the physical world. An algorithm, on the other hand, can be a purely mathematical concept. $\endgroup$
    – Robert Mugattarov
    Jan 11, 2017 at 16:22
1
$\begingroup$

An algorithm is a self-contained step-by-step set of operations to be performed to solve a specific problem or a class of problems.

A computer program is a sequence of instructions that comply the rules of a specific programming language , written to perform a specified task with a computer.

Algorithms are general and have to be translated into a specific programming language (implemented).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ But the whole point of the question is that a program (either its source code or the compiled binary) is "a self-contained step-by-step set of operations to be performed to solve a specific problem or class of problems." $\endgroup$
    – David Richerby
    Feb 15, 2015 at 16:24
  • $\begingroup$ But it isn't. A program is not those operations, but an implementation of them: something that executes them in a particular context. E.g. the Unix sort utility is not a sorting algorithm, it uses a sorting algorithm. $\endgroup$
    – reinierpost
    Jan 11, 2017 at 20:52
1
$\begingroup$

An algorithm is expressing our idea or solution for specific problem in step by step approach.it is only problem solving and human understandable approach not for computer system

Program is step by step instructions which implemented for solving problem by computer system .it must be understandable by not only programmer also computer.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Welcome to Computer Science Stack Exchange. Please read cs.stackexchange.com/tour.if you have not yet done so. $\endgroup$
    – babou
    Jul 23, 2015 at 12:44
1
$\begingroup$

The other answers here, I think, miss an important point. The definition of 'algorithm' which I was taught included the requirement that the procedure halts on all inputs. Naturally that makes 'program' a broader class of procedures than 'algorithm', since some programs halt on all inputs and others do not.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ This is not universal. The definition I was taught didn't include that requirement. $\endgroup$
    – reinierpost
    Jan 11, 2017 at 20:47
1
$\begingroup$

I am pretty sure that other answers are good enough to take the lead but here's how I see the difference between an algorithm and program

  • An algorithm consists of simply the steps (machine independent) needed to be followed in some order to solve a problem.

  • A program is an instruction set for a specific type of machine to put an algorithm to practice.

For example.

Let's say you have an algorithm that has a step for reaching to a particular place before doing some other step.Now how this step of reaching will be carried out is not exactly defined.You may choose to walk or run or take a bus for doing it but that depends on how you choose to implement it (which is your program).

You can say that an algorithm is an abstraction of a program i.e. missing the exact details but lays out a plan to do something.

Improve this answer
$\endgroup$
1
  • $\begingroup$ A programme is not an instruction set but a structured set of instructions. “Instruction set” normally refers to the things that a (physical or virtual) processor can do, and can be considered as a programming language for that processor, but usually one with no structuring element other than conditional jumps. $\endgroup$
    – PJTraill
    Jan 6 at 17:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.