Solving the Unsolvable

ziggy on 2006-02-14T16:01:29

If you had a multi-billion dollar software company, where would you spend your research money?

Why, solving the termination problem, of course! (Actually, if you read the fine print, the project isn't attempting to actually solve the termination problem, just solve it most of the time.)

Oh, and they're hiring. Brainiacs only, please. ;-)


Usually decidable is good enough

n1vux on 2006-02-14T17:16:18

Very interesting, thank you for the pointer.

As long as they have a heuristic to determine when decidability itself is undecideable (e.g., we've spent 20ms on this one, I guess it's toast), things which are not doable in general can be doable in practicallity. If your code is so obscure that the Terminator gives up on it, that could be a good reason to fail a code review -- unless it's a requirement. Of course, a proof of termination ... when practical ... does not prove correct operation, just proves that one pernicious but obvious-when-it-happens bug does not exist.

F# is ML.net not Fortran.Net? There's a naming problem here! Interesting that they're using two variants of ML plus Prolog, and plain ol' C++. I miss Prolog, I'm looking forward to Perl6 Rules for that reason.