laziness, impatience, and hubris PerlMonks

### Re^2: OT: Mathematics for programming (again)

by TGI (Parson)
 on Sep 10, 2008 at 22:48 UTC ( #710483=note: print w/replies, xml ) Need Help??

Is this an extension of the Curry-Howard isomorphism?

If so, as a corollary your statement "Just waving a mathematical wand and saying we have a proof doesn't mean that we're right" is equivalent to Dominus' (in)famous statement that "You can't just make shit up and expect the computer to know what you mean".

TGI says moo

• Comment on Re^2: OT: Mathematics for programming (again)

Replies are listed 'Best First'.
Re^3: OT: Mathematics for programming (again)
by tilly (Archbishop) on Sep 11, 2008 at 00:16 UTC
That isomorphism is interesting, but orthogonal to what I was trying to say. I would say that your point is part of the reason why there is such a good parallel between doing mathematics and writing programs. However the point that I was trying to make is that our customary way of doing mathematics is like programming where you only outline the program. You don't write it out completely, you don't run it through a compiler, you don't do QA on it. You just do desk checking on a program that has never actually been written and convince yourself that it would work.

If I wanted to draw a parallel to a famous quote, I would go with Knuth's, Beware of bugs in the above code; I have only proved it correct, not tried it.

I don't know that they are orthogonal, one follows from the other. Here's the logic as I see it:

1. A proof is a program.
2. A mentally validated proof is a mentally validated program.
3. Mental validation is insufficient to verify programs are correct.
4. Therefore mental validation is insufficient to verify proofs are correct.

There's all kinds of work in formal methods for creating provably correct programs. It seems like you are calling for the converse: computer verifiable proofs.

I'n not sure how you'd do this, but I think you'd need to have some notational system that encompasses all of mathematics to start. Where are Russell and Whitehead when you need them? :)

Automated verification of proofs is such a good idea that it looks like people are working on this now.

Your argument for automated verification of proofs is persuasive. Thanks for bringing the idea up, it has provided me with some interesting things to think about while procrastinating.

TGI says moo

Alright, say you program a computer to verify a hairy proof (one example is the four-colour theorem that was proved in 1970s in this way). How do you know the computer works correctly? How do you know the verifier program works correctly? How do you know you encoded the proof requirements and all prerequisites and lemmas correctly?

People have been working on automated proof verification ever since the computer was invented. It is going somewhere, but the validity of such proofs is questionable. You have to accept that a proof can be considered verified by an agent, which encompasses both humans and machines. Machines do not have independent thinking; they are programmed by people, who may and will make errors in the programming. Even if you verify the proof with different machines programmed by different people, they may still all fall prey to the same oversight, and the computers will happily churn the incorrect answer.

Also, the first step in your insufficiency proof is questionable. True, many proofs can be dressed up as linear sequences of statements, expressions, and conditionals, but that's where the analogy ends. More correctly, at the very abstract level a proof is a sequence of transformations from given statements to desired statements. There is no computational state involved, nor any sense of input or output. Rather the prerequisites of the proof are the input and the results the output, and you, the verifier, are the actual program.

--

Create A New User
Node Status?
node history
Node Type: note [id://710483]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (3)
As of 2017-08-22 02:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (327 votes). Check out past polls.

Notices?