• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

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érence
External document link
https://hal.inria.fr/hal-01675019
Date
2017
Conference title
Tenth Workshop on Information Theoretic Methods in Science and Engineering, Paris, France, September 11-13, 2017
Conference date
2017-12
Conference city
Helsinki
Conference country
FRANCE
Metadata
Show full item record
Author(s)
Durand, François
Mathieu, Fabien
Jacquet, Philippe
Abstract (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.

  • Thumbnail
    Can a Condorcet Rule Have a Low Coalitional Manipulability? 
    Durand, François; Mathieu, Fabien; Noirie, Ludovic (2016) Communication / Conférence
  • Thumbnail
    Using enterprise modelling methodologies for modelling agricultural activities and identifying information requirements. A case study of a livestock farm. 
    Abt, Vincent; Vigier, Frédéric; Pierreval, Henri; Bigeon, Jean-Baptiste; Durand, Cédric (2005) Communication / Conférence
  • Thumbnail
    Gender differences in hospital mortality and use of percutaneous coronary intervention in acute myocardial infarction : microsimulation analysis of the 1999 nationwide french hospitals database 
    Milcent, Carine; Dormont, Brigitte; Durand-Zaleski, Isabelle; Steg, Philippe Gabriel (2007) Article accepté pour publication ou publié
  • Thumbnail
    Coulomb potentials and Taylor expansions in time-dependent density-functional theory 
    Fournais, Søren; Lampart, Jonas; Lewin, Mathieu; Sørensen, Thomas Østergaard (2016) Article accepté pour publication ou publié
  • Thumbnail
    Classical field theory limit of many-body quantum Gibbs states in 2D and 3D 
    Lewin, Mathieu; Nam, Phan Thành; Rougerie, Nicolas (2021) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo