This is a presentation about joint work between Hector Zenil and Jean-Paul Delahaye. Zenil presents Experimental Algorithmic Theory as Algorithmic Information Theory and NKS, put together in a mixer. Algorithmic Complexity Theory defines the algorithmic complexity k(s) as the length of the shortest program that produces s. But since finding this short program is in general an undecidable question, the only way to approach k(s) is to use compression algorithms. He shows how to use the Compress function in (...) Mathematica to give an idea about the compressibility of various sequences. However, the idea of applying a compression algorithm breaks down for very short sequences. This is true not only for the Compress function, but also for any other compression algorithm. Zenil's approach is to construct a metric of algorithmic complexity for short sequences from scratch. He defines the algorithmic probability as the probability that an arbitrary program produces a sequence. The basic idea is to run a whole class of computational devices such as Turing Machines or Cellular Automata, and compute the distributions of the sequences they generate. Zenil presents a comparison of frequency distributions of sequences generated by 2-state 3-color Turing Machines and 2-color radius 1 Cellular Automata. He also compared these distributions to distributions found in data from the real world, and found that not only there is correlation across different systems, but also that the distributions are rather stable, and the difference between the distributions in abstract systems and real-world data can be attributed to noise. In his paper Zenil elaborates on the nature of the noise he has encountered. Zenil conjectures that the correlation distances between different systems decreases with a larger number of steps, and converge in the infinite limit case. (shrink)

This paper proposes an extension of Chaitin's halting probability Ω to a measurement operator in an infinite dimensional quantum system. Chaitin's Ω is defined as the probability that the universal self-delimiting Turing machine U halts, and plays a central role in the development of algorithmic information theory. In the theory, there are two equivalent ways to define the program-size complexity H of a given finite binary string s. In the standard way, H is defined as the length (...) of the shortest input string for U to output s. In the other way, the so-called universal probability m is introduced first, and then H is defined as –log2m without reference to the concept of program-size.Mathematically, the statistics of outcomes in a quantum measurement are described by a positive operator-valued measure in the most general setting. Based on the theory of computability structures on a Banach space developed by Pour-El and Richards, we extend the universal probability to an analogue of POVM in an infinite dimensional quantum system, called a universal semi-POVM. We also give another characterization of Chaitin's Ω numbers by universal probabilities. Then, based on this characterization, we propose to define an extension of Ω as a sum of the POVM elements of a universal semi-POVM. The validity of this definition is discussed.In what follows, we introduce an operator version equation image of H in a Hilbert space of infinite dimension using a universal semi-POVM, and study its properties. (shrink)

The aim of this paper is to comprehensively question the validity of the standard way of interpreting Chaitin's famous incompleteness theorem, which says that for every formalized theory of arithmetic there is a finite constant c such that the theory in question cannot prove any particular number to have Kolmogorov complexity larger than c. The received interpretation of theorem claims that the limiting constant is determined by the complexity of the theory itself, which is assumed to be (...) good measure of the strength of the theory. I exhibit certain strong counterexamples and establish conclusively that the received view is false. Moreover, I show that the limiting constants provided by the theorem do not in any way reflect the power of formalized theories, but that the values of these constants are actually determined by the chosen coding of Turing machines, and are thus quite accidental. (shrink)

By formalizing Berry's paradox, Vopěnka, Chaitin, Boolos and others proved the incompleteness theorems without using the diagonal argument. In this paper, we shall examine these proofs closely and show their relationships. Firstly, we shall show that we can use the diagonal argument for proofs of the incompleteness theorems based on Berry's paradox. Then, we shall show that an extension of Boolos' proof can be considered as a special case of Chaitin's proof by defining a suitable Kolmogorov complexity. (...) We shall show also that Vopěnka's proof can be reformulated in arithmetic by using the arithmetized completeness theorem. (shrink)

We investigate two constants cT and rT, introduced by Chaitin and Raatikainen respectively, defined for each recursively axiomatizable consistent theory T and universal Turing machine used to determine Kolmogorov complexity. Raatikainen argued that cT does not represent the complexity of T and found that for two theories S and T, one can always find a universal Turing machine such that equation image. We prove the following are equivalent: equation image for some universal Turing machine, equation image for (...) some universal Turing machine, and T proves some Π1-sentence which S cannnot prove. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. (shrink)

