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)

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 ...

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 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)

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)

We study the sets that are computable from both halves of some (Martin–Löf) random sequence, which we call 1/2-bases. We show that the collection of such sets forms an ideal in the Turing degrees that is generated by its c.e. elements. It is a proper subideal of the K-trivial sets. We characterize 1/2-bases as the sets computable from both halves of Chaitin’s Ω, and as the sets that obey the cost function c(x,s)=Ωs−Ωx−−−−−−−√. Generalizing these results yields a dense hierarchy of (...) subideals in the K-trivial degrees: For k<n, let Bk/n be the collection of sets that are below any k out of n columns of some random sequence. As before, this is an ideal generated by its c.e. elements and the random sequence in the definition can always be taken to be Ω. Furthermore, the corresponding cost function characterization reveals that Bk/n is independent of the particular representation of the rational k/n, and that Bp is properly contained in Bq for rational numbers p<q. These results are proved using a generalization of the Loomis–Whitney inequality, which bounds the measure of an open set in terms of the measures of its projections. The generality allows us to analyze arbitrary families of orthogonal projections. As it turns out, these do not give us new subideals of the K-trivial sets; we can calculate from the family which Bp it characterizes. We finish by studying the union of Bp for p<1; we prove that this ideal consists of the sets that are robustly computable from some random sequence. This class was previously studied by Hirschfeldt [D. R. Hirschfeldt, C. G. Jockusch, R. Kuyper and P. E. Schupp, Coarse reducibility and algorithmic randomness, J. Symbolic Logic81(3) (2016) 1028–1046], who showed that it is a proper subclass of the K-trivial sets. We prove that all such sets are robustly computable from Ω, and that they form a proper subideal of the sets computable from every (weakly) LR-hard random sequence. We also show that the ideal cannot be characterized by a cost function, giving the first such example of a Σ03 subideal of the K-trivial sets. (shrink)

We present an abstract framework in which we give simple proofs for Gödel’s First and Second Incompleteness Theorems and obtain, as consequences, Davis’, Chaitin’s and Kritchman-Raz’s Theorems.

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)

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)

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)

Gödel's first incompleteness theorem shows that no axiomatic theory can prove all mathematical truths, while Gödel's second incompleteness theorem shows that a specific mathematical result is unprovable. A famous mathematician of the time, David Hilbert, had asked for a proof that an important axiomatic theory was consistent, and Godel showed that such a proof could not be carried out within the axiomatic theory itself, and presumably could therefore not be established in a convincing way outside of the theory either.

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)

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.

This is a defense and extension of Stephen Yablo's claim that self-reference is completely inessential to the liar paradox. An infinite sequence of sentences of the form 'None of these subsequent sentences are true' generates the same instability in assigning truth values. I argue Yablo's technique of substituting infinity for self-reference applies to all so-called 'self-referential' paradoxes. A representative sample is provided which includes counterparts of the preface paradox, Pseudo-Scotus's validity paradox, the Knower, and other enigmas of the genre. I (...) rebut objections that Yablo's paradox is not a genuine liar by constructing a sequence of liars that blend into Yablo's paradox. I rebut objections that Yablo's liar has hidden self-reference with a distinction between attributive and referential self-reference and appeals to Gregory Chaitin's algorithmic information theory. The paper concludes with comments on the mystique of self-reference. (shrink)

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

