|
Selected EAIT Papers
FAQs We have coined the term Experimental Algorithmic Information Theory or EAIT to emphasize the experimental character of our research. EAIT is a multidisciplinary research program seeking to connect theoretical computer science to the real-world by way of computer experiments in the spirit of Stephen Wolfram's research program (NKS). It is close to the concepts of Bit-String Physics, Digital Mechanics (or Digital Philosophy) and Meta-mathematics as described by Gregory Chaitin. Nicolai Kolmogorov together with Ray Solomonoff, Leonid Levin and Gregory Chaitin created the field of Algorithmic Information Theory (AIT), sometimes referred to as program-size, algorithmic or simply Kolmogorov complexity. Greg Chaitin has been a particularly forceful advocate of a quasi-empirical approach to mathematics—one that involves performing experiments and running programs—to initiate a paradigm shift in the way math is done, calling this approach meta-mathematics. This approach is consonant with the one proposed by Stephen Wolfram's NKS spuring the exploration of what Wolfram has coined as the Computational Universe. Within this concepts, we have beendeveloping a hands-on approach to Algorithmic Information Theory.
Who is involved in EAIT? Hector Zenil started the project as a graduate student of Jean-Paul Delahaye at the computer science laboratory of Lille. Delahaye is a professor of computer science at the University of Lille. One of his main research interests has been algorithmic information theory for a long time. He suggested the first ideas that led to the conception of EAIT. He has been a long time popular science writer of algorithmic complexity and randomness, including the popularization of Chaitin's number, and often highligting the subtle but fundamental difference between organized and random complexity (the former related to the concept of logical depth developed by Charles Bennett and the latter related to the traditional algorithmic complexity). The research program formaly began with Hector Zenil's PhD thesis in 2006. Delahaye and Zenil main inspiration and theoretical basis came from the works of Leonid Levin, Greg Chaitin and Ray Solomonoff, and the more recent work of Cristian Calude, Ming Li, Paul Vitanyi, Walter Kirchherr and Stephen Wolfram. It has been the result of the interactions with some of these researchers that this research has been shaped.
Since the days of Newton and Leibniz, scientists have been constructing elaborated views of the world. In the past century, quantum mechanics revolutionized our understanding of physical reality at atomic scales, while general relativity did the same for our understanding at large scales. Beyond the fact that these two general theories do not reconciliate each other mainly due to the linearity of the former as opposed to the nonlinearity found in the dynamics at all other scales, our current understanding of quantum mechanics suggests that randomness is an intrinsic property of physical reality (at least at some scale) while the study of nonlinear dynamics has shown that even classical mechanics has unpredictability at its core. Some contemporary scientists have recently come up with theories in which nature is seen as processing information computing the laws of physics and everything we see around us, including all sorts of complex things like life. In this view, the universe would be computing itself and our computers would betherefore doing nothing but reprograming a part of the universe to make it compute what we want to compute. Some of these views support the idea that nature is, or can be better studied if seen as, performing (only) digital computations. Fredkin, for example, assumes that the universe is describable by digital information and therefore the universe can be conceived as either the output of some computer program or as being some sort of vast digital (Turing complete) machine. Wolfram, on the other hand, claims that the world may turn out to be produced by a set of very simple rules being computed for a long time capable of generating the great complexity we see around us. If so, Wolfram suggests, one can go hunting for our universe (the very program that generates it). John Archibald Wheeler's "It from bit" or Feynman's quotation, illustrates the early anticipation of this digital shift to understanding physics in terms of information. "It always bothers me that, according to the laws as we understand them today, it takes a computing machine an infinite number of logical operations to figure out what goes on in no matter how tiny a region of space, and no matter how tiny a region of time ... So I have often made the hypothesis that ultimately physics will not require a mathematical statement, that in the end the machinery will be revealed, and the laws will turn out to be simple, like the chequerboard with all its apparent complexities." Richard Feynman in 1964, It is not unreasonable to imagine that information sits at the core of physics, just as it sits at the core of a computer. It from bit. Otherwise put, every 'it'—every particle, every field of force, even the space-time continuum itself—derives its function, its meaning, its very existence entirely—even if in some contexts indirectly—from the apparatus-elicited answers to yes-or-no questions, binary choices, bits. 'It from bit' symbolizes the idea that every item of the physical world has at bottom—a very deep bottom, in most instances—an immaterial source and explanation; that which we call reality arises in the last analysis from the posing of yes–no questions and the registering of equipment-evoked responses; in short, that all things physical are information-theoretic in origin and that this is a participatory universe. John Archibald Wheeler in1990, There are also those who believe that nature does not only perform digital computations but rather quantum computations (e.g. David Deutsch, Charles Bennett, Seth Lloyd) namely because our world is mean to carry out quantum processes according to the the current model of physics, with digital computation being the handicapped part (after decoherence) of a quantum computation (in words of Bennett). Some theories under development are attempting to unify these views based in the works of 't Hooft, Susskind and Smolin on quantum gravity (e.g. Computational Loop Quantum Gravity). These contemporary views of a computational universe are deeply related by the concept of information to a contemporary mathematical field of research called algorithmic information theory (AIT). AIT researchers think that the true nature of nature can only be explained by the study of randomness (e.g. Greg Chaitin, Leonid Levin). The study of randomness leads to the definition of complexity and information in algorithmic terms. What we think and what our research program claims is that if the world is truly either computing or a computer by itself (digital or quantum) it should follow the same algorithmic laws that computers do, like the production of an output in accordance to the frequencies of what algorithmic probability predicts. We are interested in the question of whether nature is, or behaves as, such a computer, as an information processor. We think the question is currently within the scope of modern scientific research and it is therefore a falsifiable statement. We think there may be evidence to be had from a comparison between the outcome of the world itself and the expected output of purely digital computation. In the way, we have been connecting the theory to the real-world, from experimental approaches to the theory, such as the evaluation of the program-size complexity of strings by exhaustive means, to the algorithmic study of the behavior of financial markets, to applications of the concept of logical depth for image characterization and classification.
Other online resources
Basic bibliography
Back to the main page |
 |
Hector Zenil's blog H. Zenil FQXi 3rd. Prize "The World is Either Algorithmic or Mostly Random" Randomness Through Computation Computation in Nature The shortest universal machine implementation contest
More links Turing machines from the Stanford Encyclopedia of Philosophy Busy Beaver machine Algorithmic randomness from Scholarpedia Algorithmic complexity Applications of AIT Algorithmic probability Pascal Michel's Historical survey of busy beaver results The 2,3 Wolfram Turing Machine Research Prize Laboratoire d'Informatique Fondamentale de Lille Institute d'Histoire et Philosophie des Sciences et Techniques
|
to download the supporting material related to the paper.