This book brings together an impressive group of leading scholars in the sciences of complexity, and a few workers on the interface of science and religion, to explore the wider implications of complexity studies. It includes an introduction to complexity studies and explores the concept of information in physics and biology and various philosophical and religious perspectives. Chapter authors include Paul Davies, Greg Chaitin, Charles Bennett, Werner Loewenstein, Paul Dembski, Ian Stewart, Stuart Kauffman, Harold Morowitz, Arthur (...) Peacocke, and Niels H. Gregersen. (shrink)

The information-theoretic point of view proposed by Leibniz in 1686 and developed by algorithmic information theory (AIT) suggests that mathematics and physics are not that different. This will be a first-person account of some doubts and speculations about the nature of mathematics that I have entertained for the past three decades, and which have now been incorporated in a digital philosophy paradigm shift that is sweeping across the sciences.

We study partitions of Fraïssé limits of classes of finite relational structures where the partitions are encoded by infinite binary strings which are random in the sense of Kolmogorov-Chaitin.

We discuss mathematical and physical arguments against continuity and in favor of discreteness, with particular emphasis on the ideas of Émile Borel.

Hi everybody! It's a great pleasure for me to be back here at the new, improved Santa Fe Institute in this spectacular location. I guess this is my fourth visit and it's always very stimulating, so I'm always very happy to visit you guys. I'd like to tell you what I've been up to lately. First of all, let me say what algorithmic information theory is good for, before telling you about the new version of it I've got.

This accessible book gives a new, detailed and elementary explanation of the Gödel incompleteness theorems and presents the Chaitin results and their relation to the da Costa-Doria results, which are given in full, but with no ...

We investigate the initial segment complexity of random reals. Let K denote prefix-free Kolmogorov complexity. A natural measure of the relative randomness of two reals α and β is to compare complexity K and K. It is well-known that a real α is 1-random iff there is a constant c such that for all n, Kn−c. We ask the question, what else can be said about the initial segment complexity of random reals. Thus, we study the (...) fine behaviour of K for random α. Following work of Downey, Hirschfeldt and LaForte, we say that αK β iff there is a constant such that for all n, . We call the equivalence classes under this measure of relative randomness K-degrees. We give proofs that there is a random real α so that lim supn K−K=∞ where Ω is Chaitin's random real. One is based upon work of Solovay, and the other exploits a new idea. Further, based on this new idea, we prove there are uncountably many K-degrees of random reals by proving that μ=0. As a corollary to the proof we can prove there is no largest K-degree. Finally we prove that if n ≠ m then the initial segment complexities of the natural n- and m-random sets and Ω︀) are different. The techniques introduced in this paper have already found a number of other applications. (shrink)

Chaos, once considered antithetical to scientific law and order, is presently the subject of a vigorous and progressive scientific research program. "Chaos" as it is used in current scientific literature is a technical term: it refers to stochastic behavior generated by deterministic systems. This behavior has appeared in models of a wide range of phenomena including atmospheric patterns, population dynamics, celestial motion, heartbeat rhythms, turbulent fluids, chemical reactions and social structures. In general, chaos arises in the nonlinear dynamics of complex (...) systems. Grebogi, Ott and Yorke reflect the sentiment of the scientific community when they state that chaotic nonlinear dynamics has "fundamental implications." This dissertation explores these results in a philosophic context. ;The research is organized as follows: The Context of Science. Scientific results are achieved in and make sense in the practical context of research which includes both experiment and theory. Drawing on the work of Dyke, Galison, Garfinkel and Hacking, a philosophic context is described which more accurately reflects the significance of scientific results than do the contexts of discovery and justification. Models. Chaos theory is constituted by a family of numerical models. In this chapter, Giere's account of modeling is extended to both bio-medical and numerical models. Chaos in Scientific Models. This is a rather lengthy primer of chaos theory that is, although technically accurate, accessible to nonspecialists. It constitutes a road map for the primary literature on chaos. Chaos and Prediction. Chaos theory shows a limit of our science, namely, chaotic systems are deterministic yet unpredictable in the long run. The chapter includes a discussion of scientific determinism following Popper and, it concludes by providing evidence against the laplacian claim that deterministic systems are predictable. Chaos and Complexity. This shows what contribution chaos theory makes toward answering the challenge of organized complexity articulated by Weaver. It discusses attempts to characterize complexity and shows how the results of chaos theory can help. I draw on the work of Abraham, Arecchi, Atlan, Chaitin, Eckmann, Peacocke, Rosen, Ruelle, and others. Chaos theory provides a thoroughly nonvitalistic framework for understanding dynamical complexity in organic, as well as inorganic, systems. (shrink)

