The following undecidable problem is natural for engineers in the sense that runtime estimation is an ubiquitous engineering problem associated to (for example) control theory and circuit design.
>**Viola's theorem** Given an integer $k$ and Turing machine $M$ promised to be in P, the question "Is the runtime of $M$ of ${O}(n^k)$ with respect to input length $n$ ?" is undecidable.
The proof of this problem's undecidability was given on TCS StackExchange by Emanuele Viola in answer to the question <a href="http://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no"><i>Are runtime bounds in P decidable?</i></a>
**Background**
This question arose in parsing Luca Tevisan's answer on TCS StackExchange to the question <a href="http://cstheory.stackexchange.com/questions/4704/do-runtimes-for-p-require-exp-resources-to-upper-bound-are-concrete-examples-k/4716#4716"><i>Do runtimes for P require EXP resources to upper-bound? … are concrete examples known?</i></a> (answer: yes and yes).
The illumination sought in asking/answering this question was a better appreciation/intuition regarding the practical aspects of runtime estimation in the complexity class P, in the sense of runtime estimates that are feasible (that is, require computational resources in P), versus infeasible (that is, require computational resources in EXP), versus formally undecidable (the instance above).
What this problem's undecidability shows us, perhaps, is that some aspects of P are richer and more subtle than is readily appreciated upon first acquaintance.