Succinct argument for the fundamental role of binary digits as information units

Question

I will clear up the context of this question so that the potential answers can be effectively targeted towards what I'm looking for.

Information (at least in the non-semantic, canonical sense of the word) can be defined using either the Shannon statistical approach or the Kolmogorov computational one. The former establishes it as a notion of average codeword length expressed in some arbitrary alphabet -which is deliberately chosen to be the binary alphabet in any textbook I can cite- needed to establish a bijective mapping to the outcomes of a random source; the Source Coding Theorem proves this definition to be equal to the entropy of the source in the statistical limit of an infinite number of outcomes. The second approach makes use of universal computers in some arbitrary model (almost always chosen to be an UTM), and then defines the information contained in a source as the length of the minimal self-delimited program in the language of the computer which outputs the outcomes of the source; as the choice of a reference UTM can only make the length of a minimal program a constant term different than in any other choice, the definition is quite robust.

Indeed, the Kolmogorov approach subsumes the Shannon definition, because the probability distribution priors needed to encode the source and decode the messages are equivalent to a Turing Machine which computes an entropy encoding scheme (like Huffman or Arithmetic encodings).

So, in essence, the modern definition of "information" is in turn based on the extremely flexible and unique (i.e. absolute) definition of computation brought about by the universality results of the first half of the twentieth century.

Nevertheless, I find this story somewhat unsatisfactory. Using computation as a foundation for information seems like turning the world on its head, at least under an intuitive understanding of what the term denotes and in opposition to the canonical definitions of Shannon and Kolmogorov. Computers are procedures (or procedure-following objects, a meaningless difference under the light of Turing universality and mutual simulation of machines) and so, they are a particular kind of relation -recursion- between an input and an output. Even though this kind of relation is unique and absolute, it seems to me to be necessarily ex post to the notion of input and output; and those two are the "stuff" that intuitively matches the term "information". You can say a computation exists by showing a history of the steps (the stacked list of inputs-outputs), the same way you can explicitly show a logical deduction in sequent notation. The Church-Turing thesis then would just state that the class of stackings of inputs and outputs which can effectively be produced by any means, is exhausted by the Turing Machine or by any other equivalent model of computation.

On the other hand, the "stuff" which makes up the inputs and outputs (intuitive information) in principle doesn't necessarily need an auxiliary reference to computation to be said to exist. A string of symbols doesn't need to be related to any other one; it can exist in isolation, so no compulsory reference to a procedure is required (again, I'm leaving the formalization of this intuition as an exercise to the reader; I just expect to be talking with enough sense to be understood).

To end this section I leave this resume:

1. Information, understood in an intuitive sense of "generalized abstract stuff", seems to be more fundamental than computation given that the concept of procedure implies a reference to the former. Information should be understood as mere strings of symbols, and symbols are to be understood as generalized stuff (anything which can be distinguished);
2. What the canonical term "information" refers to, is a computational property of information in the sense of 1. I personally prefer to use the term complexity in both cases of the Shannon and Kolmogorov definitions, and preserve the term information to mere "stuff" (without reference to computation or probability priors; i.e. strings "as given").

Assuming that information is the fundamental stuff required for the concept of computation to make sense, one may wonder what is the minimal alphabet (i.e. the minimal amount of different symbols) which is needed to express any form of information in the sense I explained above. The obvious response might be that the binary alphabet is the answer to this question -after all, the bit is used as a universal measure of channel capacity. But it turns out, I haven't found in any textbook I've read a section dedicated to stating and formally proving this, let alone to elegantly and succinctly doing it! Again, it may sound obvius, but if the foundations of science are information and computation (a trend which has been going on for almost a century by now) I seriously think it should be established that the binary digit is the "most simple and fundamental possible unit of (generalized) stuff".

I will now state my question properly:

• a) How can be proved succinctly (but not heuristically) that the bit is the fundamental unit of information, and there's nothing simpler or lesser which could do the job?

And I leave this meta-question, based on the overly-long introduction to the main question:

