Is there a connection between the Undecidability Theorem and "software complexity"?

Question

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 "unless a computer program is utterly trivial, the fastest way to find out what it will do is to run it and see".

Can such a connection be made formally, or was it more of an empirical observation?

Answer 1

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 "normal" complexity theory, and indeed a very nice analog can be found from the arithmetical hierarchy to the polynomial hierarchy.