An undecidable problem in the Turing computational model is this: it is a problem for which no algorithm exists which can ] decide <i>every input case</i>.<p>This doesn't preclude <i>some</i> input cases from being decided.<p>What happens it that every attempt at making an algorithm for an undecidable problem will run into two issues: there will be input cases for which an answer exists, but for which the algorithm either gets into an infinite loop/recursion or else produces the wrong answer.<p>Why would a decision procedure ever yield the wrong answer? That is due to mitigations of the infinite looping problem. To avoid becoming trapped by the input cases that trigger infinite calculations, the algorithm has to resort to some mechanism of arbitrarily stopping, without having reached the decision. Like for instance by capping the number of steps executed. But when that situation is reached, the correct answer is not yet known. The algorithm can return "yes" or "no", but that will be wrong half the time. Or it can report "failed", which is always incorrect, not matching either "yes" or "no".<p>A classic example of an undecidable problem is the Halting Problem: the question of whether a given program (or algorithm) P, operating on an input I, will halt or not. So the space of inputs for this problem is <P, I> pairs.<p>The input space is infinite, but all instances in that space are finite: finite length programs P operating on finite inputs I.<p>The problem is that just we have a given finite P and finite I doesn't mean that halting can be decided in finite steps.<p>No matter how cleverly someone constructs a halting decider, it is easy to produce test cases which will cause that decider to either stop and produce the answer (decide incorrectly) or else iterate or recurse forever. (Demonstrating how such test cases can be produced for any decider is at the heart of a popular proof which shows that halting is undecidable.)<p>The Halting Problem is at the center of decidability, because every decision procedure of any kind (not necessarily a decision in the Halting Problem) is a <P, I> pair. For instance the decision whether a list of N integers is sorted in ascending order is a <P, I> pair. P is an algorithm for sweeping through the integers to check that they are ordered, and I is some list of integers. Since it is a <P, I> pair, it is in the domain of the Halting Problem. P is not in the Halting Problem: P is in the domain of processing a list of integers. But <P, I> is an input case of the Halting Problem: does list-processing algorithm P halt on the list of integers I.<p>The upshot is that when we are solving some decision problem by running an algorithm, which is taking long, and we ask "will this decision terminate, or is it in a loop?" we are then posing another problem, and that problem is an input case of the Halting Problem.<p>And we know that the Halting Problem is undecidable.<p>What that means is that if we happen to be calculating a problem which is undecidable, the Halting Problem informs us that there is no guaranteed shortcut for us to know whether our calculation is hung, or whether it is working toward halting.<p>When we try to apply "meta reasoning" about an algorithm that appears stuck, our reasoning itself may also get stuck. We may have to give up, cut the investigation short, and report "we don't know". I.e. we don't know whether or not our decision program is forever stuck or working toward the solution.<p>Undecidability is a somewhat important topic to a software engineer for the following reasons. In your career you may from time to time encounter requirements that call for a the calculation of an undecidable problem. If you know can recognize it, you can take action to revise the requirements. For instance, perhaps you can negotiate the requirements such that it's acceptable for the decision to be incorrect, erring on one side of the other (false positive or false negative). Equivalently, maybe some inputs can be rejected before the algorithm, leaving a decidable subset. You may have a People Problem there because the requirements are coming from non-computer-scientists who don't know about decidability; you have to be careful not to make it look like you are refusing to do hard work due to not believing in your skill, or laziness.<p>As an example, we could use the Halting Problem itself. Say you work on some virtual machine for sandboxing untrusted programs and your boss says, can we detect programs which loop infinitely, and not run them at all? Just reject them?
If you know about undecidability, you can tell your boss, no, that is an undecidable problem! What we can do is limit the number of instructions or run time, which will stop some programs that are not looping infinitely but are just taking long to calculate something. Or here is another thing we can do instead; only admit programs written in a language that is not Turing Complete: has only bounded loops and no recursion. The sandbox compiler can reject all others. Or we can allow recursion but stacked recursion only (not tail) and limit the depth. Of course, that's just an easy example; undecidability can sneak into the requirements in forms that are not immediately recognizable.