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:
- 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);
- 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?