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.