What exactly is an algorithm?

Question

I know that this may sound a bit out of the box, in fact i used to always think inside the box, but recently i've been thinking, possibly because computer science provides an high degree of freedom, about ways to devise programs other than the ones taught in university.

Consider the factorial function. Typically we define this function like

 int fact(int n) 
 { 
 int r = 1; 
 for(int i=2;i<=n;i++) 
 r = r*i; 
 return r; 
 } 

I'd call this an algorithm and have no doubt that this is the right way to do it. Then, i wondered "can i do this in constant time?", which let to the following idea: what if i had an array of integers where array[n] houses the factorial of n? Once this array is filled i could simply define fact as:

 int fact(int n) 
 { 
 return array[n]; 
 } 

Still i cant seem to cal this an algorithm, even though it provides the correct result and operates in constant time O(1). Can this be called an algorithm? Otherwise, why not? I could argue that filling the array would require an algorithm to have operated at some time, even if it was in our brain in order for us to fill the array, but could this be the criteria? How are these aspects handled formally?

Note that this concept could be extended to any function operating over integers independly of its number of arguments, i would just have to use a matrix if the function had 2 arguments, or 3 if the function had 3 arguments, and so forth. Also, aren't these solutions used simply because of memory consumption?

Also, not that functions may also encompass any program with output, since i could find a way to index every single possible output that a program could provide.

As another exemple, consider the common use of an array: i allocate an array initially of size N, then i add elements to array by storing the value at index n and increasing n by one unit. Then, if i want to look for an elemento, i cant help but to perform a linear search over the array. If instead i created an array of size, for instance, Integer.MAXVALUE, to store integers, initialized with zeroes, i could store an integer by placing 1 at its index. Then i could search for its existence in the array in O(1) time. What if i wanted to be able to place multiple units of the same number? No problema, i'd just increase the value stored at the integer's index.

Sorting would be a bit more complicated, but nonetheless lookup and addition could be performed in O(1) time.

Answer 1

The informal definition of an algorithm in a popular textbook goes something like:

An algorithm is (1) a well defined computational procedure (2) that takes some input and (3) produces some output (4) for a well defined computational problem.

In your first case you have coded an algorithm where: The problem is to find the factorial (part 4 of definition), given int n as input (part 2 of definition), the code describes the computation to be performed (part 1 of definition), the output is the factorial (part 3 of definition).

In your second case: The problem is to find the array element at position n (part 4 of definition), given n as input (part 3 of definition), the code describes the computation to be performed (part 2 of definition), the output is the element at position n (part 1 of definition).

You have stored factorials there so it gives you factorials. If you had stored squares or cubes there you'd get squares or cubes, so it cannot be said that the second snippet by itself is an algorithm to compute factorials.

And if you say that an array look up along with an array having f(n) at position n is an algorithm to compute f(n) then you have gone so deep that there is no more computation below. A well defined computational procedure should be a finite piece of information. If an infinite array of factorials is a part of the computational procedure this does not hold. So that wouldn't be an algorithm to compute factorials.

Answer 2

Most broadly, an algorithm is a series of steps for solving a problem.

In CS, the following are commonly understood/assumed when using the term algorithm:

• The algorithm has finite description and a well-defined procedure for carrying out its steps given any problem instance. (More below.)
• A problem instance given as a finite string (sequence of input symbols), and the output of the algorithm can be encoded as a finite string.
• A problem is a collection of problem instances together with possible "correct" outputs for each instance. "Solving" means producing a correct output.
• (Usually) the problem instances can be arbitrarily large (there are an infinite number of possible instances that your finite algorithm must solve).

Before CS was founded, mathematicians had the same types of concerns you raise, and introduced formal definitions of computation to address these concerns. Thus, nowadays, we can formalize all of the above assumptions by simply saying "an algorithm is a procedure that can be implemented on a Turing machine". This is probably the best formal answer to your question.