"A person is not explainable in molecular, field-theoretical, or physiological terms alone." With that declaration, Nobel laureate Gerald M. Edelman goes straight to the heart of Nature's Imagination, a vibrant and important collection of essays by some of the world's foremost scientists. Ever since the Enlightenment, the authors write, science has pursued reductionism: the idea that the whole can be understood by examining and explaining each of its parts. But as this book shows, scientists in every discipline are reaching for (...) a new paradigm that accounts for the whole--from the individual person to the universe itself. Nature's Imagination gathers together the work of thirteen leading mathematicians, astronomers, neuroscientists, and philosophers, as they discuss the revolution sweeping the sciences. Here Roger Penrose, Oliver Sacks, John Barrow, Gregory Chaitin, Maragret Boden, and others explore how and why classic reductionism is falling by the wayside in their own fields. As Freeman Dyson writes in the introduction, science is an art form, not a philosophical method, and it is always in search of new tools. Reductionism has done its work, and scientists are in search of another. Roger Penrose offers a fascinating account of irreducibility in mathematics, starting with the example of an impossible triangle--a drawing of a triangular object twisted so that could not exist in three dimensions. He breaks the triangle into three parts, showing that each corner is physically possible; only in combination is the triangle impossible. Both Penrose and mathematician Gregory Chaitin explore Godel's incompleteness theorem--as does John Barrow, who explains that Chaitin's proof of the theorem shows that, if we ever arrive at a Theory of Everything, there may be a still deeper and simpler unifying theory beyond that. Other contributors discuss the changing thinking in neuroscience, and the limitations of a mechanical view of the mind: as Oliver Sacks writes, "if we are to have a model or theory of mind as this actually occurs in living creatures in the world, it may have to be radically different from anything like a computational one." In addition, this volume includes staunch defenders of the classic scientific approach, such as Peter Atkins ("The omnicompetence of science, and in particular the simplicity its reductionist insight reveals, should be accepted as a working hypothesis until, if ever, it is proved inadequate"). The advance of science has been so startlingly swift in the last century that it has begun to approach limits never dreamed of before. This remarkable volume captures the latest thinking on where we must turn if we are to truly understand oursevles and the universe we live in. (shrink)

The proofs of Gödel (1931), Rosser (1936), Kleene (first 1936 and second 1950), Chaitin (1970), and Boolos (1989) for the first incompleteness theorem are compared with each other, especially from the viewpoint of the second incompleteness theorem. It is shown that Gödel’s (first incompleteness theorem) and Kleene’s first theorems are equivalent with the second incompleteness theorem, Rosser’s and Kleene’s second theorems do deliver the second incompleteness theorem, and Boolos’ theorem is derived from the second incompleteness theorem in the standard way. (...) It is also shown that none of Rosser’s, Kleene’s second or Boolos’ theorems is equivalent with the second incompleteness theorem, and Chaitin’s incompleteness theorem neither delivers nor is derived from the second incompleteness theorem. We compare (the strength of) these six proofs with one another. (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)

The question that this paper tries to answer is Q: “Can good academic bioethics be done without commitment to moral theory?” It is argued that the answer to Q is an unequivocal “Yes” for most of what we could call “critical bioethics,” that is, the kind of bioethics work that primarily criticizes positions or arguments already in the literature or put forward by policymakers. The answer is also “Yes” for much of empirical bioethics. The second part of the paper then (...) provides an analysis of Q in relation to “constructive bioethics,” that is, bioethics work aimed at providing an argument for a particular position. In this part, it is argued that a number of the approaches or methods used that initially look like they involve no commitment to moral theory, nevertheless, involve such a commitment. This is shown to be the case for reflective equilibrium, mid-level theory, the use of theory fragments, and argument by analogy. (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)

In this book, S. A. Lloyd offers a radically new interpretation of Hobbes's laws of nature, revealing them to be not egoistic precepts of personal prudence but rather moral instructions for obtaining the common good.

The status quo: dogmatism, the biopsychosocial model, and alternatives -- What there is: of mind and brain -- How we know: understanding the mind -- What is scientific method? -- Reading Karl Jaspers's General Psychopathology -- What is scientific method in psychiatry? -- Darwin's dangerous method: the essentialist fallacy -- What we value: the ethics of psychiatry -- Desire and self: Hellenistic and Islamic approaches -- On the nature of mental illness: disease or myth? -- Order out of chaos: from (...) insanity to DSM-III to a pluralistic nosology -- A theory of DSM-IV: ideal types -- Dimensions versus categories -- The perils of belief: psychosis -- The slings and arrows of outrageous fortune: depression -- Life's rollercoaster: mania -- Being self-aware: insight -- Calvinism or hedonism? -- Truth and statistics: problems of empirical psychiatry -- A climate of opinion: what remains of psychoanalysis -- Being there: existential psychotherapy -- Beyond eclecticism: teaching psychotherapy in the twenty-first century -- Bridging the biology/psychology dichotomy: the hopes of integrationism -- Why it is hard to be pluralist. (shrink)