3 ms·
Do we have any examples of proofs that are "unsuited to human mental processes," except by being long and tedious?
by whatshisface 6y ago
Do we have any examples of proofs that are "unsuited to human mental processes," except by being long and tedious?
- gregorygoc 6y agoLong and tedious is the definition of an unsuitable human mental process.
- jerf 6y agoI don't think we'd currently have any way of producing such a thing, because the two processes we have are 1. producing proofs suitable to human mental processess and 2. producing long and tedious proofs by a series of steps programmed by humans in the first place. Although it also depends to some extent on your definition of "suitable to human mental processes"... for instance, the famous proof that produced Graham's number is not "unsuitable to human mental processes" in the meta sense, but if you try to directly apprehend Graham's number with human mental processes, you fail. You can comprehend it and manipulate it mathematically, but you can not apprehend it.
- mikedodds 6y agoI don't know if there are proofs unsuited to human minds, but for machine proofs, there's no essential difference between what a proof assistant like Coq can do, and what a human brain can do. Ultimately Coq boils down to a very simple core logic that could (in principle) be checked by a human. But the sheer scale of such proofs means they can't be meticulously checked. Proof tools are just the same as e.g. compilers - they can do things humans can't do because to do so would be so incredibly time consuming and tedious.
- jacobr1 6y agoAn analogy might be chess with derided "computer moves." The aren't necessarily more complex that existing human heuristics, especially at the grandmaster level, but they lack at least one of several traditional "aesthetic" attributes. I'm not all that familiar with generated proofs, but from those I've seen, they will point our pedantic linkages other proofs might avoid. I suspect that can easily be overcome though be building-in aesthetic conventions in the proof presentation layer, such as we do today with ASTs and compiler optimizations. Wild speculation: automated proofs use assembly constructs and goto's when they could be using higher order constructs - but this isn't always clear because there isn't a separation of abstraction layers (or a least a a clearly articulated one). I could imagine a project that regenerated many well known proofs (these exist in form in the solvers already, but these are intentionally redone) without some of the existing heuristics abridgments that exist in the solvers. Then pair them with the human curated proofs of oft-considered elegance and train a system to convert from one to the other.
- Someone 6y ago“An analogy might be chess with derided "computer moves." The aren't necessarily more complex that existing human heuristics, especially at the grandmaster level, but they lack at least one of several traditional "aesthetic" attributes.” I think there’s a possibility that’s cultural. Generations of chess players grew up learning certain heuristics. Now, computers show those heuristics aren’t as good as we thought they were. It’s possible that new generations, trained more by computers than by older generations of chess players, will develop new heuristics. You see something similar in math. Sometimes, when a human discovers a new way to look at a problem, whole avenues of proofs open up, and what was incomprehensible becomes much easier not only for that human, but also for those learning about his work. On the other hand, I think computers sometimes make moves humans won’t make because they don’t have any notion of fear. When humans get into a minefield position where almost every move is clearly losing, but that do have one winning path through it, they may not choose that path even if they see it because they fear they’re overlooking something.
- Penyngton 6y agoHere <https://cacm.acm.org/magazines/2017/8/219606-the-science-of-brute-force/fulltext https://cacm.acm.org/magazines/2017/8/219606-the-science-of-...> is an article about a computer-generated proof of a combinatorial problem in number theory. Although you could characterise the proof as "just long", I think that the article may offer a different perspective on why proofs of this nature are interesting and useful.