2008 Turing Award Winners Announced 66
The Association for Computing Machinery has announced the 2008 Turing Award Winners. Edmund M. Clarke, Allen Emerson, and Joseph Sifakis received the award for their work on an automated method for finding design errors in computer hardware and software. "Model Checking is a type of "formal verification" that analyzes the logic underlying a design, much as a mathematician uses a proof to determine that a theorem is correct. Far from hit or miss, Model Checking considers every possible state of a hardware or software design and determines if it is consistent with the designer's specifications. Clarke and Emerson originated the idea of Model Checking at Harvard in 1981. They developed a theoretical technique for determining whether an abstract model of a hardware or software design satisfies a formal specification, given as a formula in Temporal Logic, a notation for describing possible sequences of events. Moreover, when the system fails the specification, it could identify a counterexample to show the source of the problem. Numerous model checking systems have been implemented, such as Spin at Bell Labs."
Re:Just moves the errors up one level (Score:5, Interesting)
The DoD has funded these efforts heavily since the 1970's, and computer science graduate students have been all over them for as long as I can remember. I've read way too many dull papers on the topic, as one amateur modern algebraist after another discovers the wonders of Hoare and rushes into print with his or her "unique" twist, all to the end of starting yet another unremarkable academic career.
Of course, the illusion of "perfect" software never fails to amuse me, since I remember an Interdata 32 overheating in the lab and making serious fixed point arithmetic errors. Sort of grounds one in reality, doesn't it, when the machine can't add. Sure glad the program was declared "correct," though.
Congrats to Ed. (Score:1, Interesting)
PS: Too lazy to create a slashdot account, so posting as an AC, besides, what's there in a name.
Re:Just moves the errors up one level (Score:4, Interesting)
I hope your prof failed you.
I dropped Emerson's class (Score:4, Interesting)
Re:Just moves the errors up one level (Score:5, Interesting)
Once I went to a talk about applications of model checking to the verification of software. A programmer was constantly changing a state-based algorithm for call setup in a telephone switch, and was having trouble keeping it correct. Enter model checking. Two people wrote temporal specifications of call setup, and every night or so, they'd grind the model checker on the latest version of the code. No, that didn't prove the code was correct, but it did catch an enormous number of bugs in a tricky piece of concurrent code.
Oh. The programmer was Ken Thompson. The people applying the model checker were Gerard Holzmann (the designer of SPIN) and Margaret Smith.
I'm not saying the technology is applicable everywhere, but you gotta give Clarke, Emerson, and Sifakis a lot of credit for opening a good door.