It is argued that the truth status of emergent properties of complex adaptive systems models should be based on an epistemology of proof by constructive verification and therefore on the ontological axioms of a non-realist logical system such as constructivism or intuitionism. ‘Emergent’ properties of complex adaptive systems models create particular epistemological and ontological challenges. These challenges bear directly on current debates in the philosophy of mathematics and in theoretical computer science. CAS research, with its emphasis on computer simulation, is (...) heavily reliant on models which explore the entailments of Formal Axiomatic Systems. The incompleteness results of G¨odel, the incomputability results of Turing, and the Algorithmic Information Theory results of Chaitin, undermine a realist truth model of emergent properties. These same findings support the hegemony of epistemology over ontology and point to alternative truth models such as intuitionism, constructivism and quasi-empiricism. (shrink)

MATHEMATICS is a wonderful, mad subject, full of imagination, fantasy and creativity that is not limited by the petty details of the physical world, but only by the strength of our inner light. Does this sound familiar? Probably not from the mathematics classes you may have attended. But consider the work of three famous earlier mathematicians: Leonhard Euler, Georg Cantor and Srinivasa Ramanujan.

This article explores methodological issues central to the undertaking of joint Palestinian-Israeli research, work that is impacted by the violent conflict between the two peoples. Four issues are discussed: (a) collaborating under conflict, that is, how the conflict impacts relations between the researchers on either side of the border, (b) issues of power and equality, as they impact the research process, (c) relationships with participants, that is, how the conflict influences relations between the researcher and the research participants, and (d) (...) rethinking standards, that is, whether the normative standards of research quality are relevant for Palestinian-Israeli collaborative research. The article presents examples from joint research and offers preliminary ideas for dealing with these methodological issues. (shrink)

In a famous lecture in 1900, David Hilbert listed 23 difficult problems he felt deserved the attention of mathematicians in the coming century. His conviction of the solvability of every mathematical problem was a powerful incentive to future generations: ``Wir müssen wissen. Wir werden wissen.'' (We must know. We will know.) Some of these problems were solved quickly, others might never be completed, but all have influenced mathematics. Later, Hilbert highlighted the need to clarify the methods of mathematical reasoning, using (...) a formal system of explicit assumptions, or axioms. Hilbert's vision was the culmination of 2,000 years of mathematics going back to Euclidean geometry. He stipulated that such a formal axiomatic system should be both `consistent' (free of contradictions) and `complete' (in that it represents all the truth). Hilbert also argued that any wellposed mathematical problem should be `decidable', in the sense that there exists a mechanical procedure, a computer program, for deciding whether something is true or not. Of course, the only problem with this inspiring project is that it turned out to be impossible. (shrink)

Let ω be a Kolmogorov–Chaitin random sequence with ω1: n denoting the first n digits of ω. Let P be a recursive predicate defined on all finite binary strings such that the Lebesgue measure of the set {ω|∃nP(ω1: n )} is a computable real α. Roughly, P holds with computable probability for a random infinite sequence. Then there is an algorithm which on input indices for any such P and α finds an n such that P holds within the (...) first n digits of ω or not in ω at all. We apply the result to the halting probability Ω and show that various generalizations of the result fail. (shrink)

