Is there a connection between the Undecidability Theorem and "software complexity"? I was reading Complexity: The Emerging Science at the Edge of Order and
Chaos and a certain passage got me really intrigued.  When discussing
Chris Langton's explorations of artificial life algorithms, the author
paraphrases Langton stating the following about a certain set of
evolutionary algorithms:

This is the undecidability theorem, one of the deepest results of
computer science: unless a computer program is utterly trivial, the
fastest way to find out what it will do is to run it and see.  There
is no general purpose procedure that can scan the code and the input
and give you the answer any faster than that.  That’s why the old saw
about computers only doing what their programmers tell them to do is
both perfectly true and virtually irrelevant; any piece of code that’s
complex enough to be interesting will always surprise its programmers.
That’s why any decent software package has to be endlessly tested and
debugged before it is released and that’s why the users always
discover very quickly that the debugging was never quite perfect.

But I can't easily see how the undecidability theorem allows one to
conclude that &quot;unless a computer program is utterly trivial, the fastest
way to find out what it will do is to run it and see&quot;.
Can such a connection be made formally, or was it more of an empirical
observation?
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.