Is there a connection between the Undecidability Theorem and "software complexity"?
The author is here referring to the Halting problem, and possibly also Rice's theorem (without putting words into their mouths).
It says indeed that it's not possible to decide in advance whether a Turing machine will halt on any given input or not, thus it makes it impossible to decide in advance what the actual output of the machine will be.
This is the fundamental theorem of the field known as recursion theory, more known in these days as computability theory.
The computability theory comprises infinitely many complexity classes, which we are familiar with from complexity theory, but computability theory typically concerns itself with the complexity classes on the decidable/undecidable level: primitive recursive, through the computable class, to the recursively enumerable, and going infinitely beyond to the highly undecidable problems as can be studied via the arithmetical hierarchy.
There are many connections to our &quot;normal&quot; complexity theory, and indeed a very nice analog can be found from the arithmetical hierarchy to the polynomial hierarchy.