Note that the Church-Turing thesis says that we think there is no "more powerful" formalization of algorithms than the Turing Machine.

The factorial example gets into a different model of computation, called non-uniform computation. A Turing Machine is an example of a uniform model of computation: It has a single, finite description, and works for inputs of arbitrarily large size. In other words, there exists a TM that solves the problem for all input sizes.

Now, we could instead consider computation as follows: For each input size, there exists a TM (or some other computational device) that solves the problem. This is a very different question. Notice that a single TM cannot store the factorial of every single integer, since the TM has a finite description. However, we can make a TM (or a program in C) that stores the factorials of all numbers below 1000. Then, we can make a program that stores the factorials of all numbers between 1000 and 10000. And so on.

These non-uniform types of computation are typically modeled in theoretical CS by circuits. You consider a different circuit construction for each possible input size.

Non-uniform models of computation are generally not considered algorithms, even though they might fit my first sentence. The reason is that they do not fit in our key assumptions: they do not have a finite description that can be implemented to solve the "whole" problem for any input size. Rather, they need a bigger and bigger description as the problem gets bigger (like needing a larger lookup table). However, they are still interesting models of computation.

Answer 3

An algorithm is a program written in C that should work for any length of inputs (assuming infinite memory and unbounded integers). In your examples, if we wanted the program to work for all lengths of inputs, then the table in which the results are stored would be infinitely large; programs in C are always finite, so this approach cannot be used.

The definition of algorithm is very resilient: in the early days of recursion theory, many definitions were proposed, and they were all shown to be equivalent. For example, instead of C you can use Turing machines. However, these models are not necessarily equivalent in terms of efficiency: a problem could be solved much more efficiently in C than using Turing machines. When interested about efficiency, we should restrict ourselves to all models which are "close enough" to C with respect to running time. For example, if we are allowed to use an instruction which computes $n!$ in one time unit, then the resulting model still defines the same set of computable functions, but some functions (like $n!$) can be computed in it much more efficiently, compared to C.

When worried about actual running times on an actual computer we should be even more careful, but this is usually beyond the limits of theoretical computer science, unfortunately.

---

If we are very fussy, we need to be clear about the difference between algorithms and functions computed by algorithms. For example, the factorial function gets as input a natural number $n$ and outputs $n!$. The factorial function can be computed by an algorithm. We say that a function is computable if it can be computed using some algorithm.

What notion of algorithm should we use? One suggestion, outlined above, is to use C programs. We can call this notion C-computation. Turing-computation is what you get when you use Turing machines. It turns out that a function is C-computable if and only if it is Turing-computable. It is in this sense that both these models of computation are equivalent. Indeed, many other models are equivalent, for example all programming languages in common use (assuming infinite memory and unbounded variables).

We say that a programming language P is Turing-complete is a function is P-computable if and only if it is Turing-computable. The Church–Turing hypothesis is an informal statement to the effect that all reasonable computation models having finite description and taking finite time are Turing-complete. Your model has a finite description but does not take finite time.

Answer 4

The important part of the common definition of an algorithm that yours is missing is that the specification must be finite, and the size of the specification must not vary with the size of the input.

Memory can be arbitrarily large, and so can inputs, but to be a useful definition of an algorithm, the codespace must be finite. Otherwise you get the problem that you just identified.

Unrelated to your question, any realistic definition of an algorithm machine will have memory lookup being at least $O(\log A)$ to fetch memory at address $A$. So your lookup algorithm will at least have time $O(\log n)$ for each bit of the output, which has $O(\log n!)$ bits, so your total runtime of your look up will be $O(n (\log n)^2)$. But if the input is $s$ bits, then $n = O(2^s)$, so your lookup algorithm is $O(2^s~s^2)$, nowhere in the ballpark of $O(1)$.

Answer 5

A few observations that might be helpful:

Problems are statements about allowable inputs and corresponding outputs. They're what we want to solve. Algorithms are computational procedures. We can say that an algorithm is correct with respect to a problem if it accepts inputs which are allowable with respect to the problem and produces outputs according to the problem description.

