How many bits is that tree?

Brian Cantwell Smith, rumored inventor of recursion, tells me a colleague at Xerox PARC once wondered, "How many bits is that tree?" The question is striking for being posed at all--it requires an unusual metaphysical commitment, to say the least--but moreover because it was posed seriously, as though it was a meaningful question.

There is a notion being bandied about in virtually every discipline which, in its own way, makes similarly overreaching claims on ontology. That notion is information. It is not clear just what information is. Perhaps St. Augustine would have said, “What is [information]? If no one asks me, I know; but if I wanted to explain it to one who asks me, I plainly do not know.”

But how many bits is that tree? Those of us with a computational bent are likely to think that there might be a minimal description of any given element of the universe (such as a tree), and this minimal description can be measured in bits. Wolfram certainly thinks so, and Greg Chaitin's algorithmic independence seems just suited for drawing lines around objects like trees. Nevertheless, the tree is more than its description. How many bits are in that tree seems a different question than how many bits is that tree.