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.


A change of strategy

I am finding that I am reading much faster than I am able to find the time to write here. This makes my original plan for this blog–to begin with a thorough, linear exegesis of various philosophical notes–very unpractical. Updates have been too slow to be any sign of progress.

So I think I will table that method for now.

A more realistic and interesting (for me) way to use this space is to actively work on some ideas that past readings have already inspired. I will attempt to apply the same amount of rigor to these problems, but my coverage of any particular work will be more sporadic, and I expect that for some time topics will appear disjointed. I may resort to using this space for notes; if I do so, I will make an effort to elaborate on them later, or incorporate them into some larger statement.

I think that this sort of work will likely hold my interest better, and maybe ultimately be of more use.



I wrote too soon about Habermas and his use of Popper’s “third world”:

In what follows I shall no longer employ the Popperian terminology. My purpose in reviewing Jarvie’s action-theoretic translation of Popper’s three-world theory was only to prepare the way for the thesis that with the choice of a specific sociological concept of action we generally make specific “ontological” assumptions. (TOCA, 84-85)

So it is not clear at this point in the text what Habermas’s actual metaphysical commitments are. Later in this chapter, he provides a taxonomy of actions and is explicit about the ontological assumptions of each, and I would assume that Habermas is committed, at the very least, to the ontological assumptions of communicative action theories.

My guess is that the answer to the question of what it means for an expression to embody knowledge (DFN-EXP-EMBODY-KNOWLEDGE-?) lies within this more elaborate taxonomy.


Popper’s third world

In my last post, I raised the following question in the context of TOCA:

(DFN-EXP-EMBODY-KNOWLEDGE-?) What does it mean for an expression to embody knowledge?

I didn’t find a lot to help me in the opening chapter I’ve been writing about here for some time. But thankfully, I’ve been reading faster than I’ve been blogging, and recently hit a section that should help me out.

It turns out, to my surprise, that this notion of embodiment is largely Popperian. In the third section of TOCA, Habermas introduces the Popperian notion of a “third world” of objective semantic contents.

We may first distinguish the following three worlds or universes: first the world of physical objects or physical states; secondly, the world of states of consciousness, or of mental states, or perhaps of behavioral dispositions to act; and thirdly, the world of objective contents of thought, especially the scientific and poetic thoughts and of works of art. (Popper, “Epistemology Without a Knowing Subject,” in TOCA, 76)

According to Habermas, Popper sees these three worlds as ontologically distinct. Apparently, the objective existence of the third world is intended to provide a way for objective science to proceed without dependency on a subject–which would, I suppose in Popper’s opinion, pollute the project. To this end, it is necessary for there to be both “embodied” and “unembodied” semantic contents:

Popper distinguishes between explicit semantic contents that are already embodied in phonemes and written signs … and those implicit semantic contents that are not yet “discovered,” not yet objectivated in carrier objects of the first world, but are simply inherent in already embodied meanings.
These “unembodied world 3 objects” are an important indicator of the independence of the world of the objective mind. Symbolic formations are, it is true, generated by the productive human mind; but though they are themselves products, they confront the subjective mind with the objectivity of a problematic, uncomprehended complex of meaning that can be opened up only through intellectual labor.

Habermas goes on to correct Popper’s story and especially its application to sociology. But I suspect that he finds the metaphysical commitments here OK. Unfortunately, those commitments spook the hell out of me. To put my cards on the table: I’m currently a physicalist as far as the mind/body debate goes, for reasons that I think are best elucidated in Papineau’s Thinking about Consciousness, so I already disagree with the the distinction between Popper’s first and second worlds. And the third world? Well, I think it can be reduced back down to causal relations as well.

None of this is to say that I think Habermas’ project is fundamentally misguided. But I do think it would be easier to work with it if I could work out some adjustment to a more plausible metaphysical story.


Knowledge embodied in expressions?

Habermas’ theory of rationality is broad in scope and he appears to develop it throughout TOCA, but be begins with a preliminary account grounded in some conceptual analysis.

What does it mean to say that persons behave “rationally” in a certain situation or that their expressions count as “rational”? Knowledge can be criticized as unreliable. The close relation between knowledge and rationality suggests that the rationality of an expression depends on the reliability of the knowledge embodied in it. (TOCA, 8 )

This is Habermas’ first stab: to tie the definition of rationality to the idea of knowledge “embodied” in an expression.

Consider two paradigmatic cases: an assertion with which A in a communicative attitude expresses a belief and a goal-directed intervention in the world with which B pursues a specific end. Both embody fallible knowledge; both are attempts that can go wrong. (TOCA, 8, emphasis mine)

I am initially skeptical of the free use of “embody”–it appears to be doing a lot of work for Habermas, and he refrains from defining it explicitly, and instead builds it by example only. My fear is that such an explanatory tool built out of ad hoc examples without an overarching principle will be this theory’s weakest link. But despite my reservations, let’s open up the term to the possibility of definition within our system.

(DFN-EXP-EMBODY-KNOWLEDGE-?) What does it mean for an expression to embody knowledge?

Moving on:

In both cases, the critic refers to the claims that the subjects necessarily attach to their expressions insofar as the latter are intended as assertions or goal-directed actions. This necessity is of a conceptual nature. For A does not make an assertion unless he makes a truth claim for the asserted proposition p and therewith indicates his conviction that his statement can, if necessary, be defended. And B does not perform a goal-directed action, that is, he does not want to accomplish an end by it unless he regards the action planned as promising and therewith indicates his conviction that, in the given circumstances, his choice of means can if necessary be explained.” (TOCA, 9)

There are a number of presuppositions in the passage that I would rather not take for granted, but there is one in particular which we have already explored reasons for doubting. It appears, at least on a first reading, that Habermas believes that all goal-directed actions are tied to linguistic claims and explanations. But we have already discussed here and here that the connection between know-how and language is a weak one. It might be possible, then, for there to be goal-directed action that is not tied to language at all.


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.


Know-how and language

Let’s look in more depth at the relationship between knowledge and language.  Although we have accepted (maybe only tentatively) that beliefs can be expressed as linguistic statements (see (TOCA-8-A)), we have found this compelling largely because the following appear to hold

(T&W-1) When one has a belief, one is related in a certain way (the relation of believing) to a proposition.
(T&W-3) Propositions have structure that parallels the logical structure of the sentences.

Presumably, what we mean when we say that beliefs can be expressed as linguistic statements is that for a belief B, and a proposition related to that belief PB, B can be expressed by the linguistic statement SB only when SB reflects the logical structure of PB (and when the words of SB reflect the proper concepts which constitute PB).

This all makes sense when we are talking about knowledge-that.  But we have already pointed out that know-how does not seem to have the same connection with language as knowledge-that.  In particular, there don’t appear to be sentences that correspond with our “belief-hows.”

Why might this be? If the above reasoning about knowledge-that is correct, then I think the best explanation would be this: knowledge-how is not related to propositions in the same way as knowledge-that.