Both of your examples are algorithms, as they're both clearly computational procedures. Whether the algorithms are correct or not depends upon how you define the problem and how you interpret the representation of the algorithm. Some problem statements:

1. Given $n$, compute $n!$
2. Given $n > 0$ such that $n! < $ INT_MAX, compute $n!$.

Some interpretations of your first code snippet:

1. This is pseudocode which resembles C/C++ except in the details. int really means "any integer", for instance.
2. This is to be interpreted as though it were a real C/C++ program.

Interpretation 1 is correct for problem statement 1, as long as the factorial assumes the value 1 for negative numbers (otherwise, we could modify the problem statement to restrict the domain, or the algorithm to account for desired behavior). Interpretation 2 is correct for problem statement 2, with the same caveat.

The second snippet assumes that an array has been pre-computed and is accessible to the function. Given this, there are assignments of array such that this algorithm would be correct under an "interpret as C/C++" interpretation for the given problem statement: given $n$ such that $n > 0$ and $n! < $ INT_MAX, compute $n!$. Note that this algorithm has undefined behavior for $n < 0$ and, as such, it would be unrealistic to hope that the algorithm would be correct for a problem allowing those values.

More generally - pre-computing functions into tables is a common technique for exactly the reason you have noticed: you can perform the computation once, and then reuse the results of that computation over and over. For many functions, it makes a lot of sense. Factorial is a great example: it grows so quickly, a relatively small array can store virtually all integer values you'd need in practice (exercise: what's the smallest integer $n$ such that $n! \geq 2^{32}$? such that $n! \geq 2^{64}$?)

To analyze such algorithms, you can used what's called amortized analysis. Typically, you use this when some calls to the algorithm might take a long time, while almost all (asymptotically speaking) take less time. In this case, if you want to compute $k$ random factorials (with $k$ much greater than $n$, the typical value for which you're computing the factorial), you'd end up doing work proportional to $kn$ using the first algorithm, but more like $k+n$ using the second. So, you can save some by pre-computing here.

Answer 6

An algorithm is a program written in a Turing-complete language that provably halts on all valid inputs. All standard programming languages are Turing-complete. The word originates as a European translation of the name al-Khwārizmī, a Persian mathematician, astronomer and geographer, whose work built upon that of the 7th-century Indian mathematician Brahmagupta, who introduced the Indian numeral system to the western world.

The question seems to be basically about whether lookup tables are parts of algorithms. Absolutely! In Turing machines (TM) tables can be encoded in the state table of the TM. The TM can initialize the tape based on a finite amount of data stored in the transition table. However, "algorithms" that don't run on infinite inputs, only finite inputs, are "trivially" finite-state machines (FSM).

Answer 7

There is no good formal definition of "algorithm" at the time of writing. 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 equivalent 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.

Answer 8

In a nutshell: An algorithm is the constructive part of a constructive proof that a given problem has a solution. The motivation for this definition is the Curry-Howard isomorphism between programs and proof, considering that a program has an interest only if it solves a problem, but provably so. This definition allows for more abstraction, and leaves some doors open regarding the kind of domains that may be concerned, for example regarding finiteness properties.

Warning. I am trying to find a proper formal approach to answering the question. I do think it is needed, but it seems that none of the users who replied so far (myself included, and some were more or less explicit about it in other posts) has the right background to properly develop the issues, which are related to constructive mathematics, proof theory, type theory and such results as the Curry-Howard isomorphism between proofs and programs. I am doing my best here, with whatever snippets of knowledge I do (believe to) have, and I am only too aware of the limitations of this answer. I only hope to give some hints of what I think the answer should look like. If you see any point that is clearly wrong formally (provably), please let me now in a comment - or by email.

Identifying some issues

