Also, in AIT we completely ignore the time taken by a computation, concentrating only on the size of the program. And the computation run-times may be monstrously large, quite impracticably so, in fact, totally astronomical in size. But trying to take time into account destroys AIT, an elegant, simple theory of complexity, and one which imparts much intuitive understanding. So I think that it is a mistake to try to take time into account when thinking about this kind of complexity.

I fully agree with him that comprehension and compression are very tightly interlinked. I have said similar things before (eg at Re (tilly) 3: Maintainable code is the best code -- principal components). But if it ruins the elegance of his theory to take obvious factors like time into account, well reality is messy. Because obviously in the real world time does matter.

To take a well-known example, consider chess. There is an absolute theory of chess, it is fairly simple. You have a list of pieces, you know how they move, you have a board, you know its initial set-up. It is not that hard to write a program to do a brute-force search and discover the perfect way to play. Such programs have been written.

The actual theory of chess is much more complex though. There is far less certainty (this is the perfect move). There are lots of semi-vague concepts like "material advantage", "pawn position" and "light square weakness".

Why? Because time matters. People can only think through a certain amount. We therefore substitute our ability to work with complex concepts for time we don't have. Computers operate faster and simpler. Good chess computers are somewhere between human practice and the theoretical simplicity. Like humans they have to stop analysis somewhere in real life and therefore rely on heuristics. However they can analyze farther and find heuristics harder, so they do better with a simpler theory and more brute force.

As Chaitin notes, including time ruins the simplicity of AIT. It introduces all sorts of hard to quantify issues that vary depending on the observer. But I am about to make it worse. I don't believe that programs have any intrinsic attribute that you can really call "simplicity". More precisely, I still agree with my description in the above node:

And so it is with programming. Well-written source-code is a textual representation of a model that is good for thinking about the problem. It will therefore be fairly efficient in its representation (although the text will be inefficient in ways that reduce the amount of information a human needs to understand the code). Being efficient, functions will convey a similar amount of surprise, and the total surprise per block is likely to be fairly large.

In short, there will be a good compression in the following sense. A fixed human effort spend by a good programmer in trying to master the code, should be result in a relatively large portion of the system being understood. This is far from a compact textual representation. For instance the human eye finds overall shapes easy to follow, therefore it is good to have huge amounts of text be spent in allowing instant pattern recognition of the overall code structure. (What portion of your source-code is taken up with spaces whose purpose is to keep a consistent indentation/brace style?)

Which is about as far away from AIT as you can get. :-)

A related reading: "Succintness is Power" by Paul Graham. He measures the lenght of program in parse tree elements not in bytes. Not much new information. But here is a nice quote:

I think most hackers know what it means for a language to feel restrictive. What's happening when you feel that? I think it's the same feeling you get when the street you want to take is blocked off, and you have to take a long detour to get where you wanted to go. There is something you want to say, and the language won't let you.

I see you have researched this subject thoroughly.

Researched, not really. Thought about, yes.