Algorithmic Complexity

We consider two ways one might use algorithmic randomness to characterize a probabilistic law. The first is a generative chance* law. Such laws involve a nonstandard notion of chance. The second is a probabilistic* constraining law. Such laws impose relative frequency and randomness constraints that every physically possible world must satisfy. While each notion has virtues, we argue that the latter has advantages over the former. It supports a unified governing account of non-Humean laws and provides independently motivated solutions to (...) issues in the Humean best-system account. On both notions, we have a much tighter connection between probabilistic laws and their corresponding sets of possible worlds. Certain histories permitted by traditional probabilistic laws are ruled out as physically impossible. As a result, such laws avoid one variety of empirical underdetermination, but the approach reveals other varieties of underdetermination that are typically overlooked. (shrink)

Given functionally equivalent minds, how does the expected quantity of their conscious experience differ across different substrates and how could we calculate this? We argue that a realistic digital brain emulation would be orders of magnitude less conscious than a real biological brain. On the other hand, a mind running on neuromorphic hardware or a quantum computer could in principle be more conscious than than a biological brain.

The framework of Solomonoff prediction assigns prior probability to hypotheses inversely proportional to their Kolmogorov complexity. There are two well-known problems. First, the Solomonoff prior is relative to a choice of Universal Turing machine. Second, the Solomonoff prior is not computable. However, there are responses to both problems. Different Solomonoff priors converge with more and more data. Further, there are computable approximations to the Solomonoff prior. I argue that there is a tension between these two responses. This is because computable (...) approximations to Solomonoff prediction do not always converge. (shrink)

A "patternist" approach to explanation seeks to formalize unificationism using notions from algorithmic information theory. Among other advantages, this account provides both a rigorous sense of how data can admit multiple explanations, and a rigorous sense of how some of those explanations can conjoin, while others compete.

While scientific inquiry crucially relies on the extraction of patterns from data, we still have a far from perfect understanding of the metaphysics of patterns—and, in particular, of what makes a pattern real. In this paper we derive a criterion of real-patternhood from the notion of conditional Kolmogorov complexity. The resulting account belongs to the philosophical tradition, initiated by Dennett :27–51, 1991), that links real-patternhood to data compressibility, but is simpler and formally more perspicuous than other proposals previously defended in (...) the literature. It also successfully enforces a non-redundancy principle, suggested by Ladyman and Ross, that aims to exclude from real-patternhood those patterns that can be ignored without loss of information about the target dataset, and which their own account fails to enforce. (shrink)

Bedau's influential (1997) account analyzes weak emergence in terms of the non-derivability of a system’s macrostates from its microstates except by simulation. I offer an improved version of Bedau’s account of weak emergence in light of insights from information theory. Non-derivability alone does not guarantee that a system’s macrostates are weakly emergent. Rather, it is non-derivability plus the algorithmic compressibility of the system’s macrostates that makes them weakly emergent. I argue that the resulting information-theoretic picture provides a metaphysical account of (...) weak emergence rather than a merely epistemic one. (shrink)

I argue for patternism, a new answer to the question of when some objects compose a whole. None of the standard principles of composition comfortably capture our natural judgments, such as that my cat exists and my table exists, but there is nothing wholly composed of them. Patternism holds, very roughly, that some things compose a whole whenever together they form a “real pattern”. Plausibly we are inclined to acknowledge the existence of my cat and my table but not of (...) their fusion, because the first two have a kind of internal organizational coherence that their putative fusion lacks. Kolmogorov complexity theory supplies the needed rigorous sense of “internal organizational coherence”. (shrink)