A standard way to consider an algorithm is to state that an algorithm is an arbitrary finitely specified program for some computing device, including those that have no limitations in memory. The langage may as well be the computer machine language. Actually it is enough to consider all programs for a Turing complete computing device (which implies having no memory limitations). It may not give you all algorithms presentations, in the sense that algorithms have to be expressed in a form that is dependent in its details on the interpretation context, even theoretical, as everything is defined up to some encoding. But, since it will compute all there is to be computed, it will include somehow all algoritms, up to encoding.

This definition is hopefully correct, but is it useful? Not really. Given any such computer, which we assume to be a binary computer to simplify the discussion, you can just store an arbitrary finite sequence of bytes in its memory and start executing. You will be computing something. Well, the empty output in many cases. If you are lucky, you will get an infinite enumeration of the decimals of $\pi$, or possibly, as suggested by @hirschhornsalz, such gems as World of Warcraft, Microsoft Office 17 including Service Pack 6 and Windows 9. Whatever happens, it will compute something for sometime, possibly stopping right away, or computing for ever with or without output.

The problem is that one can take any arbitrary bit sequence and see it as an algorithm, as a program for some computer. But that is perfectly useless when you have no idea what it computes. It might look like the decimals of $\pi$, but contain errors every so often. This is like Borges' Library of Babel, but worse because there is no size limit to the code of algorithms, only that they be finite. The main difference is that Borges' library is finite (since the books have a fixed size), while the number of algorithms is countably infinite. The meaningful algorithms are very few, even the buggy ones, as are the meaningful books in Borges' library. Actually, I would conjecture that, in some way, Almost all algorithms are uninteresting, possibly in the mathematical sense of almost all. But that would require more precision in definitions.

So the real question is to know what are the meaningful algorithms. The answer is that the meaningful algorithms are those that solve a problem, computing step by step the "solution", the "answer", to that problem. An algorithm is interesting if it is associated with a problem that it solves.

So given a formal problem how do we get an algorithm that solves the problem. Whether explicitly or implicitly, algorithms are associated with the idea that there exist a solution to the problem, which can be proved correct. Whether our proof techniques are accurate is another matter, but we try at least to convince ourselves. If you restrict yourself to constructive mathematics, which is actually what we have to do (and is a very acceptable axiomatic constraint for most of mathematics), the way to prove the existence of a solution is to go through proof steps that actually exhibit a construct that represents the solution, including possibly other steps that establish it correctness.

All programmers think something like: if I fiddle with the data in such and such a way, then I get this widget which has just the right properties because of Sesame's theorem, and running this foo-preserving transformation I get the desired answer. But the proof is usually informal, and we do not work out all details, which explains why a satellite tried to orbit Mars underground (among other things). We do much of the reasonning, but we actually keep only the constructive part that builds the solution, and we describe it in a computer language to be the algorithm that solves the problem.

Interesting algorithms (or programs)

All this was to introduce the following ideas, which are the object of much current research (of which I am not a specialist). The notion of "interesting algorithm" used here is mine, introduced as an informal place holder for more accurate definitions.

An interesting algorithm is the constructive part of a constructive proof that a given problem has a solution. That means that the proof must actually exhibit the solution rather than simply prove its existence, for example by contradition. For more details see Intuitionistic Logic and Constructivism in Mathematics.

This is of course a very restrictive definition, that considers only what I called interesting algorithms. So it ignores almost all of them. But so do all our textbooks on algorithm. They try to teach only some of the interesting ones.

Given all the parameters of the problem (input data), it tells you how to obtain a specified result step by step. A typical example is the resolution of equations (the name algorithm is actually derived from the name of a Persian mathematician, Muḥammad ibn Mūsā al-Khwārizmī, who studied the resolution of some equations). Parts of the proof is used to establish that some values computed in the algorithm do have some properties, but these parts need not be kept in the algorithm itself.

Of course, this must take place within a formalized logical framework that establishes what are the data computed with, what are the elementary computational steps that are allowed, and what are the axioms used.

