It is amazing to realize how complex things in Mathematics and in Computer Science can be reduced after all to 0 and 1, in other words, to the simple notion of difference… Is it beautiful or disappointing? Well, maybe both! Any resemblance to actual events is coincidental. In fact, and to be more precise, we must say sequences of 0 and 1, making then more apparent the role of ∞. In a way, Computer Science is the reign of finite sequences of 0 and 1 while Mathematics is the reign of infinite sequences of 0 and 1, in other words, the reign of ∞. Between the two, you may take a look at the concepts of Turing machines and Kolmogorov complexity. You may also take a look at Peano axioms and Gödel’s incompleteness theorems. In Probability Theory, the modelling of the Heads-or-Tails coin-tossing game involves a probability measure on {0,1}∞, the set of infinite sequences of 0 and 1. It has been shown recently that in a sense, almost all large statements are indecidable, see for instance
- Delahaye, J.-P.
Presque tout est indécidable !
Pour la Science 375 (January 2009) - Calude, C. S. (Editor)
Randomness and Complexity: From Leibniz to Chaitin
World Scientific (2007) ISBN 978-9812770820