Slashdot Mirror
Are Computers Ready to Create Mathematical Proofs?
DoraLives writes "Interesting article in the New York Times regarding the quandary mathematicians are now finding themselves in. In a lovely irony reminiscent of the torture, in days of yore, that students were put through when it came to using, or not using, newfangled calculators in class, the Big Guys are now wrestling with a very similar issue regarding computers: 'Can we trust the darned things?' 'Can we know what we know?' Fascinating stuff."
A computer could quite easier come up with a very complex answer simply because it can do more calculations in a given second than a human can. Of course humans take in a lot more variables at a given time so the numbers are actually very opposite but I'm sure you get my point.
I think you test it with progressively more different problems, if the answers come out precise and accurate then you can build your level of trust in the system. Kind of like the process of getting users to trust saving to the server after a bad crash wiped everything because the previous admin was a moron.20th century mathematics has seen some pretty amazing things, but at the same time, there are very real questions as to what constitutes "proof" any more.
consider this: the hypothesis of the famous Riemann Zeta problem has been tested for trillions of different solutions, and it has held true in every case. (If you want an explanation of the Zeta problem, look elsewhere, I don't have the time)
Now that means that it's *probably* true, but nobody accepts that as mathematical proof.
On the other hand, the classification problem for finite simple groups has been rigorously solved, but the collected proof (done in bits by hundreds of mathematicians working over 30 years) is tens of thousands of pages in many different journals. given the standards of review, it is a virtual certainty that there is an error somewhere in there that hasn't been found. So, again, the solution to this problem is *probably* right, but it has been accepted as solved.
What's the difference between these two cases really? What's the difference between these and relying on computer proofs that are, again, *probably* right?
In this light, the math of the late 19th century and early 20th century was something of a golden age, modern standards of logical rigor were in place, but the big breakthroughs were still using elementary enough techniques that the proofs could be written in only a few pages, and the majority of mathematically literate readers could be expected to follow along. These days proofs run in the hundreds of pages and only a handful of hyper-specialized readers can be expected to understand, much less review them.
In Capitalist America, bank robs you!
Automated theorem provers have been around for a long time, if you can express your thoughts using first order logic. Here's a program from 1986... lisp code
Change the title to: "Are Computers Able to Verify Mathematical Proofs Beyond All Doubt?"
Though Dr. Hoare danced around that question a little, presumably that aspect of the project would have to be done by hand, a monumental task to say the least.
-
involved, not complicated - like the Four Color [Conjecture]. Noone could figure out a way to actually prove it, so some one (or group of someones) wrote a program to systematically determine all the possible arrangements of regions in a simplified series of maps, and then figure out how to color each of those maps. The involved part was .. well, all of it. It wasn't necessarily very complicated, just labor-intensive. Computers are perfectly suited for tedium.
Read; Write; Execute
Sometimes it is enough to know that something is *true* or *false* without having to know the details of the in-between steps.
I'll give some trivial examples to illustrate:
For a famous example, it would provide a great deal of peace of mind if we could prove that P != NP. It wouldn't matter that we understand that proof so much as that it is *provably true*. If, on the other hand, it is proven false that is just as important (if not more so) and while an understanding of the proof might lead more easily to examples of such, we would know (for certain) that trusting public key encryption over the long run would be a Bad Idea(TM) (for example) and that it is just a matter of time before a polynomial time algorithm is developed.
(Not that such will necessarily be fast, mind you, but we would know it would exist).
For another example--there are certain things that can be inferred if Poincare Conjecture is true for N=3. If we can prove the Poincare Conjecture is true (and it is now thought that it might be) it means things to physicists, even if we don't know why it is true.
The bigger question here is "can we trust it if we can't verify it by hand."
Integrate Keynote and LaTeX
Don't we already have tons of resources devoted to verifying the accuracy of a computing environment? If we verify the logic and accuracy of the computer, much like the axioms of mathematics, cannot we then say that the resulting proof must be valid?
Of course, if it can't be understood by humans, it doesn't really help anything, as one of the main points of proving things is to gain insight into how to prove other things. But wouldn't building the system to proove proofs be itself a different but valuable tool?
The ______ Agenda
once upon a time, only advanced mathematicians knew calculus, but now we learn it in high school. Just wait until warp theory is an entry level college engineering course
Once upon a time, the majority of adult males knew how to trap a rabbit (or similar creature), gut it, skin it, start up a fire, cook it, and eat it.
I don't.
Heck, I couldn't even look up at the sky at night and tell you which way was north.
Once upon a time, most people could.
All I'm saying is that the amount of knowledge and skills the average human being can possess will not increase expontentially over time (barring artificial manipulation). We gain new skills as a population and lose old ones.
That's exactly the case. I had Ken Appel as a professor, and he mentioned the 4-color theorem a couple of times. As he put it, the math wasn't intensive, but actually doing the work the computer was able to do would have taken an army of grad. students years to finish. The way he saw it, the proof was understandable, just extraordinarily, arduously long. That's when they decided to use a computer to solve the problem. Unfortunately, there are still many pure mathematicians who shun computer-based proofs because they (or their grad. students) are not working things out with their own pencils. Unfortunately, I don't think that's a problem that's going away, but I do think it opens up some interesting doors such as writing program A to prove a theorem, and then haveing to prove program A's correctness, for which you write program B and so forth.
What you've done is shown that for a subset of the sets of oranges and a subset of the sets of stacks the pyramid is better.
A mathematical proof shows something is true for every single element of the sets.
because we have no way of KNOWING if the computer has built up the proof correctly, except that it says it has
Sure we do -- typical theorem provers spit out a proof that can be checked by hand (god forbid), or else checked by a simple procedure. Understanding that a theorem prover is implemented correctly is tough, but understanding that a checker is implemented correctly isn't. I trust such proofs more than I trust hand-checked proofs, because humans are more susceptible to mistakes than computers are.
Most people probably knew the "four quadrants of knowledge" thing, but didn't know they knew (DK). That is, they have enough to put it together, but have probably never put it into words before. Intuitive knowledge is one way of putting it. The bulk of most people's knowledge probably falls into this category, which is fine - language is often overrated as a conduit of knowledge (not that it's not incredibly useful and important, but other means exist and are constantly used).
;)
I don't actually believe particularly firmly in that model, though, because I don't agree with the D-K dichotomy that underlies it. It's your usual classical Greek quadrant, which means it springs from a dual dichotomy, or in this case a dual-aspect single one. Dichotomy (or even one-dimensional spectra) is not the only way to look at things, but it is a dangerously compelling model - that is, when people have been presented with a dichotomy, they typically become unable to consider without it. And the defence of a dichotomy is usually a tautology - I mean it's obvious, isn't it, you either know something or you don't?
Still useful and interesting if you can get it out of your head when needed, though.
'Can we trust the darned things?' 'Can we know what we know?'
It's not an issue of can we trust them, at least not in general. (We won't go into the question of current machines - I'll agree they're generally not there for rigorous proofs.) We're going to have to either trust some form of computation aid in proof work, or throw up our hands and abandon the field - the human brain and lifespan impose definite limits beyond which we cannot go without aid, and since I can't think of any limit human beings have willingly accepted as a group somehow I doubt this will be the first. So, instead, the question should be
"How do we create computers we can trust?"
If that is impossible, then that's it. Mathematics will be come like experimental high energy physics - 20 years effort by 100s of people to achieve one result. But I'm not ready to concede that its impossible. I know it is provable that computers can't solve all problems in general, but the same proof indicates humans can't either. The question I'm curious about is whether the behavior of a computer is too general to be attacked by useful proof methods. Most actions taken with a computer assume a definite action and a definite outcome (spreadsheets and databases, for example, do not do novel calculations but perform the same operations on well defined data.) Mathematical proof is a different question, but the ultimate question is whether a properly designed and built computer (i.e. built as rigorously as possible in a technical and algorithmic sense) would be completely unable to handle problems that are interesting to human beings in the proof field. That is a completely different question from generality statements, and from the standpoint as computers as a trustworthy tool I think it is the more interesting one.
"I object to doing things that computers can do." -- Olin Shivers, lispers.org
"On two occasions, I have been asked [by members of Parliament], 'Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?' I am not able to rightly apprehend the kind of confusion of ideas that could provoke such a question."
-- Charles Babbage (1791-1871)
Computers only do what they are told (excepting "hardware failure", which is not the topic).
Shouldn't the validity of computational proofs be able to be determined by proving the meta-logic of the solver?
i.e. proving that a strategy for finding a proof is valid (and therefore trusting its results).
Maybe those wary mathematicians are just unaccustomed to working on a problem meta-logically, and prefer to find proofs directly themselves (with the meta-logic being defined solely within their own minds)?
In such cases, perhaps peer review should not require human verification of a computational proof, but rather another independent meta-logically valid computational proof?