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?
  • "Information should be understood as mere strings of symbols, and symbols are to be understood as generalized stuff (anything which can be distinguished) [...] 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 [...]." If information is a string of symbols which may represent arbitrary distinguishable things, what prevents you from simply concluding that two distinguishable referents is the minimum? Mar 13, 2013 at 17:38
  • 1
    Because someone lacking a background in coding theory doesn't find quite obvious that one single symbol (unary) isn't enough to construct distinguishable objects. In the answer of Rex Kerr below I explained the way I handle this questions, but I feel that is a huge overkill and there should be a simpler or more elegant argument to put binary as the minimal alphabet able to express any form of information (a fact which, in addition, is taken for granted in any standard textbook). I don't share the stance that binary is just an engineering choice: there's a minimalistic foundation justifying it.
    – Mono
    Mar 13, 2013 at 19:54
  • The problem with unary schemes is that they don't augment the number of distinct signals under the cartesian product. Finger counting of course corresponds to the coproduct, which aggregates distinct alternatives, so it is cheating to count them as being on a single alphabet; similar remarks apply to EOF, which merely indicates by position which element of a countable coproduct an element belongs to. So if we grant a straightforward theory of combinatorics, the simple "at least two symbols" answer suffices. (And if you have no theory of combinatorics, you cannot conclude anything.) Mar 13, 2013 at 19:56
  • If you can make an argument using only combinatorics justifying the minimality of the binary alphabet, and also explain why this fails for the naive intuition of counting fingers (or any other unary scheme) without expanding your "mathematical toolbox", then you should post it as an answer because that's the main question (a) that I've come here looking for a response for.
    – Mono
    Mar 13, 2013 at 20:16

3 Answers 3



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+1st 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, Σn. The problem with a unary alphabet Σ = {1} is that Σn 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]

  • "In order to have a unit of information, you must have at least two possible states of affairs". I don't want to be insistent on this, but the repetition of a single state of affairs (a unary scheme) seems intuitively enough to be a more minimalistic mean of expressing information. So I'm afraid you are repeating the standard attitude of considering this too obvious to require a justification.
    – Mono
    Mar 14, 2013 at 2:17
  • @mono: I don't see where you find the problem here - it seems like a basic point to me, but I may be missing something. Can you describe your 'unary scheme that is a more minimalistic means of expressing information'? Mar 14, 2013 at 7:32
  • @mono: I have elaborated my response. (N.B. I do not make specific reference to coproducts, because although I believe that this is the appropriate way to describe selecting between one or more distinguishable items, it is moot if the problem is to find ways to distinguish the elements in the first place.) Mar 14, 2013 at 14:11
  • @NieldeBeaudrap: I thank you for the elaboration. This is the kind of answer I was looking for. I find the last sentence particularly valuable -if the length of a message is uncertain, every message must contain, apart from its length as given by itself which is trivially recognizable as received, an additional distinguishable which states explicitly what that length is. And a unary message can only signal its intrinsic length, not what this length is in addition to that. Doing so requires a marker, and so at least a binary alphabet (and the alphabet choice is justified by minimalism).
    – Mono
    Mar 14, 2013 at 14:43
  • You could also argue that, lacking a second symbol, the unary scheme can only produce strings which -being prefixes of every larger admissible one- keep ambiguous until the maximum admissible length of a message is reached (i.e. the set of ten fingers in a hand). This maximum length string isn't ambiguous, but is the only unambiguous message which can be ever encoded in the scheme; and if there's no maximum length (i.e. a classical communication channel) then every finite message is ambiguous. I have to admit this argument is not as succinct as I would have preferred originally, but is enough.
    – Mono
    Mar 14, 2013 at 14:52

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.

  • Your answer is the only one so far which addresses what I was asking. On the one hand, you point out another reason (perhaps more fundamental) why computation seems not to be a "self-contained primitive" over which information should be defined; I focused on the compulsory reference to inputs-outputs external to the notion of computation, and you pointed to the relativity associated to the Kolmogorov definition (cause of the size of the constant term, which only becomes negligible when describing very long sequences, analogously to the statistical limit of source coding in the Shannon theory).
    – Mono
    Mar 13, 2013 at 14:51
  • On the other hand, and because the notion of computation involves some "interaction" (i.e. processing) of raw strings of symbols, I prefer to use the term complexity for those metrics, and reserve "information" to refer to general strings, i.e. sequences of symbols "as given". In this sense I wanted to have a succinct argument (but semi-formal, or at least not purely heuristic) for the idea that two symbols are the minimal set of different values enough to express any information. I haven't read any book in information theory where this matter deserves a reserved space; it is just "assumed".
    – Mono
    Mar 13, 2013 at 15:00
  • @Mono - Are you looking for anything more elaborate than if you have only one thing there are no distinctions and no information; the least you can add to the picture is one more thing, which gives you a distinction and the possibility for information.
    – Rex Kerr
    Mar 13, 2013 at 15:07
  • I would really appreciate if you could cite the literature where it is established that "the computationally most trivial representation is with log = log2". It is certainly a "trivial problem" for someone initated in the field, but no that trivial when explaining to someone else. I have been asked by people "why not unary, given that we count with fingers" and in those cases I had to point to the necessity of markers at the end of every string, something impossible in a single-symbol alphabet, but the whole argument seemed always an overkill.
    – Mono
    Mar 13, 2013 at 15:08
  • Exactly, but not too heuristic though. I want to be able to rule out any other seemingly "simpler" schemes (I can only think about unary, but may be there's something else out there) without resort to an overkill, like citing coding theory (which is what I'be been answering when asked about counting fingers).
    – Mono
    Mar 13, 2013 at 15:12

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.

  • What other basis for defining information would you choose? Is there any way you can obtain a unit of information which does not boil down to a yes/no distinction? Mar 15, 2013 at 11:16
  • @deBeaudrap: Why is it neccessary to boil down? I know why its done, the virtues are pragmatic; but that doesn't make that representation of information fundamental. For example, Turing machines operate with an infinite strip marked by ones and zeros, but one can actually use other alphabets. Mar 15, 2013 at 21:45
  • @Ullah: in the context of the question, "fundamental" means "nothing simpler or lesser" as a unit of information, as per the OP. Not simpler to work with, but minimal. Mar 15, 2013 at 22:28
  • @DeBeaudrap: I do realise that. Thats why I said the simplest representation was in base 2. The focus of my answer was why a minimal representation is 'unsatisfactory' and like 'turning the world on its head'. Mar 16, 2013 at 2:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .