Shannon, Turing and Hats: Information Theory Incompleteness
Durand, François; Mathieu, Fabien; Jacquet, Philippe (2017), Shannon, Turing and Hats: Information Theory Incompleteness, Tenth Workshop on Information Theoretic Methods in Science and Engineering, Paris, France, September 11-13, 2017, 2017-12, Helsinki, FRANCE
Type
Communication / ConférenceExternal document link
https://hal.inria.fr/hal-01675019Date
2017Conference title
Tenth Workshop on Information Theoretic Methods in Science and Engineering, Paris, France, September 11-13, 2017Conference date
2017-12Conference city
HelsinkiConference country
FRANCEMetadata
Show full item recordAbstract (EN)
When Claude Shannon introduced his theory of information in 1948, he was mainly targeting potentially infinite sequences of symbols, e.g. finite sequences whose length n were tending to infinity. Parameters like information rate, error correction, compress-ibility and predictability are defined for finite n with interesting properties when n tends to infinity. Here we consider that the sequence of events is truly infinite (past and future). Manipulate truly infinite sequences is not exactly the same as manipulating potentially infinite sequences. Prediction can be related to infinite hat puzzles, so that if we introduce the axiom of choice in information theory over infinite sequences, then the number of prediction errors on an infinite sequence is finite. This implies that the prediction error rate is actually zero. This is a rather surprising result since the infinite sequence could have been generated by a memoryless source. Moreover, if the infinite sequence is a computable sequence toward the past, then we get the zero error rate result without the axiom of choice. This is also a surprising result since a computable sequence is not necessarily computable toward the future, since a Turing machine is not necessarily reversible.Related items
Showing items related by title and author.
-
Durand, François; Mathieu, Fabien; Noirie, Ludovic (2016) Communication / Conférence
-
Abt, Vincent; Vigier, Frédéric; Pierreval, Henri; Bigeon, Jean-Baptiste; Durand, Cédric (2005) Communication / Conférence
-
Milcent, Carine; Dormont, Brigitte; Durand-Zaleski, Isabelle; Steg, Philippe Gabriel (2007) Article accepté pour publication ou publié
-
Fournais, Søren; Lampart, Jonas; Lewin, Mathieu; Sørensen, Thomas Østergaard (2016) Article accepté pour publication ou publié
-
Lewin, Mathieu; Nam, Phan Thành; Rougerie, Nicolas (2021) Article accepté pour publication ou publié