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.


0 Responses to “Introduction to Kolmogorov complexity”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: