Wednesday, September 4, 2013

Schroeder complexity


Schroeder claims that bit strings formed from random coin tosses, most probably, will have zero information content zero.  I'm not sure how he can argue that unless he happens to known the receiving machine in question.

But, taken very generally, it is an interesting question to ask, I think: what is the minimum Kolmogorov complexity of a message that would be recognized as a valid proof of Godel's Incompleteness Theorem (in English)?  Once you figure out a number, call that number N.

What would Schroeder assess the average Shannon complexity of the shorter such proofs to be?  (Schroeder thinks exclusively in terms of Shannon complexity.)  Would it be more than N?  Does it make a difference that state change from not understanding the theorem to comprehending the truth of the proof results from a relatively small set of messages, even among the set of all proofs.

Now, what is the probability that of a randomly generated bitstring N bits long can be decrypted (or creatively recrypted) into one of these proofs using a decryption algorithm with Kolmogorov complexity less than N/4?

What, then, is the problem with claiming that specified complexity is a reliable empirical marker of intelligence? The problem isn't that establishing specified complexity assumes the form of an eliminative argument. Nor is the problem that specified complexity fails to identify a causal story. Instead, the problem is that specified complexity is supposed to miscarry by counterexample. In particular, the Darwinian mechanism is supposed to purchase specified complexity apart from a designing intelligence. But does it? [from here]

No comments:

Post a Comment