6 ms·
Sure, "proof mining" is feasible, but the goal of proving a theorem is only rarely finding any proof, it is rather finding a proof that makes sense, is "elegant
by Koshkin 9y ago
Sure, "proof mining" is feasible, but the goal of proving a theorem is only rarely finding any proof, it is rather finding a proof that makes sense, is "elegant", and in the best case scenario a proof that actually forms a sensible new theoretical framework in which the theorem becomes almost trivial to prove.
- raverbashing 9y agoNot really A proof that works is the most important part. After that you can make it nice
- Koshkin 9y ago> you can make it nice Not the 200 terabyte one, you can't.
- fosap 9y agoMaybe we can use the brute force of a "math superoptimizer" to "compress" it to something far more reasonable. If we teach said opimizer what structures are well understood by humans we might actually understand at last parts.
- nbates80 9y agoI don't know why people keep thinking there's something special about the way we humans do calculations vs what could be achieved with a complex enough computer
- AstralStorm 9y agoThese are not mere calculations. See, an understandable proof has more structure than plain first order logic alone. This allows such proofs to be extended and worked upon as well as real life implications to be discovered.
- fosap 9y agoMath is not about proofing something, or creating a as big as possible collection of lemmas. Math is about creating structures that can use as tools to solve problems. And problem solving is a task done by humans, so math is only useful if humans understand it and have a intuition.
- CJefferson 9y agoI have a couple of experiences of doing similar big projects where we counted the number of some objects (I haven't checked how big they are.. I have run SAT solvers for a couple of weeks, I didn't try to record some "proof size", I imagine it would be as big if not bigger than 200 terabytes). Once I could tell a mathematician the count, in both cases someone they proved the result in an alternative way fairly soon afterwards :)
- hinkley 9y agoIt never occurred to me until just now that one of the AI overlord scenarios, and also quite possibly the most plausible one, is one in which AI just exploits some impenetrable proofs to win at economics via information asymmetry. Rather than rounding us up or exterminating us, we just become the live at home kid always begging for money, grumbling about a curfew and having to do chores at 25.
- ISL 9y agoIf something can be proven by any method, that means that it is true. An elegant proof is often more illuminating, but it isn't precluded by a direct method. If the proven theorem is useful, isn't it better to be able to make use of it earlier, rather than wait for the elegant proof? An example: If the AdS/CFT conjecture is demonstrably proven, it will elevate it from "useful computational technique" to "law of mathematics, probably how nature does it, too". I'll take any proof, as early as I can get it, in order to guide our experimental work.
- eric_h 9y agohttps://en.wikipedia.org/wiki/AdS/CFT_correspondence https://en.wikipedia.org/wiki/AdS/CFT_correspondence In case anyone else had no idea what the parent was talking about.
- groby_b 9y agoI still have no idea :) Wikipedia on Quantum Physics is usually pretty atrocious, and this page is no exception. It reads like... well, nerds showing off knowledge. (There's nothing wrong with that, but unless you're already pretty steeped in things quantum, the page is jargon without meaning) A more readable summary: http://whystringtheory.com/toolbox/ads-cft/ http://whystringtheory.com/toolbox/ads-cft/
- aisofteng 9y agoThat's because it's an encyclopedia, not a romance novel.
- dzamo_norton 9y agoThere's a point there that is obscured by the overreach to "romance novel": it's because it's a one-page encyclopedia article on a highly-technical and esoteric subject not a 300-page introductory textbook to be studied over the course of a year. Then again "If someone cannot explain something in plain English, then we should question whether they really do themselves understand what they profess." - Richard Feynmann
- roywiggins 9y agoIf you just care about the correctness of some algorithm, proving it is just tedium and not likely to produce a proof useful for reading anyway. So an exceptionally long, boring proof of correctness generated by a supercomputer is perfectly fine.
- nickpsecurity 9y agoThis sort of thing is standard in Frama-C and SPARK Ada for proving code to be safe from common vulnerabilities or crashes. I don't care what the proof terms look like: just that the code won't get hacked. Same with CompCert even though it's meant to be readable. I just want a correct compilation. Lots of situations where the result obtained is only thing that matters to most users.
- pmiller2 9y agoI would say elegance is often only a beneficial side effect of finding a good proof. A good proof is one that has explanatory value, and gets to the root of why the statement is true.
- dgfgfdagasdfgfa 9y agoErr—presumably the proof that makes sense is a correct proof. How is that not a binary quality?
- aschampion 9y agoIt means the proof is explanatory, i.e., that it provides a framework of thought that extends our capability to reason about related problems within our very limited cognitive envelope. Pure proofs, like purely predictive models in science, often do not provide this.
- scarmig 9y agoIs that particularly valuable, though? It seems like a pretty anthropic point of view to value an algorithm as more elegant just because inferior hardware is able run it.
- aschampion 9y agoIt's been a historically valuable heuristic -- algorithms/theories that provide cognitive scaffolding allow us not only to solve related problems but reason about the limits of applicability of that theory, successively guiding discovery of new theory. Obviously our cognitive envelope doesn't just include our own brains but the tools we use, including computational ones, so it's not as if pure proof/pure prediction don't also have value for guiding discovery, but it does require a lot of ingenuity to find ways to exploit them.
- Florin_Andrei 9y agoWhen proofs are creeping slowly into the petabyte or exabyte territory, at some point you will not be able to distinguish them from the complexity of Mother Nature herself. Proof used to be a distillation of a complex phenomenon, or a complex logical tangle, into a smooth thread that one could follow and agree that, yes, this is obvious when you put it this way. Sure, at some point computers will take over the work of doing proofs, just like in a different trade hammers took over fists, or wheels took over feet, or engines took over muscles, hearts and lungs. But at that point we will have to re-examine this concept of "proof".
- hellbanner 9y agoStart now and make your altcoin, seriously :)
- c3534l 9y agoThat's one goal of proving a theorem. It's still useful to know the answer ahead of time if you're going to prove it. And some stuff is useful to know anyway. Proving P = NP would be super important to know, even if no one actually understood why. In fact, there's countless theorems that depend on results which have not been proven yet. People may have been doing important work that relies on the Riemann Hypothesis because they incorrectly believed it was true and that time might have been wasted. Additionally, once you find a proof through exhaustive search, it's entirely possible that human beings can go in there and simplify it to a level that can be understood by people. And maybe multiple results might paint a picture that shows us a direction to go in that we wouldn't have guessed beforehand.
- awkwarddaturtle 9y ago> but the goal of proving a theorem is only rarely finding any proof No. The goal of proving a theorem is proving it any way possible. And "inelegant" proof is just as much a proof as an "elegant" proof. > and in the best case scenario a proof that actually forms a sensible new theoretical framework in which the theorem becomes almost trivial to prove. What?
- gizmo686 9y ago>> and in the best case scenario a proof that actually forms a sensible new theoretical framework in which the theorem becomes almost trivial to prove. >What? The idea is that, in creating the proof a mathematician invents a new way of looking at the problem. When viewed in this new way, the problem itself sometimes becomes trivial. When this happens, the the framework that was developed could be used to attack new problems that had previously been unapproachable.
- daveFNbuck 9y agoIsn't tossing a bunch of computational resources at a problem a new way of viewing it that makes it trivial?
- snakeboy 9y agoBut it gives no framework for approaching other problems under any kind of new unified theory.
- daveFNbuck 9y agoInstead it gives a framework that will solve fairly arbitrary problems as you work on developing a unified theory. Techniques can be much more broadly useful than theories. When I was working on my PhD, I probably saved days or weeks of effort by writing a program to brute force an approximate solution to an equation I couldn't work out. After seeing that the solution wasn't what I wanted, I was able to spend the time I would otherwise have spent on figuring out the equation on something more useful.
- joe_the_user 9y agoAs others have noted, finding the truth of a theorem is important and elegance has to be secondary in most people's book. Or at least, the truth of a proposition is never not going to be important. But oppositely, I don't think anyone's demonstrated "proof mining" to be practical in any general sense. Huge proofs have been produced by brute-force, yes, BUT ONLY after the original theorem claim was altered in a clever and important fashion (for 4-color theorem, for Ramsey's theory and so-forth).