Archive for the 'Uncategorized' Category

08
Jun
08

Introduction to Kolmogorov complexity

A chance encounter with a friend, Michael Greenberg, with whom I had fallen out of touch, reminded me today of what I ought to be doing with this blog.

Recall from earlier these two definitions:

(DFN-SYSTEM) A system is a set of beliefs and valuations.

(DFN-RATIONAL-SYSTEM-v.1.0) A system is a rational system to the extent that its contents are deducible from its axioms.

The latter definition is vague at best.  What does it mean for a system to be deducible to some extent?

Thankfully, there is a definition from information theory that can be brought to bear on this problem: Kolmogorov complexity.

The Kolmogorov complexity of a string is defined as the length of the shortest description in a particular description language.  Each of the italicized terms ought to be fleshed out.  Here, a “description language” is a function from strings to strings.  A “description” d of a string s in a language L is another string such that L(d) = s.  These description languages are often defined in terms of computational machines, like Turing Machines or common programming languages like Lisp.  The description language is also declared to be universal in the sense that for any string, there exists at least one a description of it in the language.

If a string has low Kolmogorov complexity for a particular language, that means that it is possible to describe it in a way that is shorter than the string itself.

The application to the philosophical idea of systems that I propose is this: if a description language is seen to encode the rules of deduction used to evaluate a particular system, and the system itself can be represented as a string, then a rational system in the sense above should have a low Kolmogorov complexity because much of its content can be deduced programmatically from its axioms.

There is a lot to flesh out here, and the assumptions are dubious.