12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your second function should have the array as a parameter. Otherwise you get lost in the imperative trap of implicit state, which is useful in programming but can make your code very difficult to reason about. $\endgroup$ – jmite Oct 15 '14 at 15:21
  • $\begingroup$ Yes, your second code can be called an algorithm for which the input is the number n and the array which has all the factorials. In the first code the algorithm has only one input i.e the number n. $\endgroup$ – Ankur Oct 16 '14 at 12:50
  • $\begingroup$ Obligatory: I shall not today attempt further to define the kinds of material I understand to be embraced within that shorthand description ["algorithm"], and perhaps I could never succeed in intelligibly doing so. But I know it when I see it, and the things described in the posts below are not that. $\endgroup$ – Patrick87 Oct 17 '14 at 15:27
  • $\begingroup$ Related to this question (but not directly answering it), it is also interesting to read "What is an algorithm?" by Yuri Gurevich, Microsoft Research, Technical Report MSR-TR-2011-116 research.microsoft.com/pubs/155608/209-3.pdf $\endgroup$ – godfatherofpolka Oct 28 '14 at 12:33
  • $\begingroup$ You say: "... what if i had an array of integers where array[n] houses the factorial of n? Once this array is filled....". How are you going to fill up an array with the factorials of all integers? This array would have an infinite size and it would take infinite time to be filled. Therefore your question is ill posed. $\endgroup$ – A.P. Oct 28 '14 at 13:50
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The real problem with the OP's suggestion is that the description of the "well-defined computational procedure" is not finite. Of course, unless we explain what we mean by "well-defined computational procedure", one cannot tell in advance whether the OP's algorithm is legit or not. It is actually a "well-defined computational procedure" given the infinite array, so why is this illegal? The OP can even describe in finite terms how to populate the array. What then goes wrong? Your informal definition cannot distinguish between hypercomputation and (Turing) computation. $\endgroup$ – Yuval Filmus Oct 15 '14 at 16:32
  • $\begingroup$ A well defined computational procedure should be expressible as a finite piece of information. If an infinite array of factorials is a part of it this does not hold. $\endgroup$ – Computer Oct 15 '14 at 18:03
  • 2
    $\begingroup$ It is expressible as a finite piece of information, as the OP has demonstrated. The array is initialized with all factorials. This is a finite description. It's just not operatively finite. In the same way, $\{(n,n!) : n \in \mathbb{N}\}$ has a finite description without being finite. $\endgroup$ – Yuval Filmus Oct 15 '14 at 18:06
  • $\begingroup$ The description of the array is expressible as a finite piece of information but the array itself is not. $\endgroup$ – Computer Oct 15 '14 at 18:10
  • $\begingroup$ I'd argue that both of the OP's examples are algorithms, and that neither computes the factorial for all integers. But that's just being picky, I suppose. $\endgroup$ – Patrick87 Oct 16 '14 at 14:41
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think your circuit based computational model is inappropriate. As you say, a TM has a finite description. But that does not preclude having an auxiliary tape that is filled with a tabulated version of factorial. One could even do "worse" and still have a finite description. But really all you need is a computable description, which is necessarily ultimately finite. There are many computationally uniform ways to define a Turing machine with a tabulated factorial, none of which is able to actually increase the computational power of a TM. Hence your conclusion does not hold. $\endgroup$ – babou Oct 29 '14 at 20:29
  • $\begingroup$ @babou, I don't understand what you mean. What do you mean by "inappropriate" and which conclusion did I make that is false? Notes: I did not invent the circuit model. Perhaps I did not do a good job describing it. The key point is that, for each input, we allow a different computational device (TM or circuit), meaning that there may be no uniform algorithm that generates all of these devices (for all input sizes), or in other words, there may be no finite description that describes all of them. $\endgroup$ – usul Oct 29 '14 at 23:38
  • $\begingroup$ Viewing the tabulation of the factorial function as a non-uniform computation does not seem to me the proper way to go. It is actually very uniform, to such an extent that its finite segments may be seen as continuous with a limit at infinity which is the whole table. That is what is done with Scott's semantics. Furthermore the whole table can actually be finitely described in a computable way, so that it would make computational sense to consider a TM with an extra tape containing the precomputed table. Your answer seems to conclude that a precomputed table cannot be considered an algorithm. $\endgroup$ – babou Oct 30 '14 at 0:29
  • $\begingroup$ Any particular precomputed table might be part of an algorithm, and for an infinite sequence of increasingly-sized precomputed tables, you might produce these any one of these things using an algorithm. But I would not consider an infinite set of increasingly-sized lookup tables to be, on its own, an algorithm or a uniform computation since it is infinite in size. $\endgroup$ – usul Oct 30 '14 at 0:47
  • $\begingroup$ You would not consider it an algorithm. This is subjective. What matters is knowing why you should not. And there is no reason that I can see. Any concept that makes sense for algorithms keeps making sense in that case. All it does is abstract out the creation of the table, though that can be accounted for separately. Actually this is a purely semantics issue, since considering the increasing sequence as such, or replacing it by its infinite limit, amounts mathematically to the same. And semantic theories of computation do consider such infinite limits, however produced or represented. $\endgroup$ – babou Oct 30 '14 at 10:40
