Worth having a look at
http://scribblethink.org/Work/Softestim/kcsest.pdf, which attempts to
demonstrate:
"Algorithmic (KCS) complexity results can be interpreted as
indicating some limits to software estimation. While these limits
are abstract they nevertheless contradict enthusiastic claims
occasionally made by commercial software estimation advocates.
Specifically, if it is accepted that algorithmic complexity is an
appropriate definition of the complexity of a programming project,
then claims of purely objective estimation of project complexity,
development time, and programmer productivity are necessarily
incorrect."
Which effectively means it's impossible to predict cost / timelines for
sufficiently complex problems, without actually doing the problem. A
bit of a 'duuh' maybe for those here, but it's still nice to have this
backed up by a fancy paper with a cool mathematical proof.
Ah yes, the halting problem arises in another guise. Strictly speaking,
since many complex programs cannot be proven to ever complete, how then
could one arrive at an accurate estimate for developing a successful
complex program (at least if it's one of those)?