Kolmogorov meaning

Is the meaning of life non-computable? Noson F Yanofsky has a nice rumination about Kolmogorov complexity and meaning in Nautilus. Kolmogorov complexity, he tells us, is a measure based on the length of the shortest computer program that can generate a given string of digits. The shorter the program, the lower the complexity. This way of looking at it means that structure, which informally we might see as a sign of complexity, actually tends to reduce it, the most complex numbers being completely random strings.

The number giving the Kolmogorov complexity should be determined by the length of the shortest program which can generate the number. Interestingly, though, determining the shortest program is a non-computable problem, something that can apparently be proved by reductio, though Yanofsky does not trouble his readers with the actual proof.

Yanofsky notes that our efforts to give meaning to events generally takes the form of looking for patterns, something you could see as loosely analogous to identifying the programs that generate the Kolmogorov values. Perhaps this too, is an intractable problem, he suggests, so that we can never be sure there isn’t a deeper meaning we have missed; our search will never be over.

This is a matter of general philosophical pondering rather than a tight logical argument, but I found it a congenial point of view that slots easily in alongside the family of non-computable issues to do with the frame problem, radical translation, and so on which lie around the fringes of consciousness and suggest that it too involves dealing with problems that are computationally intractable.

In fact, while Yanofsky speaks of meaning in a very general sense, I think we might apply a similar analogy to meaning in the sense of intentionality or ‘aboutness’. Let’s suppose we are dealing with strings of characters and the task is to identify what those characters mean (let’s keep it simple and suppose ‘what it means’ is just a matter of identifying which physical object is referred to by the string of characters). Now any string of characters has an idefinitely long list of possible interpretations. We could read them in English, in French, or in any arbitrary encoding we care to devise, so that, in short, we can make them be about anything. But Grice helpfully tells us that we can assume in interpreting human utterances that only the minimum of necessary and relevant information has been provided. So in a way rather similar to the search for a Kolmogorov value, we need to look for the simplest meaning that would have required this string of characters to convey it.

Is that, too, a non-computable problem? Intuitively, I feel it probably is, though I’m not quite sure how we could shape a proof – perhaps something about examining a tricksy self-referential string like ‘the meaning of this string is not determinable’, but I leave that as an exercise for the reader.

Curiously, this reasoning seems to imply that all strings of characters that have a meaning at all have one correct meaning. We just can’t be sure (computationally at least) what it is.

7 thoughts on “Kolmogorov meaning

  1. The proof for the uncomputability of Kolmogorov complexity typically uses Berry’s paradox: take “the smallest number not expressible in less than eleven words”. We can order all English expressions naming numbers according to length, check the numbers they correspond to, and thus, find out which number answers to the above description. But that description only contains ten words—yielding contradiction.

    Similarly, if Kolmogorov complexity were computable, one could construct a program that outputs a number such that it can be proven to have a Kolmogorov complexity of x, but the program itself has less than x bits—but the Kolmogorov complexity is defined as the shortest program producing a certain number: contradiction.

    I think there’s another opening for the uncomputability of Kolmogorov complexity to enter the mind, and that’s in induction: you can base a formal theory of induction upon Kolmogorov complexity (Solomonoff induction), which gives formal meaning to the question of how you get to general principles from isolated observations. Perhaps one can reframe the problem of meaning in a similar way—as an inductive step of reasoning from representation to represented.

  2. Math is a proof of itself, math proves math…
    …is this kind of string, a very simple computational object of meaning…
    …that one plus unknown equals one unknown and describes definite and indefinite searches (1+x=1x)…

    Wouldn’t value be found in embracing the search for…

  3. (‘the meaning of this string is not determinable’)

    One is then compelled to consider: Just because the meaning of the string is not determinable, does this make the meaning of the string correspond to a subjective reality that can be whatever one says it is, or does this make the meaning of the string correspond to an objective reality that just happens to be indeterminate? If it is an objective reality, then I do concur that: “Curiously, this reasoning seems to imply that all strings of characters that have a meaning at all have one correct meaning. We just can’t be sure (computationally at least) what it is.”

  4. It could be said that science is the search for the shortest mechanism that produces observed phenomena, for the universe’s shortest program that produces the system in question. The laws of nature are really just compression algorithms. And the much sought after Theory of Everything would be the ultimate minimum program. But as Yanosfky notes, we could never know whether we’ve found the truly minimal one, or if a yet more basic one awaited discovery.

    I’m not sure I’m on board with equating meaning with this, or at least with equating all possible meanings with it. But admittedly, other meanings would likely all be relative to a particular observer, such as the meaning of this comment to an English speaker versus someone who doesn’t know English.

  5. I don’t really see what measuring complexity has to do with meaning in the intentional sense. Meaning in the explanatory sense however usually implies that the explanation of a phenomenon should be smaller than the actual thing being explained. This is a practical concern, and related to the limited amount of memory and capacity we have in our brains to model things.

    If you want to analyze text with maths, there are loads of better tools available than Kolmogorov complexity. Shannon entropy for example, it works at about the same level, does not care about grammar or word boundaries.

    “Curiously, this reasoning seems to imply that all strings of characters that have a meaning at all have one correct meaning. We just can’t be sure (computationally at least) what it is.”

    The problem here might be that the computer that executes the Kolmogorov algorithm itself is not well defined. There is no single one computer instance that defines the “correct” meaning of all possible strings. In fact, the complexity measure should include the size of the machine executing the algorithm, but this leads to a regress: what framework do we use to describe the machine, to measure the size?

  6. Pingback: Kolmogorov meaning – Health and Fitness Recipes

  7. language never uses the minumal computational complexity to operate. It is a practical combination of the requirements of conciseness and information redundancy, largely determined by patterns of language inherited by speech, not the written word.

    Written chinese has less information redundancy than english for instance, and is more prone to misinterpretation should there be transmission issues. English has surprising strength in the face of numerous missing characters and the intended maning cn stll be gssed at, if you get my meaning.

    But language is word based, not character based, and according to Chomsky has all kinds of universally determinitive grammar rules. Finding the minimum “meaning” in a string of characters probably isn’t one of them.

    J

Leave a Reply

Your email address will not be published. Required fields are marked *