Going back to your factorial example, it may be construed as an algorithm, albeit a trivial one. The normal factorial function corresponds to a proof that, given some arithmetic framework, and given an integer n, there is a number that is the product of the first n integers. This is pretty straightforward, as is the factorial computation. It could be more complex for other functions.

Now, if you decide to tabulate factorial, assuming you can, which is not true for all integers (but could be true for some finite domain of values), all you are doing is including in your axioms the existence of factorial by defining with a new axiom its value for each integer, so that you no longer need to prove (hence to compute) anything.

But a system of axioms is supposed to be finite (or at least finitely defined). And there is an infinity of values for factorial, one per integer. So you are in trouble for your finite system of axioms if you axiomatize an infinite function, i.e. defined on an infinite domain. That translate computationally in the fact that your would-be table look-up cannot be implemented for all integers. That would kill the usual finiteness requirement for algorithms (but is it to be as strict as often presented?).

You could decide to have a finitely defined axiom generator to handle all cases. This would amount, more or less, to including the standard factorial program in your algorithm to initialize the array as needed. That is called memoization by programmers. This is actually the closest you get to the equivalent of a precomputed table. It can be understood has having a precomputed table, except for the fact the the table is actually created in lazy evaluation mode, whenever needed. This discussion would probably need a little bit more formal care.

You may define your primitive operations as you wish (within consistency with your formal system) and assign to them whatever cost you choose when used in an algorithm, so as to do complexity or performance analysis. But, if the concrete systems that actually implement your algorithm (a computer, or a brain for example) cannot respect these cost specifications, your analysis may be intellectually interesting, but is worthless for actual use in the real world.

To consider the last example in the question, it is easy to represent a number on the order of $2^{1000}$ on the computer, and even to sort such numbers. It is somewhat harder (in this universe at least) to implement an array with that size. Hence, it may be an interesting theoretical algorithmic speculation, but it may also not be very applicable in our limited physical world.

What programs are interesting

This discussion should be more properly linked to results such as the Curry-Howard isomorphism between programs and proof. If any program is actually a proof of something, any program may be construed as an interesting program in the sense of the definition above.

However, to my (limited) understanding, this isomorphism is limited to programs that can be well typed in some appropriate typing system, where types corresponds to propositions of the axiomatic theory. Hence not all program can qualify as interesting programs. My guess is that it is in that sense that an algorithm is supposed to solve a problem.

This probably excludes most "randomly generated" programs.

It is also a somewhat open definition of what is an "interesting algorithm". Anything program that can be seen as interesting is definitely so, as there is an identified type system that makes it interesting. But a program that was not typable so far, could become typeable with a more advanced type sytem, and thus become interesting. More precisely, it always was interesting, but for lack of knowledge of the proper type system, we could not know it.

However, it is known that not all programs are typeable, since it is known that some lambda expression, such as implementing the Y combinator, cannot be typed in a sound type system.

This view only applies to programming formalisms that can be directly associated to some axiomatic proof system. I do not know how it can be extended to low level computational formalisms such as the Turing Machine. However, since algorithmics and computability is often a game of encoding of problems and solutions (think of arithmetics encoded in lambda calculus), one can consider that any formally defined computation that can be shown as being an encoding of an algorithm is also an algorithm. Such encodings probably use only a very small part of what can be expressed in a low level formalism, such as Turing Machines.

One interest of this approach is that it gives a notion of algorithm that is more abstract and independent of issues of actual encoding, of "physical representability" of the computation domain. So one can, for example, consider domains with infinite objects as long as there is a computationally sound way of using them.

Answer 9

Your question and description do not relate that much. Algorithm is theoretical and doesnt relate to any programming language. Algorithm is a set of rules or steps (procedure) to solve a problem. Your problem can be solved in many ways or many algorithms.

Your second solutions means to compute first a big array of factorials which initially will take a lot of time then store it. It will consume more storage but eventually it will be faster while the first one doesnt consume storage but consumes computing power so you will have to chose depending on your environment.