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”