• b) Is there a book where information is developed from the "bottom-up" approach I've called "the intuitive sense of the word information" here, i.e. taking strings of symbols as fundamental, and then developing derived notions like computation and statistics from there?

And finally, of course:

• c) Does all I've wrote here make any sense?

Answer 1

Summary

Information distinguishes between multiple states of affairs; which indicates at the very least a bias in the likelihood that some state of affairs is realized, and ideally which indicates that some single state of affairs is realized while a number of alternatives have not been.

In order to have a unit of information, you must have at least two possible states of affairs. Conventionally, we might describe these states of affairs as being the truth-value of a logical proposition: we either have A, or not-A. Such binary distinctions are the crudest, and most elementary, ways of distinguishing states of affairs in classical (and related boolean-style forms of) logic. Any theory of information arising from such a logic will inevitably tend towards indicating bivalent choices — i.e. a bit — as the unit of information.

Combinatorics and the necessity of alphabets of size > 1

We may consider the problems with obtaining something which is more minimal, specifically a unary approach which involves a one-letter alphabet (but where we have words of varying lengths) by seriously considering what combinatorial machinery is required to get more than one possibility out of a unary framework. In the comments, you propose a setting in which there are messages consisting of a single letter, possibly augmented by a single-use "end of file" character. Let me denote those two letters by '1' and 'E'.

In the multiletter setting, we still want to express more than a finite number of signals despite having an alphabet of finite size. (Attempts to use infinite alphabets will give rise to precision issues, where we must somehow certify the distinctness of two 'letters'. This is a boot-strapping problem without an apparent resolution. So we restrict ourselves to finite alphabets.) The way we deal with this is to associate different states of affairs with sequences of characters with distinct states of affairs. The game "twenty questions" is a good example of this (albeit in an interactive setting) where one tries to infer the identity of an object through a sequence of yes/no questions of fixed length.

So, we can simulate an alphabet T of arbitrary size, simply by using a sufficiently large number of characters from a smaller alphabet Σ. But unless you use a fixed code, where from the first n characters you can be certain of whether or not you await an n+1^st character to complete the message, you must use strings of a fixed length.

We can model fixed-length strings by the n-fold (Cartesian) product of the alphabet with itself, Σⁿ. The problem with a unary alphabet Σ = {1} is that Σⁿ has the same size as Σ itself, which defeats the purpose.

What prevents us from considering variable-length strings? If we have multi-letter alphabets, nothing at all; but we must be clear how we are describing the length of the string — which, metadata or not, is still information; it defines how we are meant to interpret the signal. On a hard drive, for instance, an end-of-file character E does not actually signify that there is no information whatsoever following the disk; only that whatever data that follows is irrelevant to the information being conveyed (for instance, by the specific file being referred to).

Mathematically, we can describe files of length ranging from 0 to n by using one of the characters E to signify 'end-of-message', meaning that two strings which agree up to that character are to be regarded as equivalent. For example, using an alphabet Σ = {1,E}, we would say that the two strings

111E1111   and   111E1EE1

as equivalent, as they agree up to the left-most E character. We would abbreviate the equivalence class to which both of those strings belong as 111. However, we do need the second character to define where the "information content" of the string ends, and thereby indicate which equivalence class of strings we intend by the message. This would also be true in a practical communications context, where protocols are set up to indicate to various devices when they are, in fact, no longer in communication with a remote device (rather than interpreting random noise as data).

Of course, we usually do not describe strings of varying lengths in terms of equivalence classes of strings of any finite or infinite length. This, however, is a convenience; in everyday practice, in mathematics as in normal prose, we have end-of-sequence markers if only in the form of whitespace and punctuation, which is itself a distinguishable signal from any marking such as 0 or 1; when I write 11 and 101, you know that these are strings of length 2 and 3 respectively because one is terminated by a blank, and another by a comma. You do not mistake them for the strings "11 an..." or "101, you kn..." because the conventions of our written language establish these as potential end-of-sequence markers for words or strings of characters in general. That is, they convey that information. Without interpreting them in this way, you would have no idea when a word or a sentence ended, and thus no place to bound the complexity of the message that I am sending to you.

