4 ms·
For brute force proofs, the proof basically nothing to do with the output of the program. I'll explain: A mathematical proof is just some utterance or depictio
by justin_vanw 17y ago
For brute force proofs, the proof basically nothing to do with the output of the program. I'll explain:
A mathematical proof is just some utterance or depiction that will convince your audience that you have proven something. The actual utterance that might 'count' is totally dependent upon who is in the audience. If you are a topologist and you are talking to another topologist working on very similar stuff, your proofs would be incomprehensible to even other mathematics researchers, who could not determine if you were giving a valid proof or not, while the other topologist could easily tell.
If your audience is a really smart physics professor, that same topology proof would have to suck in many other facts, and explicitly quote accepted theorems, or you would risk the physicist jumping up and saying "not so fast" every time he see's a break in the reasoning. At least the physicist will be comfortable with the existence of theorems.
Now, a proof of the same thing, given to an alien with an IQ of 5000 but who's race never thought up the concept of a theorem would be exquisitely painful. You might have to actually give the proof of each theorem you use, and each theorem each of those theorems use. Otherwise, he would say "your logic is flawless, but you assume facts you have not proven, so this proof is incomplete."
If people were way smarter, proofs would be way shorter, since nobody writes down things that are really obvious. Nobody says something like "since the real numbers are commutative under multiplication..." because there is no need to say it. If people were 50 times smarter or something, way more complex things would just 'go without saying'.
So, what does some kind of brute force proof really consist of? It's a program that runs on a computer generally. So the proof is really the source code. If people are convinced the program does what you claim, and then you run it, that is certainly a proof.
If you can't count that, you also can't count any other non-constructive proof. I would say that they are basically pointless, since you can use the result of the proof in other proofs, but you can't build on it very much.
- eru 17y agoI agree with your notion of "proof as conversation". That's the way presenting proofs verbally works in practice. (And I am a mathematician.)
- justin_vanw 17y agoI got most of this from conversations with Rich Schwartz. http://www.math.brown.edu/~res/ http://www.math.brown.edu/~res/
- hc 17y agono, this is really begging the question. youve reduced "the proposition is true" to "the algorithm is correct, and the algorithm returns 'true'". once you prove the former you still have to do the hard part of actually _proving_ the latter. i suppose this amounts to mathematically proving, among other things, that your pentium 4 or whatever is incapable of executing a program incorrectly.
- justin_vanw 17y agoYou miss my point completely. You are thinking that mathematical proofs are like airtight and completely unassailable and locked in for all time. In reality (practice) they are pretty sloppy, and are really just a form of persuasion. Now, persuading a group of mathematicians to believe a claim is a high bar, and they are very good at finding logical holes, gaps, and mistakes. As Nietzsche points out in Beyond Good and Evil, it is quite possible that humans as a species have all sorts of blind spots in our reasoning abilities, and that such blind spots are essential for life itself. In fact, we know of many of these blind spots, or failures of human reason. One great example is the Monty Hall problem. Others are the lottery, gambling, stock market events, advertising (the effects of), and all sorts of experiments that economists do these days. So before you get concerned about the Pentium IV's accuracy, and 'mathematically proving' it is correct, consider that your brain is a very imperfect reason engine, and there is no reason to suspect that our intuition is accurate except in (and still imperfectly in) those situations where those intuitions improved the reproductive chances of our ancestors.
- justin_vanw 17y agoOh, I just made a huge howler. >...our intuition is accurate except in (and still imperfectly in) those situations where those intuitions improved the reproductive chances of our ancestors That actually contradicts my point. Our intuition and reasoning powers did not evolve toward accuracy or better understanding the world, it evolved purely toward whatever kept our monkey ancestors out of lion mouths. Sometimes that could have caused our primitive ancestors to believe that they could only safely cross the plains while holding magic rubaduba fruit. This would of course be reinforced, since perhaps the rubaduba fruit only is on trees in the one month a year that lions are far away looking for water. The proto-humans who believed the rubaduba bullshit survived because they were able to pick up on a correlation, but they only acted on it because they believed in causation, meaning we our ancestors who thought the rubyduby fruit theory was idiotic got eaten by lions, while the credulous saps who filled sacks with 50 pounds of inedible crap and carried it across the plain were fine. This is a just-so story, but the point is illustrated, which is that not only do humans have terrible reasoning ability when it comes to money and anything remotely scary, it's quite possible we evolved specifically towards irrationality in certain situations. There is billions of dollars spent studying this every year, it's called marketing.