11 ms·
Why is writing mathematical proofs more fault-proof than writing code? (2011)
- lainon 9y agoIt was posted dec 11 2017, not dec 2011 :)
- bor0 9y agoAs the top voted answer says, proofs are at a very high level compared to programming. Now imagine writing proofs on a very low level (check Metamath) where you work with wff and rewrite rules. It gets as tricky as programming.
- graycat 9y agoNice observation. What really matters is the actual thinking about the actual subject. In nearly all math proofs, the writing is closer to that thinking than in coding. Or, each sentence in a math proof -- and well written proofs actually are written in sentences -- is closer to the thinking than for the programming language statements in the coding. Or, look at the statements in the coding -- without mnemonic identifier naming, they are close to just gibberish. To get the coding closer to the thinking, that's the documentation in the coding. However the documentation is usually not as precise as the sentences in a math proof or the statements in code. So, maybe we need to do something to get programming closer to the real thinking: For this, maybe try to have what we use in programming to be easier to describe. That is, in a math proof, we have numbers, sets, vectors, functions, etc. and at each point in the proof see clearly what these mean. In programming we have variables, arrays, structures, IF statements, loops, subroutines, and without documentation or careful reading don't see clearly what these mean. Once I tried: I wrote some subroutines for sorting, permutations, etc. and tried to have clear properties for the operations the code die, properties that could reason about. Then for some uses of these subroutines, could do some logical reasoning much like in algebra in math. I didn't go very far with that idea!
- nerdponx 9y agoWhy the hell are you being downvoted? I really appreciated this line of thinking.
- zzzcpan 9y agoBecause he argues under the same incorrect assumption that writing mathematical proofs is more fault-proof than writing code. Which is what the answers on stackexchange are partly about.
- moocowtruck 9y agoi think he's arguing that it gives us a more precise language to describe our documentation than just regular comments, not that mathematical proofs are fault proof
- posterboy 9y agoI liked this part of one answer especially > Still, I hope that this sheds some light on the question that is implied: "What really is the difference between proving some theorem and writing a program?" (To which a careless observer of the Curry-Howard correspondence might say: "Nothing at all!")
- sorokod 9y agoBoth theorem proving and programming operate on an abstracted view of reallity ( in case of mathematics this reallity is often determined by some choice of axioms). By some metric the abstracted reallity of programming tends to be more complicated and noisy than that of mathematics.
- auggierose 9y agoThe answer is simple. In Mathematics you operate on a much higher level of concepts, and these concepts don't just fall out of thin air, but were sometimes decades or centuries in the making. In programming though your concepts are made up very much on the fly (if you bother developing concepts at all; usually you just use your framework of choice and hope it got enough concepts baked in so you can survive), and therefore often not very good and coherent. That means you can not rely on them for any kind of correctness assessment.
- JohnStrange 9y agoIt's not just that, people spend way more time going through mathematical proofs, finding, and formulating them. If you give programmers time to muse about every function for weeks and write no more than 50-100 pages of program text per year or even less, then their programs will be almost bug free. You get what you pay for. Note: I'm not claiming that programmers should be treated like mathematicians or vice versa, I'm merely pointing out the differences of the activities. Edit: There is of course also a more trivial reason. On average, research mathematicians are probably more intelligent, skillful and diligent than typical programmers.
- auggierose 9y agoAs I said, concepts don't fall out of thin air, it takes time to come up with the right ones. This is the major part of doing mathematics, once you got the right concepts nailed down, the proofs fall out basically automatically.
- peoplewindow 9y agoProgrammers are less intelligent, skillful and diligent on average than research mathematicians? How do you figure that? This statement appears to rely on a circular definition of intelligence - maths is "hard" therefore people who do it must be "intelligent". Given the examples in the linked discussion of cases where not only did mathematicians write buggy proofs but it took years to figure out a mistake existed at all, let alone what it was, I find it hard to believe that. To the extent it may appear superficially to be true it's likely the result of the academic setting in which there is no connection to real world relevance and the only pressure that exists to get things done comes from peers and the need to publish papers - but if those papers achieve very little and your peers papers also achieve little, that's totally OK. Compare to the world of the working programmer who is judged not by how fast he writes code but by the real world positive impact of that code, and it is easy to see how the mathematician may come across as more diligent or intelligent. But it's just an artifact of the pressure-free environment. I was also surprised to learn that the idea of checking mathematical proofs using Coq is considered just as exotic or impractical as checking programs. I had thought that Coq and other proof assistants were in wide usage for this use case, as surely pure mathematics is simpler to reason about formally than entire programs ... but apparently not. The fact that maths proofs are still mostly checked by hand, whereas machine-checked proofs (like static type systems) are widely used by even novice programmers, is hardly reassuring.
- dnautics 9y agoBecause in mathematical proofs the preconditions are usually explicit and well understood. A program usually has reality-bound constraints that are not explicit, e.g. "does not work unless the target system has at least 3.5mb of memory" or "assumes that opcode X never fails" or "assumes memory is consistent and never is corrupted"
- Peaker 9y agoPrograms could be explicit about those constraints, encode more of them statically and check them statically.
- traviscj 9y agoEverything has a failure rate. This introduces another set of heuristics (and another false-{positive,negative} rate), another set of potential implementation bugs in those heuristics. What if being able to run the program on a particularly memory-limited computer could save the universe, even more slowly than the project manager originally wanted it to run? Statically encoding something like a memory constraint sounds very hard for all but the simplest algorithms. What about a randomized algorithm that sometimes uses more heap? How do you get around not knowing how much it's going to use without running it?
- Peaker 9y agoAllocate for the worst case use in the bss. The program's static size indicates explicit memory requirements.
- nickpsecurity 9y agoThat's Design-by-Contract. On checking side, one can generate tests from specs, static analysis, turn them plus code into verification conditions to feed to solvers, or inputs to theorem prover for handling complex stuff. Eiffel implements DbC with test generation. SPARK Ada does automated and manual proofs. Ada 2012 added contracts but idk tool support. Many languages have ways of emulating this functionality, too. What you're describing is essentially a proven, lightweight, formal method for improving software quality. Many commercial apps use it.
- dukeflukem 9y agoWith maths the requirements are made by other mathematicians. With code they come from the real world. QED . []
- setra 9y agoThese days programming languages actually are used for expressing proofs. They can automatically check them to. For example the Coq theorem proving language. https://en.wikipedia.org/wiki/Coq https://en.wikipedia.org/wiki/Coq Some would argue that writing code IS more fault proof than writing proofs the traditional way.
- contravariant 9y agoI would still trust a mathematical argument I can understand over the output of some automated theorem prover. Of course these aren't mutually exclusive, provided the theorem prover is simple enough to understand.
- dtx1 9y agoAdding to the arguments present here already, it's also often easier to work with mathematical formulas and concepts compared to programming concepts. For example: pi. Easy in "math", effing hard to do in code. You don't have to worry about iee floats in "math". You don't have to worry about computational restrictions like ram, cpu time, null pointers etc.
- gpmcadam 9y ago[Meta] Why do people respond in the HN comments with answers to this question? Do people not realise that this is a post to a thread, wherein the value (and the answers) are in the original link, on stackexchange?
- soroso 9y agoNot really because the StackExchange thought police really does not let people freely answer the questions. It means in practice that if you write an answer not in alignment with the correct thought you get scolded and penalized.
- nerdponx 9y agoWhat? Answers there disagree all the time. You have an example of this kind of thought police behavior? In all my years on that site I have never seen anything like what you are describing.
- qubex 9y agoI’ve experienced it often. I came across a question pertinent to a problem I was experiencing, I tried the work-around in the comments, it didn’t work, I mentioned this and was moderated to oblivion and attacked; I created a new issue, and drew fire for then answering it myself (but also accidentally using a comment to do so); I got hollered at for creating a link between the two issues; I was downvoted for being new. It’s a totally hostile environment. As of then I consider it a Read-Only resource (plus my questions never get answered anyway).
- yorwba 9y agoIf you're also qubex on SO [1], then I'm not seeing any of that hostility. Did it get deleted, or is it that my perception differs because I'm an unrelated third party? [1] https://stackoverflow.com/users/3637244/qubex https://stackoverflow.com/users/3637244/qubex
- tzahola 9y agoBecause in a program you can't have functions having their implementation left as an exercise for the computer. :^)
- hyperpallium 9y agoI feel less confident of my proofs than my programs, because I can't run them, to see what happens. Yes, there are proof assistents like coq, but mathematicians look down on them. Proofs are usually about some very small thing, and require a tremendous amount of work. Then, there is a huge literature for guidance and reusable elements (though, a lot of work to use it), and peer review to check it (also labour intensive).
- nerdponx 9y agoI do not understand why mathematicians look down on proof assistants. I've heard this claim multiple times and it continues to make no sense to me. Are there any mathematicians here who can weigh in?
- znfi 9y agoNot really a mathematician, so take this with a grain of salt. I would guess there are probably several different reasons for "looking down" on proof assistants. On the one hand we have something like the 4-colour theorem where there is some kind of "proof", which is very large and incomprehensible. This is probably unsatisfactory to many because one is not really interested in just knowing that something is true, but ideally one also want an understanding of "why" something is true. This is, to various degrees, achived in more standard proofs. Another reason for disliking proof assistants is probably that they simply are very cumbersome to use and not very much can be proven with them so far. I would guess that even if you could get someone to admitt that the idea is cool and could be very useful, it's just not practical and for most people in mathematics it's just a distraction from what they are trying to work on at the moment. Compare with trying to convince someone that a flying car is really cool, yeah, sure, it probably would be, but so far it's basically sci-fi. If you want to work on building this, great, but most commuters will probably "look down" on your idea if you start bugging them about it.
- ufo 9y agoIt is a bit similar to why we don't use program verification tools very much in software development. They are very complicated to use and while they do a good job at verifying existing code they don't help as much when writing code from scratch, because they tend to add extra obstacles at this stage. From what I have seen, proof assistants in math are used when extreme rigour is desired (which is not always the case) and when working with extremely long computational proofs with hundreds of cases (where you need to work at a higher abstraction level; a human writes a program that outputs the proof and then the proof checker verifies that this extremely long step by step proof is valid)
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- CJefferson 9y agoI consider myself a bit of an expert in this area, I work on lots of mathematical algorithms. My experience is this isn't true. The reason it seems to be true is mathematicians will skip over writing out "boring" edge cases, which while hypothetically simple are often where the bugs occur in code.
- milesvp 9y agoFrom the people I've talked to it gets even worse than this when you cross domain or language barriers too. There are all kinds of implicit assumptions about variables that can get used in subtly different ways by convention, which were you to spell out said assumptions, you'd have a whole lot more places where bugs can occur in code.
- wbhart 9y agoThere are many, many errors in the published mathematical literature, and the older you get, the more of them you see. What I find even more amusing is when people don't withdraw their papers after you convince them their paper is fundamentally wrong, and they agree the argument can't be salvaged. I used to think of mathematical arguments that I couldn't follow as being "advanced" and written by "elite" people. I now consider them "heuristic" or worse still, "the spam of confused minds". At the top of various fields, you basically have a bunch of experts writing for each other, using heuristic arguments, and writing only to a level that will convince one another that the result is "probably true". Important results of great public interest are picked to pieces. But this is not true of less prominent work (of which the majority of the literature consists), probably each paper is read an average of 0.6 times, including by the authors and referees.
- dsacco 9y ago> There are many, many errors in the published mathematical literature, and the older you get, the more of them you see. Can you provide any examples? I know this is true, but I'm interested in examples you have off the top of your head.
- 9y ago
- EGreg 9y agoBecause the proof checker is a smaller piece of software to find bugs in, and used by more people so more people look. Simple.
- 0x445442 9y agox = x + 1 I remember the fist time I saw that line and said, that's false. And it's been an ever ending divergence from pure math for the past 30 years.
- goatlover 9y agoIt can also be: x <- x + 1 x := x + 1 But I guess since assignment is more frequent than equality checks, most PL designers opt for using equals. I do like R's left arrow assignment operator. If only keyboards had a default arrow character key. It would completely get rid of a class of errors based on forgetting the second equals sign.
- user5994461 9y agoA sane compiler always give a warning when doing a comparison outside a condition and when doing an assignment within a condition.
- aknoob 9y agoDepends on how you define fault here. Is it mere logical correctness of code or any error that might occur when code executes. If we follow former definition of fault then , they both are similar in being "fault-proof". If we follow later definition then execution environment of the program comes into play and it depends on a lot of variables and their complex interplay, that it becomes much harder to provide any formal guarantees of fault tolerance. However there are execution environments, read RTOS that try to be fault tolerant. Also various virtual machines like JVM,CLR try to provide fault tolerance to varying degrees.
- bocajuniors 9y agomathematical proofs have no side effects
- api 9y agoYou know all the preconditions and constraints ahead of time. With real world applied software that is very rarely the case.
- deleted 9y ago[deleted]
- eximius 9y agoCompare writing a proof in Coq to writing a normal program. That is far more equal in terms of what you're doing. Writing a proof for people implicitly assumes a mountain of background information and interpolation between statements that doesn't exist in programming.
- bsznjyewgd 9y agoBecause the interpreter for mathematical proofs is far more forgiving than the interpreter for code.
- ychen306 9y agoBecause it's not true :-) Writing mathematical proofs is as fault-proof as writing pseudo-code. Writing machine-check proofs is as fault-proof as writing code.
- yaseer 9y agoI think the line of reasoning is incorrect. Most mathematical arguments are actually not formal, in the way a program is a formal language. In many instances, there are not only ambiguities but errors in the mathematical expression. They only become formalised to an equivalent degree in a system like Isabelle or Coq. Writing proofs in Isabelle and Coq is essentially the same process as writing highly functional code, and is susceptible to the same arduous process. It's hard because it's a formal language running on a rigid machine. Programming would be easy if you specified everything in a semi --formal pseudo code, designed to be interpreted by a human mind that can fill in the blanks. This is what most mathematics is.
- vidarh 9y agoI often point out that exactly because of this, it's a red flag for me when I see a CS paper that relies on maths - it often indicates handwaving and missing details that would be a lot more obvious in code to the extent that I've learned to expect that if the paper is full of maths, chances are it will be a long, arduous process to try to reconstruct what the paper is actually doing. Often it extends to missing out essential details, such as values of important constants and the like.
- frozenport 9y agoAnother similar vantage point is that that the math can have no relation to what's actually happening. For example, the author might indicate in one step they invert a matrix, but instead use some heavily regularized solver. It might be that only a few eigenmodes are invertible which changes the physics of the problem.
- majos 9y agoAs someone who's worked a bit in theoretical CS, I think this is attributable to theory's different culture. In theory the focus tends to be more on intrinsic qualities of the problem in question -- does there exist a polynomial time solution? a sublinear time solution? how is it like or not like other problems? -- and less on clever engineering ways to optimize the constants in the problem, which is why the implementation (and its attendant constants) often seems like an afterthought. This is more useful than it sounds, since studying problems themselves can often lead to generalizations ("ah, this is NP-hard") that let you import plug-and-play knowledge ("we shouldn't expect a polynomial time solution"). But yeah when it comes time to implement/simulate, papers that are hand wavey with constants get annoying.
- solomatov 9y agoI had experience both of writing programs and writing proofs including proofs in formally verified languages, e.g. Coq, Agda. First of all, I think that the author underestimates the complexity of writing correct programs. What if integer overflow occurs? What is some exceptions happens somewhere? Programmers rarely consider all the pathological cases, while mathematicians must consider all of them. If program works most of the time, it's good enough for programmer but not good enough for mathematician. Second, thanks to Curry Howard Correspondence, every formal proof has a corresponding program which 'constructs' a result of the theorem from preconditions, so, the proof is basically a program (and vice versa in a typed programming language).
- willtim 9y agoMost programming languages are unsound logic systems which allow us to prove true==false rather too easily!
- fpoling 9y agoIn mathematical theorems the initial conditions are rather uniform without much if any of special cases. Thus mathematical proofs needs typically much less control flow to cover the initial conditions than computer programs. In fact many proofs are just straight deduction without single if to cover corner cases. Such type of "code" is simple to check. One just checks for logic of deduction, not the coverage of all initial conditions.
- mcguire 9y agoPosted 11 Dec, 2017, not 2011.
- totemizer 9y agomath resides in the land of abtractions(fantasy land) and actual code has to run on actual physical machines in the real world. In the real world you can't just state an axiom and fix bugs as math people have solved all their problems in the past 150 years.
- majos 9y agoWhat? If this is true then there are a whole lot of misguided mathematicians out there working on "solved" problems. If they could just add whatever axiom seemed useful math research would be meaningless. If you're saying that math/theoretical computer science makes unrealistic assumptions, that's a different (and more reasonable) claim.
- totemizer 9y agoThat is not what I said. What I said is that math ultimately doesn't need to and doesn't want to deal with reality. The "proofs" they create do not even have to be consistent with each other, you can pick whatever you need...
- Maro 9y agoI think it's not an apples to apples comparison. In mathematics, there are abstract concepts like integers. For any i, i+1 is also an integer. In programming, there is a MIN_INT and MAX_INT. If you write i/2, it's different than i/2.0. If you store a long string in a database, the column may be cut off at 32 chars because of the column type. Running string algorithms that sounds perfectly reasonable on ASCII may result in weird outcomes on Unicode. Most of these things also depend on the programming language, the compiler (MS, gnu, etc), the compiler version, OS, libraries, sometimes even the locale! A provably good crypto algorithm may be vulnerable to side-channel attacks. A mathematician may be happy to give an existential proof, but a programmer needs an implementation, and one that is polynomial [usually]. And so on... The tldr is, the real world is more complicated, limited and nuanced than the abstract concepts of mathematics.
- imranq 9y agoJust peruse any upper level undergraduate math text. Flip to any proof and you’ll find “it follows naturally that...” The bane of my existence as a math undergrad.
- ejz 9y agoOne extra element I'd add is that what counts as an error in a proof is different than what counts as a bug. In pure math, an error is a strict failure of logic that breaks the proof. In programming, a bug doesn't need to only refer to something that stops the code from working. I've also heard it referred to as something that stops the code from working properly or efficiently, for instance. Mathematicians don't care about that because they have a different goal than a programmer, that is, to prove the truth of something (though some are motivated to produce more "elegant" proofs).
- ttty 9y agoNot sure if really related but I couldn't follow the math at school. For example in algebra the rules were complicated and required you to know things that are not explicitly set. Because of that I wrote my own functions to do what my teacher said. Then in the exams we are allowed to bring formulas, therefore I bring my own JavaScript function and I was the compiler :) The teacher steps would resume in 5 sentences, but the function would be more long and include exceptions and weird cases. No room for mistakes with my JavaScript. No wonder I had the biggest score in the classroom.
- alangpierce 9y ago> I've never heard of someone who wrote a big computer program with no mistakes in it in one go, and had full confidence that it would be bugless. I've actually done this a number of times before, but only in the ACM ICPC programming contest, so maybe a difference here is the environment in which people write programs vs proofs. In the contest, you have a team of three people and only one computer, and if you submit an incorrect solution, the only response you get back is "Wrong answer" with no detail about what test case was wrong. The typical way that teams approach this is to write code out completely on paper, then transcribe it from paper to the computer, run the provided test cases, and submit. Computer time is valuable, so if you run into a mistake that you can't figure out, it's common to print your code and look through the code on paper rather than trying to debug it on the computer. When you train enough in an environment like that, you learn to be very careful about all of the details of the program you're writing. A single mistake can dramatically increase the time it takes to solve a problem, and there's pretty much no opportunity to "try it and see" like there is in normal programming. Also, the simple act of writing code down on paper and then copying it into the computer (double-checking as you go) gives you much more time to notice mistakes. Mistakes are still common, of course, but I've had a number of times where I write out a program on paper, type it into the computer, compile it with no errors, run the sample test cases and have them all pass, and then submit it and and see that it's correct. I've never experienced something like that in any other programming environment, including other programming contests, which typically let you write your code on the computer. Proofs tend to be the same type of environment: you write it out, with no compiler to help you, and you have plenty of time to read through it over and over before you have someone else check it for correctness. Maybe that sort of environment forces a level of care that you don't see as much in programming.
- jondubois 9y agoWith maths, you're merely discovering something which already exists. Programming is more like you're creating something new.
- ajarmst 9y agoBecause we generally only accept mathematical proofs from highly-trained experts, and no one would hire the kid next door, who taught himself math and seems to spend a lot of time fooling around with calculators to do professional work in mathematics?
- yakitori 9y agoBecause one is dealing with abstract theory with specific rules vs engineering in the real world. One exists in the world of abstraction while the other lives in the real world. Might as well ask why we can have a perfect circle in math while a perfect circle doesn't exist in the real world.
- shrimpx 9y agoI don't agree that mathematical proofs are more fault-proof than code. Mathematics is based more in the "spirit" of the idea and proof, rather than pedantically driving things down into the ultimate nuts and bolts. Many paper proofs are likely full of bugs deep in the details. As intuitionism and machine formalism develop, and the standard of rigor rises, we might see entire branches of mathematics being relegated to the dustbin of historically interesting human endeavors but totally useless as foundations/formal assumptions for future work.
- gerbilly 9y agoTwo words, iteration and conditional execution. Most math lacks these features common in programming. With iteration you blend the results at time t with the results at time t+1. Because of conditionals (if statements), a programming mistake at time t may not become evident till some much later step in the iteration, because the path through the logic is not guaranteed to be consistent. Typically the data of all intervening steps has been lost by the time you encounter the error.
- wccrawford 9y agoIf I spent as much time on a few lines of code as I spent in high school on a few lines of a proof, they'd be just as bug-proof. Nobody is going to pay me to spend that kind of time on that little amount of code. Heck, I'm not even going to spend that kind of time on my own projects.
- hyperpallium 9y agoI like the Lamport answer, implying that proofs are just as faulty as programs, they just don't get tested https://cs.stackexchange.com/a/85362/23759 https://cs.stackexchange.com/a/85362/23759 One might say the amazing thing is that many (not all!) such theorems are correct, despite the errors. Somehow, mathematical insight sees the truth, despite formalism failure... But, by this standard, most programs are "correct", they just have some inconsequential errors. I think this goes to a systemic problem in mathematics, that proofs are not very rigorous. I've never found one convincing. Instead, math is slightly like English Literature, where you learn "theories" that are held to be true by the community. You get inducted, and off you go. It's not purely objective. Of course, this doesn't explain the usefulness of mathematics when applied to reality, so I only claim it's "slightly like" an Arts subject. Perhaps some survivor bias, and engineers fix any problems.
- umanwizard 9y ago> I think this goes to a systemic problem in mathematics, that proofs are not very rigorous. I've never found one convincing. Instead, math is slightly like English Literature, where you learn "theories" that are held to be true by the community. You get inducted, and off you go. It's not purely objective. This is an outrageous exaggeration.
- sunstone 9y agoVery few real time interrupts in math proofs.
- Edzus124 9y agoIndividuāls risinājums tavam biznesam ar Aizdevums biznesam https://www.cityfinances.lv/ https://www.cityfinances.lv/
- vorotato 9y agoI think the resounding answer has been over the years that written proofs aren't more fault proof, they're just better at hiding the faults because they lack explicitness. There has been a recent push for formal verification because it's easier to actually find issues with the proof.