We call A weakly low for K if there is a c such that $K^A(\sigma)\geq K(\sigma)-c$ for infinitely many σ; in other words, there are infinitely many strings that A does not help compress. We prove that A is weakly low for K if and only if Chaitin's Ω is A-random. This has consequences in the K-degrees and the low for K (i.e., low for random) degrees. Furthermore, we prove that the initial segment prefix-free complexity of 2-random reals (...) is infinitely often maximal. This had previously been proved for plain Kolmogorov complexity. (shrink)

This book is a state-of-the-art review on the Physics of Emergence. Foreword v Gregory J. Chaitin Preface vii Ignazio Licata Emergence and Computation at the Edge of Classical and Quantum Systems 1 Ignazio Licata Gauge Generalized Principle for Complex Systems 27 Germano Resconi Undoing Quantum Measurement: Novel Twists to the Physical Account of Time 61 Avshalom C. Elitzur and Shahar Dolev Process Physics: Quantum Theories as Models of Complexity 77 Kirsty Kitto A Cross-disciplinary Framework for the Description of (...) Contextually Mediated Change 109 Liane Gabora and Diederik Aerts Quantum-like Probabilistic Models Outside Physics 135 Andrei Khrennikov Phase Transitions in Biological Matter 165 Eliano Pessa Microcosm to Macrocosm via the Notion of a Sheaf (Observers in Terms of t-topos) 229 Goro Kato The Dissipative Quantum Model of Brain and Laboratory Observations 233 Walter J. Freeman and Giuseppe Vitiello Supersymmetric Methods in the Traveling Variable: Inside Neurons and at the Brain Scale 253 H.C. Rosu, O. Cornejo-Perez, and J.E. Perez-Terrazas Turing Systems: A General Model for Complex Patterns in Nature 267 R.A. Barrio Primordial Evolution in the Finitary Process Soup 297 Olof Gornerup and James P. Crutchfield Emergence of Universe from a Quantum Network 313 Paola A. Zizzi Occam's Razor Revisited: Simplicity vs. Complexity in Biology 327 Joseph P. Zbilut Order in the Nothing: Autopoiesis and the Organizational Characterization of the Living 339 Leonardo Bich and Luisa Damiano Anticipation in Biological and Cognitive Systems: The Need for a Physical Theory of Biological Organization 371 Graziano Terenzi How Uncertain is Uncertainty? 389 Tibor Vamos Archetypes, Causal Description and Creativity in Natural World 405 Leonardo Chiatti . (shrink)

This paper defends an internalist perspective of selection based on the hypothesis that considers living evolutionary units as Maxwell's demons (MD) or Zurek's Information Gathering and Using Systems (IGUS). Individuals are considered as IGUS that extract work by means of measuring and recording processes. Interactions or measurements convert uncertainty about the environment (Shannon's information, H) into internalized information in the form of a compressed record (Chaitin's algorithmic complexity, K). The requirements of the model and the limitations inherent to (...) its formalization are discussed. This approach offers an alternative view to the causes of evolutionary variations which goes beyond the classical Lamarckian-Darwinian controversy. I argue that random variations only apply near-to-equilibrium at the time organisms have attained structural closure, and that a speed up of mutation rates that facilitates the production of directed variations occurs far-from-equilibrium due to organisms' openness to the surrounding conditions. However, real organisms are located somewhere between the above two cases and thus, operate at an intermediate stage where there is a maximum efficiency of H/K conversion. In consequence, IGUS keep their autonomy and evolving capacity by compromising between external circumstances and inner constraints. This compromise is made possible by closure regulation. Likewise, this model explains why nature has favored the selection of agents capable of selectively recording a partial description of their environment. (shrink)

