{"id":806,"date":"2009-09-21T12:55:37","date_gmt":"2009-09-21T12:55:37","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2009\/09\/21\/information-vs-meaning\/"},"modified":"2009-09-21T12:55:37","modified_gmt":"2009-09-21T12:55:37","slug":"information-vs-meaning","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2009\/09\/21\/information-vs-meaning\/","title":{"rendered":"Information vs. Meaning"},"content":{"rendered":"

If you regularly follow comments on this blog, you’ll know that I’ve been
\nhaving a back-and-forth with a guy who doesn’t know much about information
\ntheory, and who’s been using his ignorance to try to assemble arguments against the
\nKolmogorov-Chaitin information-theoretic measure of information in a string.
\nIn the course of doing that, I came up with what I think are some interesting ways
\nof explaining bits of it, so I thought I’d promote it to the top-level to share
\nwith more readers.<\/p>\n

To be absolutely clear up front: I’m far<\/em> from an expert on K-C theory. It’s something that I find incredibly fascinating, and I’ve read a lot of Chaitin’s work. I’ve been fortunate enough to meet Greg Chaitin a bunch of times when we both worked at
\nIBM, and I’ve attended a bunch of his lectures. But this isn’t my main area of expertise,
\nnot by a long-shot.<\/p>\n

If you don’t know any K-C information theory, then you can look at my
\nintroduction here<\/a>. The rest is beneath the fold.<\/p>\n

<\/p>\n

Information vs. Meaning<\/h2>\n

Kolmogorov-Chaitin information theory is focused on
\nquantification<\/em> – that is, on being able to measure the quantity of
\ninformation in a string of characters. It doesn’t care what the string
\nmeans<\/em>. Information theory cares about how much<\/em> information
\nis in a string; it doesn’t care what the string means. In fact, you can say
\nsomething much stronger about information theory: if you consider meaning
\nat all<\/em>, then you’re not<\/em> doing information theory. A truly
\nabstract string could mean many different things: information theory’s
\nmeasurement of its information content must<\/em> include everything that
\ncould be used relative to any possible system of meaning<\/em> to determine
\nthe information content of a string.<\/p>\n

I’ll borrow a tiny bit of formality from denotational semantics. In
\ndenotational semantics, we take a domain of objects and functions that range
\nover those objects, and we map statements<\/em> – sentences that have some
\nsyntactic structure – onto the objects and functions in the domain.
\nTo assign meaning, what you’re basically doing is creating a system where
\nyou can map<\/em> from syntax – that is, from strings of symbols – to
\nobjects and functions. The string of characters “Mark Chu-Carroll” has
\nabsolutely no<\/em> intrinsic meaning. But by interpreting in a domain
\nof meaning, we can say that the domain maps<\/em> that string of symbols
\nin a way that makes it a representation of a reference to me. But there’s
\nnothing about that string that makes it necessarily<\/em> be a reference
\nto me. It could mean many different things, depending on domain of meaning
\nwhich we use to interpret it.<\/p>\n

To be a bit more specific, consider the string
\n“0000000000000000000000000000000000000000”. That’s a string of 40 “0”s. If you
\ninterpret that as a number – that is, you understand the string of digits as
\nhaving a meaning<\/em> as a number, it’s the number 0. But a string of 40
\nzeros is not<\/em> equivalent to the number 0 in terms of information
\ntheory. That string could also mean the number 40 understood as a unary
\nnumber. Or it could mean a sequence of 5 bytes containing nothing but zeros in
\na computer memory. Or it could mean sequence of 41 bytes, the first forty
\ncontaining the ASCII code for the character “0”, and one containing a
\nterminator-mark. The string contains enough information to allow you to
\ninterpret<\/em> it as any of those things. But if you choose any of those
\nas the<\/em> meaning of it, and work out a representation of that meaning,
\nyou’ll wind up with a different<\/em> answer to the quantity of information
\ncontained in that string than you would for the string considered as an
\nabstract. Choosing a framework in which to assign it meaning can make a string
\nappear to have either more or less information than the
\nstring-as-abstract.<\/p>\n

You can make it appear to have more information by choosing a system of
\nmeaning in which the system itself contains extra information that it assigns
\nto the string; for example, when I say “the complete table of printable
\nunicode code-points in order”, if I interpret that string in the right
\nframework of meaning, it means<\/em> a sequence of over 1100 characters.
\nBut those 1100 characters aren’t containing in the string; they’re part of the
\nframework of meaning that’s used to interpret the string. <\/p>\n

You can also choose a framework in which to assign meaning which makes a
\nstring appear to have less<\/em> information content than the
\nstring-as-abstract. For example, the string of 0s above. If we interpret a
\nstring of 40 “0”s as meaning<\/em> zero, then in terms of meaning, that
\nstring has one character<\/em> of information.<\/p>\n

What’s information?<\/h2>\n

Intuitively, it’s hard for us to separation information from meaning. Informally,
\nwe consider them to be the same thing. But in information theory, they’re very
\ndifferent. As I said above, meaning is what happens when you interpret<\/em>
\na piece of information in some context. But absent any context, how can
\nyou quantify its information content?\n<\/p>\n

To be strict, you can’t. Without any context of any kind, you’ve got no
\nway to quantify anything. But you can create a sort of minimal context, which
\ngives you a really simple way to quantify the amount of information in the
\nstring.<\/p>\n

The basic, fundamental idea is description<\/em>. The amount of
\ninformation contained in a string is the length of the shortest<\/em>
\ndescription that uniquely identifies that string.<\/p>\n

And that’s the essence of information theory: description<\/em>. The
\namount of information in something is the shortest description<\/em> that
\ncan uniquely reproduce that thing. It doesn’t matter what the thing means. You
\ndon’t need to understand it. You don’t need to interpret it. All you need is a
\ndescription that allows you to reproduce it. To produce the string
\n10101101, you don’t need to know that it means the number ten million, one hundred and
\none thousand, one hundred and one interpreted as a number written
\nin decimal notation. You don’t need to know that it means the number
\n173, interpreted as a binary number. All you need to know is that
\nit’s a sequence of symbols.<\/p>\n

That definition might seem like a trick – it just replaces “quantity of
\ninformation” with “length of the shortest description”. How can we
\ndescribe<\/em> something in a way that doesn’t involve meaning? <\/p>\n

The answer is: by computation<\/em>. We can define a simple,
\nminimal<\/em> universal computing device. A description is a program that
\ngenerates a string. The shortest description of a string is the shortest
\ninput-free program that can generate that string.<\/p>\n

Of course, there’s another copout there. What’s minimal<\/em>? And
\nwon’t the information content of a string be different using different computing
\ndevices?<\/p>\n

Minimality is a tricky topic to tackle formally. You could easily write
\na PhD dissertation (and someone probably already has) on a precise
\ndefinition of a minimal computing device. But informally, the idea that
\nwe’re getting at is very simple: no magic instructions<\/em>. That is,
\neach instruction performs a single action – so you can’t output
\nmore than one symbol with a single instruction.<\/p>\n

For the second question: yes, that’s true – to a limited extent. But
\ngiven any pair of computing machines, the difference between the
\nlength of the shortest programs to generate a specific string will vary
\nby no more than a single fixed constant.<\/p>\n

That last point is easy (and fun) to prove. First, we need to
\nformalize the statement. Take two computing
\nmachines, P and Q. Let the information content of a string S relative
\nto P be written as I(S, P), and relative to Q be I(S,Q).
\nFor all strings S, the absolute value of I(S,P) – I(S,Q) will
\nbe less than or equal to a constant C.<\/p>\n

Here’s the proof:<\/p>\n

    \n
  1. if P and Q are both universal computing devices, then
    \nthere is a program<\/em> for P which allows it to emulate Q;
    \nand there is a program for Q which allows it to emulate P. <\/li>\n
  2. Let the program for P to emulate Q have size Pq<\/sub>,
    \nand let the program for Q to emulate P be Qp<\/sub>.<\/li>\n
  3. Consider a string S. Let the program for P to generate S
    \nbe PS<\/sub>, and the program for Q to generate S be
    \nQS<\/sub>. If PS<\/sub> is shorter than QS<\/sub>,
    \nthen the shortest program for Q to generate S cannot possibly
    \nbe longer than QS<\/sub> + QP<\/sub>. <\/li>\n
  4. Reverse the above statement for P and Q.<\/li>\n
  5. Now, take the longer of PQ<\/sub> and QP<\/sub>. For
    \nany string S, it should be obvious that information content of
    \nS relative to P or Q cannot possibly differ by more that
    \nmax(len(PQ<\/sub>), len(QP<\/sub>)).<\/li>\n<\/ol>\n

    No magic there. It’s very straightforward.<\/p>\n","protected":false},"excerpt":{"rendered":"

    If you regularly follow comments on this blog, you’ll know that I’ve been having a back-and-forth with a guy who doesn’t know much about information theory, and who’s been using his ignorance to try to assemble arguments against the Kolmogorov-Chaitin information-theoretic measure of information in a string. In the course of doing that, I came […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[30],"tags":[],"class_list":["post-806","post","type-post","status-publish","format-standard","hentry","category-information-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-d0","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/806","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=806"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/806\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=806"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=806"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=806"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}