Archived from groups: alt.video.ptv.tivo (
More info?)
>> Norm,
>> It is true many firms have an indifferent attitude towards
>> software QA. However mathematicians have shown anything more than
>> a trivial program (and we are talking 10's of lines of code)
>> cannot be proven correct. Joe
>Math and programming do not go hand in hand so are we talking a
>program that solves a math equation here because this just cant even
>be close to a true statement, if it was we would be in BIG trouble.
In that sense, you're right. We're in trouble. If you want to be
absolutely, 100% certain that an arbitrary computer program is
correct... you can't be.
It's surprisingly difficult to prove even some very simple things
about a program... like, will it ever produce an answer at all? (and
by "produce an answer" I don't just mean in the sense of solving a
math equation - I mean "finish its task" in a more general sense, such
as doing a database lookup). This is the famous "Halting problem",
first discussed in this context by Alan Turing back when he described
the first stored-program computer.
In short: if you want to prove or determine, by any sort of
"mechanical procedure" (e.g. going through physical or mathematical
steps, using deductive reasoning, etc.) that a Turing machine (a
programmed computer) will halt (produce an answer or complete a task)
on a given input... you cannot. The "Halting problem" is insoluble.
Turing showed (by drawing on an application of Godel's Incompleteness
Theorem) that there is *NO* procedure you can follow which will be
able to give you an accurate answer in all cases. The proof is an
interesting one... if there were such a procedure, you could "turn it
on itself" in an inverted way, and generate two contradictory answers
for the same problem.
So - absolute proof of correctness of nontrivial programs is
impossible. You can't even tell for sure whether the program will
produce an answer (do something), let alone whether the answer will be
correct (whether it'll do what you really *want* it to do).
Software developers have come up with numerous ways of helping find,
correct, or make-impossible-to-do a lot of the commoner mistakes in
software development - uninitialized variables, "leaks" in memory
allocation, storing data "out of bounds" and clobbering other memory
locations, and so forth. When applied properly throughout the design
and implementation of software, these techniques can greatly reduce
the number of potential bugs in the software.
Unfortunately, these techniques are necessarily less than perfect, and
are often not applied as well as they might be for any number of
organizational, financial, and social reasons.
Weinberg's Second Law: "If builders built buildings the way
programmers wrote programs, then the first woodpecker that came along
would destroy civilization."
--
Dave Platt <dplatt@radagast.org> AE6EO
Hosting the Jade Warrior home page:
http
/www.radagast.org/jade-warrior
I do _not_ wish to receive unsolicited commercial email, and I will
boycott any company which has the gall to send me such ads!
/www.nabs.net/Cartoons/Peanuts/TenPin.gif
Facebook
Twitter