Brief consideration of (1) Peirce’s ‘logic of vagueness’, (2) his categories, and (3) the concepts of overdetermination and underdetermination, vagueness and generality, and inconsistency and incompleteness, along with (4) the abrogation of classical Aristotelian principles of logic, bear out the complexity of all relatively rich sign systems. Given this complexity, there is semiotic indeterminacy, which suggests sign limitations, and at the same time it promises semiotic freedom, giving rise to sign proliferation the yield of which is pluralistic, inter-relational (...) semiosis. This proliferation of signs owes its perpetual flowing change in time to the inapplicability of classical logical principles, namely Non-Contradiction and Excluded-Middle, with respect to elements of vagueness and generality in all signs. Hempel’s ‘Inductivity Paradox’ and Goodman’s ‘New Riddle of Induction’ bear out the limitation and freedom of sign making and sign taking. A concrete cultural example, the Spaniards’ world including the Virgin of Guadalupe and the Aztecs world including their Goddess, Tonantzín, are given a Hempel-Goodman interpretation to reveal the ambiguous, vague, and complex nature of intercultural sign systems, further suggesting pluralism. In fact, when taking the ‘limitativetheorems’ of Gödel, Turing, and Chaitin into account, pluralism becomes undeniable, in view of the inconsistency-incompleteness of complex systems. A model for embracing and coping with pluralism suggests itself in the form of contextualized novelty seeking relativism. This form of pluralism takes overdetermination, largely characteristic of Peirce’s Firstness, and underdetermination largely characteristic of Peirce’s Thirdness, into its embrace to reveal a global context capable of elucidating local contexts the collection of which is considerably less than that global view. The entirety of this global context is impossible to encompass, given our inevitable finitude and fallibilism. Yet, we usually manage to cope with processual pluralism, within the play of semiosis. (shrink)

If is a random sequence, then the sequence is clearly not random; however, seems to be “about half random”. L. Staiger [Kolmogorov complexity and Hausdorff dimension, Inform. and Comput. 103 159–194 and A tight upper bound on Kolmogorov complexity and uniformly optimal prediction, Theory Comput. Syst. 31 215–229] and K. Tadaki [A generalisation of Chaitin’s halting probability Ω and halting self-similar sets, Hokkaido Math. J. 31 219–253] have studied the degree of randomness of sequences or reals by (...) measuring their “degree of compression”. This line of study leads to various definitions of partial randomness. In this paper we explore some relations between these definitions. Among other results we obtain a characterisation of Σ1-dimension in terms of strong Martin-Löf ε-tests , and we show that ε-randomness for ε is different than the classical 1-randomness. (shrink)

English summary: Philosophers have sought to apply laws of order, symmetry, and harmony to the observable universe. However, the mathematical work of Gregory Chaitin has shown that complexity, defined as the total absence of symmetry and order, appears everywhere, even in numbers. Complexity thus becomes the unsurpassable limit of reason, reducing the efforts of philosophers and scientists who would propose a system of values that every human should rationally admit. French description: Pour maitriser par la pensee et, (...) - connaitre par le langage l'accablante diversite du reel, les philosophies ont suppose l'existence d'un ordre sous-jacent se manifestant dans la symetrie, l'harmonie et la simplicite. Dans leurs efforts pour elucider et enoncer des lois concises regissant les rapports entre les elements constitutifs du monde observable, les scientifiques leur ont emboite le pas. Or, des recherches recentes en mathematiques de Gregory J. Chaitin, ont fait apparaitre que la complexite, definie comme absence totale d'ordre et de symetrie, se manifeste a tous les niveaux du reel, y compris dans les nombres. Irreductiblement rebelle a l'analyse, la complexite s'erige en limite indepassable de la raison, reduisant les pretentions des scientifiques et rendant irrealisable, comme l'avait deja compris Heidegger, le projet de philosophes qui, comme Platon et Kant, voulaient proposer un systeme de valeurs que tout etre humain devait rationnellement admettre. (shrink)

Review of "Exploring Randomness" (200) and "The Unknowable" (1999) by Gregory Chaitin.

In this article, I study Richard’s paradox, and I consider several of its solutions. I then restate the paradox using Kolmogorov’s theory of complexity. Taking as a starting point Chaitin’s demonstration that Kolmogorov’s understanding of «complexity» is only relative, I put forth a new solution to the paradox.