Early work on the frequency theory of probability made extensive use of the notion of randomness, conceived of as a property possessed by disorderly collections of outcomes. Growing out of this work, a rich mathematical literature on algorithmic randomness and Kolmogorov complexity developed through the twentieth century, but largely lost contact with the philosophical literature on physical probability. The present chapter begins with a clarification of the notions of randomness and probability, conceiving of the former as a property of a (...) sequence of outcomes, and the latter as a property of the process generating those outcomes. A discussion follows of the nature and limits of the relationship between the two notions, with largely negative verdicts on the prospects for any reduction of one to the other, although the existence of an apparently random sequence of outcomes is good evidence for the involvement of a genuinely chancy process. (shrink)

Applying the concepts of Kolmogorov-Chaitin complexity and Turing’s uncomputability from the computability and algorithmic information theories to the irreducible and incomputable randomness of quantum mechanics, a novel argument for the existence of God is presented. Concepts of ‘transintelligence’ and ‘transcausality’ are introduced, and from them, it is posited that our universe must be epistemologically and ontologically an open universe. The proposed idea also proffers a new perspective on the nonlocal nature and the infamous wave-function-collapse problem of quantum mechanics.

There are writers in both metaphysics and algorithmic information theory (AIT) who seem to think that the latter could provide a formal theory of the former. This paper is intended as a step in that direction. It demonstrates how AIT might be used to define basic metaphysical notions such as *object* and *property* for a simple, idealized world. The extent to which these definitions capture intuitions about the metaphysics of the simple world, times the extent to which we think the (...) simple world is analogous to our own, will determine a lower bound for basing a metaphysics for *our* world on AIT. (shrink)

The concept of randomness has been unjustly neglected in recent philosophical literature, and when philosophers have thought about it, they have usually acquiesced in views about the concept that are fundamentally flawed. After indicating the ways in which these accounts are flawed, I propose that randomness is to be understood as a special case of the epistemic concept of the unpredictability of a process. This proposal arguably captures the intuitive desiderata for the concept of randomness; at least it should suggest (...) that the commonly accepted accounts cannot be the whole story and more philosophical attention needs to be paid. 1. Randomness in science1.1Random systems1.2Random behaviour1.3Random sampling1.4Caprice, arbitrariness and noise2. Concepts of randomness2.1Von Mises/church/martin-löf randomness2.2KCS-randomness3. Randomness is unpredictability: preliminaries3.1Process and product randomness3.2Randomness is indeterminism?4. Predictability4.1Epistemic constraints on prediction4.2Computational constraints on prediction4.3Pragmatic constraints on prediction4.4Prediction defined5. Unpredictability6. Randomness is unpredictability6.1Clarification of the definition of randomness6.2Randomness and probability6.3Subjectivity and context sensitivity of randomness7. Evaluating the analysis[R]andomness … is going to be a concept which is relative to our body of knowledge, which will somehow reflect what we know and what we don't know. Henry E. Kyburg, Jr ([1974], p. 217)Phenomena that we cannot predict must be judged random. Patrick Suppes ([1984], p. 32). (shrink)

Chaitin’s incompleteness result related to random reals and the halting probability has been advertised as the ultimate and the strongest possible version of the incompleteness and undecidability theorems. It is argued that such claims are exaggerations.

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)

The simulation hypothesis has recently excited renewed interest, especially in the physics and philosophy communities. However, the hypothesis specifically concerns {computers} that simulate physical universes, which means that to properly investigate it we need to couple computer science theory with physics. Here I do this by exploiting the physical Church-Turing thesis. This allows me to introduce a preliminary investigation of some of the computer science theoretic aspects of the simulation hypothesis. In particular, building on Kleene's second recursion theorem, I prove (...) that it is mathematically possible for us to be in a simulation that is being run on a computer \textit{by us}. In such a case, there would be two identical instances of us; the question of which of those is ``really us'' is meaningless. I also show how Rice's theorem provides some interesting impossibility results concerning simulation and self-simulation; briefly describe the philosophical implications of fully homomorphic encryption for (self-)simulation; briefly investigate the graphical structure of universes simulating universes simulating universes, among other issues. I end by describing some of the possible avenues for future research that this preliminary investigation reveals. (shrink)