4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ lol "An algorithm is a program written in C..."?!? $\endgroup$ – vzn Oct 15 '14 at 15:14
  • 2
    $\begingroup$ "An algorithm is a program written in C" ... Why are you specifying the language? It makes non-sense. $\endgroup$ – nouney Oct 15 '14 at 15:14
  • 1
    $\begingroup$ @nouney I'm just trying to be concrete. Your favorite programming language is also Turing-complete. $\endgroup$ – Yuval Filmus Oct 15 '14 at 15:16
  • $\begingroup$ @YuvalFilmus Well you're not concrete, you're confusing. $\endgroup$ – nouney Oct 15 '14 at 15:19
  • $\begingroup$ @nouney You're welcome to add your own answer. $\endgroup$ – Yuval Filmus Oct 15 '14 at 15:20
4
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ "the codespace must be finite": Do you mean to say that a Lisp program that calls the eval function on some large data structure it just created, and which represent a lLisp expression, cannot be considered an algorithm. I suspect that much of the code produced at MIT in the 20th century does not qualify as algorithms. This is just an informal argument, but the formal problem lies with the view of what a finite specification is, which you read in a far too restrictive way. $\endgroup$ – babou Oct 29 '14 at 20:40
  • $\begingroup$ If the expression was generated then it is finite. No matter how large. However, removing the restriction on the finiteness of codespace can be useful, it can be used to prove lowers bounds on runtime (such as proving a lowerbound on the runtime of list sorting). But almost any interesting result on algorithms themselves will require a finite codespace. It is similar to how polynomials must have a finite number of coefficients, but power series are useful as well. $\endgroup$ – DanielV Oct 29 '14 at 21:58
  • $\begingroup$ I am no expert on how to compute complexity (not my field), but the fact that you have or do not have the mathematics to do it should not impact what is an algorithm. The point is that the Lisp program can keep increasing the size of its code without any bound. Then it may make more sense to analyze this as an infinite piece of code with specific computational properties. The case of the tabulated function can be seen in that light. I am surprised that answers have such a limited (I was about to say parochial) view of what an algorithm is. $\endgroup$ – babou Oct 29 '14 at 22:27
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I would think that the concept of an algorithm goes somewhat beyond the word size limitations of a computer. I feel that you are just dodging the issue. $\endgroup$ – babou Oct 29 '14 at 21:05
1
$\begingroup$

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).

$\endgroup$
  • 3
    $\begingroup$ Why does it have to be in a TUring complete language? $\endgroup$ – babou Oct 16 '14 at 18:35
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I don't think it's fair to say there is no good formal definition of an algorithm. This was the case roughly 100 years ago. $\endgroup$ – Juho Oct 17 '14 at 14:16
  • 1
    $\begingroup$ @Juho It may be that Pseudonym makes it sound too strong, though he does try to mitigate the statement, adding in particular that the situation is making progress. However, I do think he is rather right in his assessment. I am reacting late, because I spent spending much time on this, and feel pretty much the same. People have improved considerably their understanding, but the whole discussion shows that there is no real consensus ... and I found most contributions extremely immature, given the level of the people involved. If he is unfair, who do you think gave a good formal definition? $\endgroup$ – babou Nov 1 '14 at 16:03
  • $\begingroup$ You are 100% correct. And I think that if Turing were sill alive, or any other theoretician in complexity theory, he would 100% agree with you. The academics need to give up their troglodyticism. It is actually hindering the field. This will eventually happen any way, once they die. Thank goodness for that. $\endgroup$ – BananaCats Category Theory App Oct 15 '16 at 17:16
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This is not an easy view of the issue, though it is a fundamental one. I had to simplify outrageouly and I may have made mistakes. But, if you are to downvote, please tell me why. $\endgroup$ – babou Oct 16 '14 at 18:33
  • $\begingroup$ Yeah, I'm not sure what's with the downvotes. $\endgroup$ – Pseudonym Oct 17 '14 at 0:12
  • $\begingroup$ @Pseudonym In my case. I think I know. It suspect it is the old battle between semanticists and algorithmicians, especially those working on computability. That is the battle between philosophy and business, what it is and what it costs. I am interested in algorithms that are "meaningful". I modified accordingly (but I am at the edge of my knowledge whish seems still better than most). You may suffer from the same ghettoisation. - - - However. it is quite clear that on this subtle topic, anyone whose opinion is worth half a cent would not dream of downvoting without proper explanation. $\endgroup$ – babou Oct 17 '14 at 8:52
  • $\begingroup$ After reading both the question and your answer, I'm temped to downvote it, because it doesn't focus enough on the actual question, and contains too many unfinished thoughts. In addition, I don't think that "solving a problem" is the missing part in the definition of an algorithm. But I agree that "semantics" shouldn't be ignored in the definition of what constitutes an algorithm. $\endgroup$ – Thomas Klimpel Oct 22 '14 at 8:10
  • $\begingroup$ @ThomasKlimpel As I said, I am not expert enough on the real issues. And I added that no other answer is. Making algorithms is not the same as understanding what they are. My awareness of my limited knowledge, which it would be unscientific to hide is the source of this unfinished thoughts feeling. It seems better to underscore the existence of problem, rather then ignore them. I did address each example, more from a semantics p.o.v. than from an algorithmic one, as the question is a semantical question ("What is ...?"). Do you think other answers bring any formal understanding. Cf my comments $\endgroup$ – babou Oct 22 '14 at 10:26
-4
$\begingroup$

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.

$\endgroup$

protected by Yuval Filmus Dec 11 '16 at 19:07

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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