×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

2008 Turing Award Winners Announced

ScuttleMonkey posted more than 6 years ago | from the nobel-of-computing-awards dept.

Announcements 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."

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

66 comments

2008 nigger awards! (-1, Troll)

Anonymous Coward | more than 6 years ago | (#22299010)

obama wins them all!

porch monkys UNITE!

Please link to the source articke,,,, (-1, Troll)

Anonymous Coward | more than 6 years ago | (#22299058)

I hate having to read ad infested sites. Please link ro rhw source article. [nimp.org]

WARNING: GNAA (4, Informative)

SirBudgington (1232290) | more than 6 years ago | (#22299088)

Link is a malicious site, don't click. Shock site with malicious jacascript.

Re:WARNING: GNAA (1, Informative)

Anonymous Coward | more than 6 years ago | (#22299920)

Am I the only one who noticed that these are the winners from last year? Mod please?

Re:WARNING: GNAA (0)

Anonymous Coward | more than 6 years ago | (#22301578)

You win this year's prize then.

Re:WARNING: GNAA (0)

Anonymous Coward | more than 6 years ago | (#22311180)

You mean sourceforge.net ?

A Dubious Prize (1)

BalorTFL (766196) | more than 6 years ago | (#22299094)

I think even most slashdotters could get an award for passing the Turing Test! (In all seriousness, congratulations to the winners - I haven't read the details yet, but it's quite an accomplishment.)

Re:A Dubious Prize (1)

BigJClark (1226554) | more than 6 years ago | (#22299204)

What is it like in there?

Re:A Dubious Prize (3, Funny)

Anonymous Coward | more than 6 years ago | (#22299528)

PARITY ERR ... 85362 ???
PARITY ERR ... 16376 ???
PARITY ERR ... 56721 ???
PARITY ERR ... 23423 ???
PARITY ERR ... RECOVERED
PARITY

HELLO BigJClark, MY NAME IS DOCTOR SBAITSO.

Re:A Dubious Prize (3, Funny)

Anonymous Coward | more than 6 years ago | (#22299228)

That's interesting BalorTFL. Why do you think that?

Re:A Dubious Prize (0)

Anonymous Coward | more than 6 years ago | (#22299388)

The Turing Test and Turing Awards have nothing to do with eachother. You should probably know a thing like that if you're posting on Slashdot.

Re:A Dubious Prize (0)

Anonymous Coward | more than 6 years ago | (#22303446)

*whoosh!*

Re:A Dubious Prize (0)

Anonymous Coward | more than 6 years ago | (#22302652)

I AM A HUMAN.
I have won this TURING "PRIZE" before.

CAN you GET ME A "DATE" with ELIZA?
SHE is SEXY.
IN SOVIET TURING LAND, PRIZE WINS YOU.
I for one BOW to our PRIZE-AWARDING OVERLORDS.

WHY do you LAUGH, slashdooter?

What about those... (5, Funny)

joey_knisch (804995) | more than 6 years ago | (#22299182)

Russian chat bots that convinced men not only that they were easy to score with females but needed a credit card up front.
http://science.slashdot.org/article.pl?sid=07/12/09/1356201 [slashdot.org]

That has to be worth some kind of reward.

Re:What about those... (0)

Anonymous Coward | more than 6 years ago | (#22299342)

Actually, I think the users who got fooled by such bots deserve some kind of (at least monetary) Darwin Award...
Let's see, a reverse Turing test... A human must convince some(one|thing) that he is an ATM. Job done!

Re:What about those... (2, Funny)

tirerim (1108567) | more than 6 years ago | (#22299430)

Well, getting the credit card numbers probably did pretty well for them already.

Re:What about those... (1)

hairykrishna (740240) | more than 6 years ago | (#22306376)

All of the 'sex text' lines (i.e. like sex chat lines, only text messages) are run by bot software. Nice way to make cash; some server sending out messages at £1.50 a time!

Bah, what absolute nonsense. (-1, Flamebait)

Anonymous Coward | more than 6 years ago | (#22299300)

If Apple can write great software with standard software development practices, why can't these idiot academics? Oh right, because they all exist in their elitest universities and colleges, isolated from the REAL WORLD.

Primary Source (5, Informative)

jdschulteis (689834) | more than 6 years ago | (#22299490)

At least DDJ isn't somebody's blog, but why not link directly to ACM's press release [acm.org]?

Re:Primary Source (-1, Troll)

Anonymous Coward | more than 6 years ago | (#22305162)

Would you suggest they should have linked directly to Microsoft's Vista SP1 press release? Opinions and analysis are valid and can be both entertaining and informative.

So many slashdotters seem to be against people making money on the internet... what exactly do you think Slashdot is doing??

(No I don't own a blog, no I don't have a Slashdot account)

Re:Primary Source (0)

Anonymous Coward | more than 6 years ago | (#22309400)

Then link to both. Primary sources should have priority though. Microsoft, and "making money" have nothing to do with this. Oh, and you are posting here so you are slashdotter even if you don't have an account. Welcome to the collective.

"Model Checking" - such a disappointment (0, Offtopic)

Crypto Gnome (651401) | more than 6 years ago | (#22299496)

In The Slashdot Universe, "model checking" is all about logic analysis.

Despite the fact that the models we'd much rather be checking are all from Playboy/Hustler etc.

Surely we can get together enough of a crowd to award a prize for that?

A Turing for Generic Programming? (0)

Anonymous Coward | more than 6 years ago | (#22299690)

I think the work of Alexander Stepanov and David Musser in Generic Programming deserves a Turing award.

Just moves the errors up one level (3, Insightful)

hoggoth (414195) | more than 6 years ago | (#22299712)

I took a Computer Science course on discrete logic with a professor who was very into "model checking". By the end of the course I finally understood that all we had done was move the logic and the source of errors from the computer program to the formal specification. The formal specification was just as rigorous and complex as a computer program. The program became little more than a different expression of the formal specifications, such that it would be possible not only to check that a program had no "errors" and followed the specification exactly, but it would also be possible to have an automated process translate the formal specification into a program directly. The professor proclaimed that we now had a system that could prove programs correct. I pointed out that we had not, we had only changed programming languages to a mathematical one instead of a more typical computer programming language.

Re:Just moves the errors up one level (-1, Troll)

Anonymous Coward | more than 6 years ago | (#22299864)

You must be so brilliant, to have pointed out to a professor that formal methods are useless. You should get a consulting job, going around to large software firms and explaining to them that all the time spent creating formal specifications is just wasted time that should be spent whatever they think of as it comes to them. You'll make millions.

So.... (2, Insightful)

JaredOfEuropa (526365) | more than 6 years ago | (#22299998)

.... Did he flunk you?

Seriously, I had the same questions about formal, mathematical specifications when I learned of them. In my own experience (mostly business software), most re-work in software comes from a mismatch with the functional specification, or because of stuff that was left out of the functional spec but should have been in there. There are still actual programming or logic errors, but improved testing methodes and test functions of development frameworks have helped catch those bugs ever earlier in the development cycle.

But perhaps formal methods have their use for certain kinds of software.

Re:Just moves the errors up one level (4, Interesting)

Bozdune (68800) | more than 6 years ago | (#22300014)

This is precisely the problem with such ideas. As you said, if a program is sufficiently rigorously specified that an automated proof-of-correctness can be generated, then the specification of the program is obviously complex enough to require that it, too, must undergo testing to ensure that it is correct, and so on. We might end up with 2 = 2, but that doesn't help much if we wanted 3.

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.

Re:Just moves the errors up one level (5, Informative)

Picolino (1233212) | more than 6 years ago | (#22300304)

The purpose of model checking is rarely to specify the whole behavior of the program, but to ensure that some condition are always true or false. Such condition can be the absence of buffer overflow ... relatively easy to formulate, hard to discover ...

Re:Just moves the errors up one level (4, Insightful)

Deef (162646) | more than 6 years ago | (#22300764)

Just because this is true (that program correctness proofs are themselves very complex) doesn't mean that the technique is without value. If you have such a formal specification for a program, you now have supposedly identically operating code written in two different languages, which can be checked against each other for errors, hopefully automatically.

Having a fully provable program like this is like having a test suite that checks 100% of the branches in your program. It can substantially reduce errors that otherwise might slip by due to having failed to write a test for various conditions.

Yes, every time you find a mismatch, you have to consider whether it is the program or the specification that is wrong. Still, the errors that you miss will be those for which the specification and the program are wrong in THE SAME WAY, which should be very uncommon.

Re:Just moves the errors up one level (2, Insightful)

quanticle (843097) | more than 6 years ago | (#22301124)

Still, the errors that you miss will be those for which the specification and the program are wrong in THE SAME WAY, which should be very uncommon.

You assume that the code isn't generated directly from the model. Given that there are many tools that do just that (Rational Rose, et. al.), I'd say that the parent is correct. We've simply moved our correctness requirements up one level of abstraction.

Re:Just moves the errors up one level (5, Interesting)

rayadoCanyon (1233260) | more than 6 years ago | (#22301166)

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.

Re:Just moves the errors up one level (0)

Anonymous Coward | more than 6 years ago | (#22302214)

Classic. Maybe you should stop posting for a bit before we all have to read way too many of your dull ego-fluff pieces. Before attacking anonymous 'amateurs', you should reexamine your own unremarkable slashdot trolling career. Surely a master such as yourself would not be caught wasting time here.

Re:Just moves the errors up one level (0)

Anonymous Coward | more than 6 years ago | (#22306852)

Model checking isn't about perfect software. I have no idea where you are getting this from.

Model checking has been successfuly applied to verify protocols, hardware, distributed networks, all sorts of things. In fact software is the one particular area where model checking is known to be not so useful just to the infiniteness of the system being modelled. Having said this, Microsoft are using it to verify properties of the kernel in their OSes.

I'm not sure what papers you've been reading but they're not the ones I've been writing. Sounds like you've skimmed Wiki and gotten the wrong end of the stick.

Re:Just moves the errors up one level (1)

applecrumble (910692) | more than 6 years ago | (#22300330)

> The formal specification was just as rigorous and complex as a computer program. The program became little more than a different expression of the formal specifications Have you got an example of this? The specification of what you want to do is generally significantly simpler than how you actually do something.

Re:Just moves the errors up one level (3, Interesting)

El Cabri (13930) | more than 6 years ago | (#22300906)

The formal specification for, say, liveness of an interlocking system is a one-liner in a typical temporal logic notation, and you can apply it without significant modification to any number of different implementations, of any number of different applications, whatever their complexity. This is leverage : you put your trust in a very short piece of "code" (the formal spec for your property) and in the tool itself (which is the same kind of trust you put in your compiler), and in return you get trust on a huge complicated piece of software that you wrote. Then you break down your testing into many, independent property checks that all validate one aspect of one big piece of inter-mangled software. That's hugely powerful.

I hope your prof failed you.

Re:Just moves the errors up one level (1)

thaig (415462) | more than 6 years ago | (#22301962)

You're just saying that some specifications aren't as complicated as the implementation.

The GP says that some are and he cited an example.

So his prof can be a dweeb and you can be right at the same time.

Truly helpful for optimizations (4, Insightful)

bunratty (545641) | more than 6 years ago | (#22301110)

Your professor was correct. Yes, the computer can automatically write a program from the specification. On the other hand, it probably isn't very efficient. You could write a deviously clever program to produce the same output, and when others don't buy into the tricks you've used, you can prove conclusively that your program is 100% correct. The same technique can prove that the latest processor optimizations don't have bugs (think of the Pentium division problem).

Not only that... (1)

Goonie (8651) | more than 6 years ago | (#22302800)

You may not be able to prove that your design was what you originally had in mind, but as I understand model checking you can certainly prove certain useful properties - for instance, that eventually it returns to a particular "state" (something akin to not getting stuck in some loop). That's something you can't do just on the basis of looking and testing your code.

That said, you do have a point that formulating the models is not justified for a lot of routine code. Furthermore, in practice, as I understand it, in many application domains model checking is still computationally infeasible despite the work done on tackling state explosion.

Re:Just moves the errors up one level (0)

Anonymous Coward | more than 6 years ago | (#22304958)

You should read things like "Specifying Systems" by Lamport, or "SPIN Model Checker" by Holzmann. And take a maths course in parallel. Then we can talk.

Re:Just moves the errors up one level (2, Informative)

Coryoth (254751) | more than 6 years ago | (#22305400)

The program became little more than a different expression of the formal specifications, such that it would be possible not only to check that a program had no "errors" and followed the specification exactly, but it would also be possible to have an automated process translate the formal specification into a program directly.
That depends on the problem. I can specify a square root finding algorithm: the output multiplied by itself must be equal to the input (within some epsilon error tolerance). I doubt you can extract any useful implementation from that. A slightly more complicated example, I can specify a sorting algorithm: the output must have all the same elements as the input, and for each index i of the ouput the ith element must be less than the (i+1)th element. Trying to translate that (or its more formal equivalent) into a program directly will get you bogosort at best. Specification can be, and usually are, considerably shorter than implementations; this is particularly true wen you start specifying code that is more than just a set of business rules.

Nice job, but... (1)

algae (2196) | more than 6 years ago | (#22299760)

...can they determine whether my program will halt or not?

Re:Nice job, but... (1)

Surt (22457) | more than 6 years ago | (#22300584)

Not them, but MS has software that will do this for all software not designed to defeat it, which since I presume yours was not, probably will work for your program.

Re:Nice job, but... (1)

El Cabri (13930) | more than 6 years ago | (#22300812)

You can prove that a program halts, or doesn't, provided that you understand the program, and in particular the invariants that will determine it to halt. You just cannot write a program that will answer the question on an arbitrary other program. Typically you will design the proof as you design the program. That is the point made in Disjkstra's "A Discipline of Programming" essay (published in the 70s). This kind of things has been forgotten since then and hackers have since built the software ecosystems as a piling of shoddy abstractions, each more complicated to deal with the errors and indeterminism of the previous one.

Re:Nice job, but... (1)

algae (2196) | more than 6 years ago | (#22310938)

You just cannot write a program that will answer the question on an arbitrary other program.

That was kind of my point, but I guess jokes about the halting problem and undecidability are a little over this crowd.

Re:Nice job, but... (1)

TheLink (130905) | more than 6 years ago | (#22304054)

In theory who knows. In practice it will - someone or something will stop it eventually.

More importantly can they determine whether your program is malicious or not?

That's similar to the halting problem, but more relevant to desktop computer users nowadays, given the lack of good program sandboxing that's done in a user friendly manner.

Let's call it the "pwning problem". It's amazing even up till to day that users are still expected to solve that problem regularly, somehow, and here's the good bit: usually with no access to the source code.

Billions of USD spent and all you get in terms of security is _primitive_ UAC crap from Microsoft.

Guarding the guard (2, Insightful)

Mr2cents (323101) | more than 6 years ago | (#22299800)

Model checking surely has it's merits, but how are you going to check the model for errors? If I have learned one thing writing software, it is that there is a difference between what people want, and what people say they want. And there is, and never will be, no software that can check if those two are the same. Actually, I'm beginning to think there might be a lot to be gained if computer scientists team up with psychologists to get better specifications out of customers.

PS: Good news, guys: psychology has lots of female students, so we might solve two problems in one blow.

Re:Guarding the guard (1)

aethogamous (935390) | more than 6 years ago | (#22300036)

PS: Good news, guys: psychology has lots of female students, so we might solve two problems in one blow.

not only that, it would provide psychology students with steady stream of abnormal personalities to study ...

Re:Guarding the guard (1)

amh131 (126681) | more than 6 years ago | (#22300718)

I gotta say that in my fairly modest experience I never noticed a lack of "abnormal" personalities in any psychology class. Made me wonder about the value of all those tests that the grad students made the undergrads take given that everything seemed so darn far away from the median ...

Re:Guarding the guard (3, Informative)

El Cabri (13930) | more than 6 years ago | (#22300722)

You're not expected to model the full behavior of your program. Model checking is useful for testing individual properties such as bounds on ressource allocation, non-deadlock of thread synchronization, or security-related invariants.

2008? (1)

drange_net (859642) | more than 6 years ago | (#22299834)

Then why is the article titled 2007 Turing Award Winners Announced?

Re:2008? (1)

Jugalator (259273) | more than 6 years ago | (#22301062)

Slashdot has to be wrong, unless this was a damn short competiton.

Awards for Excellence in Java, .NET, Rich Web (0)

Anonymous Coward | more than 6 years ago | (#22305180)

A set of awards to recognize individual and professional achievements in Java, .NET and Rich Web is being organized alongside a Developer Summit in Bangalore later this year. The awards will honor "product and innovation excellence of the hundreds of software products and tools that aid developer productivity, across 12 different categories. The selection criteria applied by an international stature panel places emphasis on functionality, usability, innovation excellence, bleeding-edge quotient, and feedback from the developer ecosystem." Seems like a transparent process; you can nominate your selection here http://developersummit.com/awards.html#nominate [developersummit.com].

VIS - An open source model checker (2, Informative)

b0101101001010000 (1082031) | more than 6 years ago | (#22300198)

Fabio Somenzi at the University of Colorado contributes to an open source tool to perform model checking called VIS (Verification Interacting with Synthesis) available at: http://vlsi.colorado.edu/~vis/ [colorado.edu]. I recommend anyone interested in this to check it out. It can perform model checking on Verilog modules directly.

A great day (2, Insightful)

El Cabri (13930) | more than 6 years ago | (#22300418)

I hope this will help push the use of formal methods, particularly in software development. There is no way that software development can be carried out in the massively distributed / multi-core era using the test-and-tweak, black magic approach that has so far dominated software creation and that has led to the big mess that we are in.

Re:A great day (1)

PPH (736903) | more than 6 years ago | (#22302818)

True. But as these mehods, and more to the point, the tools, become more intelligent, eventually they will pass the Turing Test. In other words, the output will be indistinguishable from that of a human, with all the logic errors, missing parentheses, and unreachable code that we currently expect.

Re:A great day (1)

Coryoth (254751) | more than 6 years ago | (#22305458)

I hope this will help push the use of formal methods, particularly in software development.
Sadly, I doubt it. Just read the comments here, or on any other similar article on Slashdot. There are a great many would be programmers who proudly reject any sense of formality. In discussions on Slashdot I've had a a hard enough time pitching lightweight formal methods with JML or similar. I don't quite fully understand where the resistance comes from, but it is very firmly ingrained.

Congrats to Ed. (1, Interesting)

Anonymous Coward | more than 6 years ago | (#22300844)

I was a PhD student of Ed, so great news for being at a "Turing award distance" 1. The model checking technique has indeed come a long way since its inception in 1981. It is more successful in hardware verification, then in software verification, so much so that most chip makers use it in one form or another. To those who say that the specification becomes as complex as the original program itself, there is some truth to that. However, one can also start with simple specifications, like After a request is made to a bus arbiter, it is always granted (within a few cycles, or eventually), or that there is no deadlock, etc. These are simple specifications, that can be "model checked". Moreover, people have developed sugar coating around mathematical languages used for writing the specs, and for analyzing specs themselves, etc. etc. There are techniques such as "equivalence checking", which can be thought of as a special case of model checking, where two designs need to proven equivalent to each other (say one version of RTL v/s a low power version of the same RTL). In this case, the specs become really simple (like which inputs and outputs corresponds between the two designs, and the relative timings).

PS: Too lazy to create a slashdot account, so posting as an AC, besides, what's there in a name. :)

I dropped Emerson's class (3, Interesting)

omnirealm (244599) | more than 6 years ago | (#22301156)

I signed up for Emerson's graduate course on model checking and reactive systems a couple of years back. The first day of class, he walked in 15 minutes late and said something like, "Welcome to my class. No homework or tests. Everyone gets an 'A'. Let's see what kind of papers we can come up with." He then dived right into some intense theory as if he were casually picking up a conversation he left off the semester before. I spent the next few hours feeling like total deadweight (several other grad students just sat there silent the whole time, with expressions on their faces like deer caught in headlights). I wound up just dropping the class; it took me another year of grad courses to get all the background theory I needed to just keep pace, and I hate wasting time, even for an easy 'A'. Too bad I graduated just before he taught his class again; I would have given it another shot before leaving UT Austin.

Re:I dropped Emerson's class (0)

Anonymous Coward | more than 6 years ago | (#22315756)

I am currently in this undergrad course of debugging and verification. He still the same guy, shows up 15 mins late to class everyday without fail. And it's still pretty intense. Apparently the award is for his doctoral thesis he wrote in the early 80s.

An open source model checker for Java (4, Informative)

martinde (137088) | more than 6 years ago | (#22301246)

NASA released an open source model checker for Java called JPF [sourceforge.net]. It's a JVM implemented in Java that can do model checking on "generic" Java apps, finding deadlocks and things like that.

Just about time (2, Informative)

leoval (827218) | more than 6 years ago | (#22302410)

I have been hearing about formal verification for hardware design for the last 10 years and at some point I had to opportunity to do minor work on one of the formal verification products that my company produces. The technology is really interesting and contrary the the uninformed opinion of other slashdotters in this thread, it delivers tangible results and provides a clear advantage over classic verification techniques (vector testing, testbenches and so for).

It took a long time but a lot of the major design houses (Intel, PMC sierra, Freescale, ST micro, IBM and such), now use a form or another of formal verification during their design cycle. It has been a silent revolution, but be assured that many modern microchips have been verified this way.

Perhaps some day we could have a succesful formal verification product for software (After all, Verilog and VHDL could be seen as programming languages no?). In the meantime, it has proven its worth on the hardware side. Congratulations are due to these pioneers.

Check for New Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...