Codes and Gödel

SHORT POST TIME. Which means I thought of this off-hand (and it’s certainly not new information, but is kind of fun).

Coding theory is concerned with encoding messages in a way so as to minimize their length for transmission over some sort of channel. The mathematical formalization of this goes all the way back to Shannon’s Information Theory, so I’ll give some basics and then mention the RANDOM CONNECTION.

Here’s the idea. We have two parties, Alice and Bob, who are trying to communicate over some sort of digital channel. (For convenience, let’s assume that the channel communicates every message that is sent across without corruption). Alice has a message M that she wants to send, and the message is drawn from some alphabet \Sigma. Concretely, let’s assume the message is drawn from the English alphabet

\displaystyle \Sigma = \{a, b, c, \ldots, x, y, z, \#\},

where we use # as a placeholder for a blank space. Let \Sigma^* denote the set of all messages we can compose out of the symbols in the alphabet \Sigma. For example,

what\#up\#dog \in \Sigma^*.

Now, suppose the channel is binary, so it can only send 0s and 1s. Obviously, Alice needs some way to encode her alphabet \Sigma into the alphabet \{0,1\} to send over pressing messages to Bob.



To bring this about, let’s define a binary code to be a function

\displaystyle C: \Sigma \rightarrow \{0,1\}^*.

That is, a binary code is any map from our source alphabet to a sequence of bits. Note that if we have a binary code C we can easily extend it to messages (i.e. to elements of \Sigma^*) by defining, for any sequence of symbols \alpha_1 \alpha_2 \cdots \alpha_n \in \Sigma^*, the map

\displaystyle C(\alpha_1 \alpha_2 \cdots \alpha_n) = C(\alpha_1) C(\alpha_2) \cdots C(\alpha_n).

Now, most codes are useless. Indeed, under our above definition, the map C(\alpha) = 0 for every English letter \alpha is a code. Unfortunately, if Alice used this code over their channel Bob would have a tough time decoding it.alicebad

So, we need some condition that allows us to actually decode the bloody things! We’ll start with a useful type of code called a prefix-free code.

Definition: A binary code C: \Sigma \rightarrow \{0,1\}^* is prefix-free if, for every pair of symbols \alpha, \beta \in \Sigma neither C(\alpha) is a prefix of C(\beta) nor vice-versa.

An example of a prefix-free binary code (for the first four letters of the English alphabet) could be the following:

\displaystyle C(a) = 0, C(b) = 10, C(c) = 110, C(d) = 111.

Let’s encode a message with C: if Alice encoded the message badcab via C and sent it to Bob, Bob would receive


Now, the beautiful property of prefix-free codes is the following: Bob can actually decode this message online. That is, he can do the following: iterate through each of the bits in sequence, and store what order they came in. Once his stored bit sequence matches a sequence in the code, he can automatically decode that character and keep going!

To illustrate, Bob first reads a 1 off the string. He convinces himself that 1 is not the code for anything, so he reads the next bit, a 0. He now has the string “10″, which is a code for b. Now, is it possible that this could be the beginning of a code for another letter? NO! Because “10″ is the code for b and is not the prefix of any other code. So Bob can translate the b, and move on.

We define nonsingular codes to be the set of codes that can actually be decoded. After seeing the above example, it’s clear that prefix-free codes are non-singular. However, is it possible for there to be non-prefix-free, non-singular codes? That is, are there codes that are decodable, but require us to read the entire message before we can decode them? (NOTE: These codes are practically useless, from an efficiency point of view. This is just a thought experiment to test the definition.)

The answer is YES, and a natural example are Gödel numberings! Here is how it works: for each letter \alpha in the alphabet \Sigma choose a distinct positive integer z_\alpha. Now, to encode a message

\displaystyle \alpha_1 \alpha_2 \cdots \alpha_n

let M be the positive integer defined as

\displaystyle M = 2^{z_1}3^{z_2}5^{z_3}\cdots p_n^{z_n}

where p_n is the nth prime number. We then send the binary expansion of M as our message.

How does Bob decrypt it? Easily: he reads ALL of M, factors it, and reads off the powers of the exponents: the order of the message is preserved if we read off in order of lowest prime to highest, where the power of the ith prime is the code of the ith symbol in the message. Bob has to read all of the message (and he has to make sure he’s transcribed it correctly), or else he cannot recover any of it! Marvelously useless.

OR IS IT USELESS? Similar ideas lurk under regular RSA encryption which everyone uses a billion times a day without even realizing it (thank you blaggerwebs). If factoring integers is as hard as complexity theorists believe it is, then Alice has just sent Bob a frustratingly uncrackable message.