As a natural example of a 1-random real, Chaitin proposed the halting probability Ω of a universal prefix-free machine. We can relativize this example by considering a universal prefix-free oracle machine U. Let [Formula: see text] be the halting probability of UA; this gives a natural uniform way of producing an A-random real for every A ∈ 2ω. It is this operator which is our primary object of study. We can draw an analogy between the jump operator from computability (...) theory and this Omega operator. But unlike the jump, which is invariant under the choice of an effective enumeration of the partial computable functions, [Formula: see text] can be vastly different for different choices of U. Even for a fixed U, there are oracles A =* B such that [Formula: see text] and [Formula: see text] are 1-random relative to each other. We prove this and many other interesting properties of Omega operators. We investigate these operators from the perspective of analysis, computability theory, and of course, algorithmic randomness. (shrink)

We present a new method for expressing Chaitin’s random real, Ω, through Diophantine equations. Where Chaitin’s method causes a particular quantity to express the bits of Ω by fluctuating between finite and infinite values, in our method this quantity is always finite and the bits of Ω are expressed in its fluctuations between odd and even values, allowing for some interesting developments. We then use exponential Diophantine equations to simplify this result and finally show how both methods can (...) also be used to create polynomials which express the bits of Ω in the number of positive values they assume. (shrink)

This essay presents arguments for the claim that in the best of all possible worlds (Leibniz) there are sources of unpredictability and creativity for us humans, even given a pancomputational stance. A suggested answer to Chaitin’s questions: “Where do new mathematical and biological ideas come from? How do they emerge?” is that they come from the world and emerge from basic physical (computational) laws. For humans as a tiny subset of the universe, a part of the new ideas comes (...) as the result of the re-configuration and reshaping of already existing elements and another part comes from the outside as a consequence of openness and interactivity of the system. For the universe at large it is randomness that is the source of unpredictability on the fundamental level. In order to be able to completely predict the Universe-computer we would need the Universe-computer itself to compute its next state; as Chaitin already demonstrated there are incompressible truths which means truths that cannot be computed by any other computer but the universe itself. (shrink)

This essay presents arguments for the claim that in the best of all possible worlds (Leibniz) there are sources of unpredictability and creativity for us humans, even given a pancomputational stance. A suggested answer to Chaitin’s questions: “Where do new mathematical and biological ideas come from? How do they emerge?” is that they come from the world and emerge from basic physical (computational) laws. For humans as a tiny subset of the universe, a part of the new ideas comes (...) as the result of the re-configuration and reshaping of already existing elements and another part comes from the outside world as a consequence of openness and interactivity of biological and cognitive systems. For the universe at large it is randomness that is the source of unpredictability on the fundamental level. In order to be able to completely predict the Universe-computer we would need the Universe-computer itself to compute its next state. As Chaitin demonstrated there are incompressible truths, which means truths that cannot be computed by any other computer but the universe itself. (shrink)

We prove that the continuous function${\rm{\hat \Omega }}:2^\omega \to $ that is defined via$X \mapsto \mathop \sum \limits_n 2^{ - K\left} $ for all $X \in {2^\omega }$ is differentiable exactly at the Martin-Löf random reals with the derivative having value 0; that it is nowhere monotonic; and that $\mathop \smallint \nolimits _0^1{\rm{\hat{\Omega }}}\left\,{\rm{d}}X$ is a left-c.e. $wtt$-complete real having effective Hausdorff dimension ${1 / 2}$.We further investigate the algorithmic properties of ${\rm{\hat{\Omega }}}$. For example, we show that the maximal (...) value of ${\rm{\hat{\Omega }}}$ must be random, the minimal value must be Turing complete, and that ${\rm{\hat{\Omega }}}\left \oplus X{ \ge _T}\emptyset \prime$ for every X. We also obtain some machine-dependent results, including that for every $\varepsilon > 0$, there is a universal machine V such that ${{\rm{\hat{\Omega }}}_V}$ maps every real X having effective Hausdorff dimension greater than ε to a real of effective Hausdorff dimension 0 with the property that $X{ \le _{tt}}{{\rm{\hat{\Omega }}}_V}\left$; and that there is a real X and a universal machine V such that ${{\rm{\Omega }}_V}\left$ is rational. (shrink)

(1991). Gödel, Turing, chaitin and the question of emergence as a meta‐principle of modern physics. some arguments against reductionism. World Futures: Vol. 32, Creative Evolution in Nature, Mind, and Society, pp. 185-195.