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.


Rationality, for Habermas

If we seek the grammatical subjects that go with the predicate expression “rational,” two candidates come to the fore: persons, who have knowledge, can be more or less rational, as can symbolic expressions–linguistic and nonlinguistic, communication or non-communicative actions–that embody knowledge. We can call men and women, children and adults, ministers and bus conductors “rational,” but not animals or lilac bushes, mountains, streets, or chairs. We can call apologies, delays, surgical interventions, declarations of war, repairs, construction plans or conference decisions “irrational,” but not a storm, and accident, a lottery win, or an illness. (TOCA, 8 )

A few observations on this passage:

First, Habermas appears to be adopted at least preliminarily the methodology of linguistic analysis that we would expect to find in analytic philosophy. I’m personally skeptical about the power of this methodology, but reading ahead I have been impressed with Habermas’ use of it. More on this later, for now I would just like to point it out.

Second, what a headache keeping all these definitions is going to be! We already have one definition of the predicate “rational,” which is Lukacs’ predicate that he uses, a predicate whose “grammatical subject” is limited to systems. Now, at the very least, we have a new predicate that applies only to persons for which we use the same word. Let’s introduce this in a new definition, which we will have to leave undetermined for the moment.

(DFN-RATIONAL-PERSON-?) For given person, it is possible that that person is a rational person. What does that mean?

In addition, Habermas claims that there is another use of “rational” which applies to “symbolic expressions.” I think that my parsing here takes “linguistic and nonlinguistic, communication or non-communicative actions” to be in apposition to “symbolic expression,” hence defining it. And the former phrase pretty clearly logically reduces to “actions.” So “symbolic expressions” is just a fancy way of saying “actions.” Let’s propose the following (blank) definition:

(DFN-RATIONAL-ACTION-?) For given action, it is possible that that person is a rational action. What does that mean?

I think that in the future, I will disambiguate when necessary between these three predicates by subscripting them to note the category of their subjects. So, “rationals“, “rationalp“, and “rationala“, refer to the predicates relating to systems, persons, and actions, respectively.