Limits of Computation

Rice's theorem states that every non-trivial semantic property of programs is undecidable. Not difficult, not expensive: undecidable. No procedure takes the text of a program and returns what that program means.

This is usually filed as a curiosity, a result about pathological programs that real engineering never meets. Read literally it is a constraint on method: inspection is not a way of finding out, and no amount of care in the reading repairs that.

The result is about all programs and all properties, which is also its weakness. Bound the time, the memory and the input and some of what was undecidable becomes merely expensive. Where that boundary sits for a given system is a real question with a real answer.

So the work is in locating it. Which properties of the systems being built now fall on the decidable side once the bounds are stated, what the decision costs, and what has to be run because nothing else will settle it.