One of the reason I didn't study computer science is that it is a pit of despair: as far as practical problems are concerned, nobody has yet come up with a programming language that is really usable (so everyone writes stuff in C, which is the moral equivalent of writing in English in iambic pentameters without the letter ‘e’—that is, sheer masochism—,or C++, which is worse; and high-level languages simply don't work); as for theoretical problems, they are sitting in a kind of limbo between mathematics and theology. Anyway.
But math is also a source of despair, when one reflects on how little one can prove and how many simple questions are left open and probably will remain so for a long time.
It is easy to concoct a math problem which is understandable by anyone and which is probably bound to remain unsolved for a really long time. Perhaps the simplest example is the so-called Syracuse problem (on the Collatz sequence), namely: start with a positive integer n, and, so long as it is not equal to 1, repeat the following: if it is even, divide it by two, and if it is odd, multiply it by three and add one (for example: 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1); the conjecture states that, whatever the starting integer, the sequence will eventually reach 1 (after which it would go into the loop 1 → 4 → 2 → 1 if it is continued; the question is essentially whether there exist other loops than that which starts from 1). It has been verified experimentally for a huge number of starting values, but so far as I know, nobody has been able to come up with a proof (or, at least, a published proof which has passed peer-review: because there are certainly hundreds of crackpot-generated proofs on the Web). Of course, nobody (almost no real mathematician, I mean) is seriously interested in this particular problem, so it isn't a surprise that no progress is being made; all the same, it is probably a very hard problem.
Here's one, however, that is of much greater theoretical interest, which is “probably not false” (as I heard Swinnerton-Dyer call it), and which is hopelessly out of reach of the present techniques of mathematics. Let F1,…,Fk be k polynomials (in one variable x) with integer coefficients and positive leading coefficient, and assume the product F1·…·Fk of all the Fi is not constantly divisible by some prime p (for example, x²+x is always even—assume that sort of thing doesn't happen): then [the conjecture states that] there are infinitely many integer values of x such that the Fi(x) are all simultaneously prime. This is called Schinzel's (H) hypothesis (or sometimes the Schinzel-Sierpiński hypothesis). Even in the simple case where one takes the two polynomials x and x+2, the Schinzel hypothesis implies the twin primes conjecture, which is far from proven. Similarly, Schinzel's hypothesis implies that there are infinitely many primes of the form 6q²+1 where q itself is prime, and many other things of the same form.
Here is another conjecture, which is about of the order of
difficulty of Schinzel's hypothesis (i.e., probably not false, but
unattainable
): assume
t1,…,tr
are r complex numbers that are linearly independent over
the rationals, meaning that if
c1,…,cr
are r rationals such that
c1·t1 + … +
cr·tr
= 0, then all the ci are zero (for
example, 1, √2 and 2iπ are linearly
independent over the rationals); then [the conjecture states that] out
of the 2r complex numbers
t1,…,tr,et1,…etr
(in other words, add the exponentials of the
ti to the list), there are at least
r which are algebraically independent (over the rationals),
meaning that if some polynomial with rational coefficients in
r variables vanishes when applied to the r
quantities in question, the polynomial is identically zero. This is
known as Schanuel's conjecture. If applied in the particular case of
1, √2 and 2iπ, Schanuel's conjecture
implies that the three quantities e,
e√2 and π are algebraically
independent, which in turn implies the transcendence of such
quantities as e+π which is still an open
problem. Schanuel's conjecture is a kind of holy grail in
transcendental number theory.
In comparison to Schinzel's hypothesis or Schanuel's conjecture, the seven problems whose head is at stake for $1000000 are presumably quite easy (in fact, at least one—namely the Poincaré conjecture—can now be considered as good as solved, thanks to Perelman).
It is not unthinkable that these problems should be undecidable;
however, the tools available for proving the undecidability of a
mathematical statement are even more inadequate, in this case, than
those that might attempt to prove the statement… (I let those
with some knowledge in logic reflect upon what happens when one
iterates the construction is undecidable
to transfinite
heights).