Shannon's information theory and foundations of mathematics

José Manuel Rodríguez Caballero josephcmac at
Fri Jun 3 23:06:05 EDT 2022

Gregory Chaitin's algorithmic information theory is related to the
foundations of mathematics, e.g., it can be used to prove some of Gödel's

Chaitin, Gregory J. "Gödel's theorem and information." *International
Journal of Theoretical Physics* 21.12 (1982): 941-954.

So, it is natural to ask whether the other information theory (the one
developed by Claude Shannon and Norbert Wiener) is somehow relevant to the
foundations of mathematics. According to Chaitin, the difference is as
follows (quote from the paper about):

Algorithmic information theory focuses on individual objects rather than on
> the ensembles and probability distributions considered in Claude Shannon
> and Norbert Wiener's information theory. How many bits does it take to
> describe how to compute an individual object? In other words, what is the
> size in bits of the smallest program for calculating it? It is easy to see
> that since general-purpose computers (universal Turing machines) can
> simulate each other, the choice of computer as yardstick is not very
> important and really only corresponds to the choice of origin in a
> coordinate system

I would like to point out that, according to Stéphane Mallat, Shannon's
information theory is more relevant for machine learning than algorithmic
information theory:

One possibility (conjecture) could be that the foundations of mathematics
on the one hand and statistics (including machine learning as a particular
case) on the other hand are like the position and momentum in quantum
mechanics: we can't use both information theories (Shannon and Chaitin) at
the same time to describe the same formal system. That is, the relevance of
one information theory implies the irrelevance of the other one in any
concrete situation.

Kind regards,
Jose M.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20220603/2b26bdb5/attachment.html>

More information about the FOM mailing list