Someone who insists (I would say naïvely) that they can 'intuitively' distinguish unary sequences of arbitrary length, and thus communicate different messages with the strings 1, 11, 111, 1111, 11111, etc., I would say that this again falls to the same problem as having an alphabet of infinite length; metadata becomes crucial to the problem of distinguishing possible signals, and therefore in the end the metadata encodes the message — i.e. the metadata is the data itself. I do not think it is possible to immediately grasp the difference between two messages 111...1 which continue for 1000 characters, from one of 1001 characters; the representation itself must contain clues about where the message begins and ends, if only in the form of whitespace of a quiescent baseline signal in place of an overt signal. Distinguishing whether or not the message has ended becomes crucial to determining where the message has ended.

The division of characters into 'data' and 'metadata' is a division that we make ourselves, practically, with respect to messages. However, metadata still communicates states of affairs which may prove essential to the correct interpretation of the message sent. For example, and end-of-file character indicates the state of affairs "there are no more characters which play a role in the message", while every character which (in or out of context) does not indicate an end-of-file for messages of uncertain length, indicates "more characters are necessary for disambiguation". If the role of information fundamentally is to disambiguate states of affairs, then our own division of states of affairs into "those which concern the message itself" and "those which do not concern the message itself" is incidental, however useful it is practically to do so. If the message is of uncertain length, it is necessary to have a means of communicating what the length of the message actually is; and this is impossible to do with a single-letter alphabet, which — because it can only communicate one message of any fixed length — cannot in any number of characters distinguish between two states of affairs.

[Edited to add remarks on combinatorics, unary schemes]

Answer 2

I think you're right that computation is not fundamental, but to me the point of using computation is that universal computation lets you compute anything including any metric of information that you might like. Therefore, measuring information in terms of computation is merely availing yourself of infinite expressive capability. It's not a statement that computation is the key thing here, just that you can do whatever you want with it.

Also, constant factors matter a lot. If I invent a programming language which contains the previous paragraph as the symbol ☆ then there is just a constant factor difference in program length to express the above paragraph (some 440x), and yet I have failed utterly to capture the intuition about information that Kolmogorov was presumably aiming for. If you do not self-impose the limitation to use compact general-purpose computing devices, Kolmogorov information measures return nonsensical results. This also illustrates that computation is not what is fundamental about information. Rather, it is a tool (that must be appropriately used) for analysis.

That said, I do not believe you can "prove" that the bit is the fundamental unit of information. You can certainly adopt a set of axioms that include something logically equivalent to "the bit is the fundamental unit of information". Most texts on Shannon information do exactly this (in that they prove that the Shannon information of -p log p is the right one^†, and the computationally most trivial representation* is with log = log2). But if you ask on a deeper level, I don't think you can show that the bit is fundamental rather than the action potential (or synaptic release) from a biological perspective; or than the standard deviation (or confidence interval) from an analog statistical perspective. At some level they're all equivalent (but you have to dig pretty hard to get from each to the other), and which you favor will depend on your perspective.

^{† For a very good reason, as any introductory textbook will prove to you.}

* ^{Not for any really good reason except that two states is the minimum possible number, and it just so happens that physics conspires to make two-state devices easier to build than others, and so our computers are binary.}

Answer 3

I don't think the bit is the fundamental unit of information. It is from a certain perspective, but others could be chosen.

The rationale in brief goes like this:

a. What knowledge we have can be codified mathematically

b. mathematics can always be coded as numbers

c. the simplest representation in a number system is in base 2

step a) is where knowledge as opposed to information commonly falls down which is what you point out by admitting the difference between information and 'semantics'. The bit is simply a good engineering choice - this is not to detract from its importance. When it is said the bit is fundamental the context should be preserved and this is the computational and engineering context.

Writing is a form of information, were there no actual person to understand it, it would be merely a sequence of geometric forms separated by spaces.

You're right about mistaking information (as in bits) that is c) for knowledge a) is turning the world upside down. But of course bits can themselves become a new source of knowledge. So the situation is more subtle than I've described.