A set $B\subseteq\mathbb{N}$ is called low for Martin-Löf random if every Martin-Löf random set is also Martin-Löf random relative to B . We show that a $\Delta^0_2$ set B is low for Martin-Löf random if and only if the class of oracles which compress less efficiently than B , namely, the class $\mathcal{C}^B=\{A\ |\ \forall n\ K^B(n)\leq^+ K^A(n)\}$ is countable (where K denotes the prefix-free complexity and $\leq^+$ denotes inequality modulo a constant. It follows that $\Delta^0_2$ is the largest arithmetical (...) class with this property and if $\mathcal{C}^B$ is uncountable, it contains a perfect $\Pi^0_1$ set of reals. The proof introduces a new method for constructing nontrivial reals below a $\Delta^0_2$ set which is not low for Martin-Löf random. (shrink)

Does Nature permit the implementation of behaviours that cannot be simulated computationally? We consider the meaning of physical computation in some detail, and present arguments in favour of physical hypercomputation: for example, modern scientific method does not allow the specification of any experiment capable of refuting hypercomputation. We consider the implications of relativistic algorithms capable of solving the (Turing) Halting Problem. We also reject as a fallacy the argument that hypercomputation has no relevance because non-computable values are indistinguishable from sufficiently (...) close computable approximations. In addition to considering the nature of computability relative to any given physical theory, we can consider the relationship between versions of computability corresponding to different models of physics. Deutsch and Penrose have argued on mathematical grounds that quantum computation and Turing computation have equivalent formal power. We suggest this equivalence is invalid when considered from the physical point of view, by highlighting a quantum computational behaviour that cannot meaningfully be considered feasible in the classical universe. (shrink)

The reference class problem arises when we want to assign a probability to a proposition (or sentence, or event) X, which may be classified in various ways, yet its probability can change depending on how it is classified. The problem is usually regarded as one specifically for the frequentist interpretation of probability and is often considered fatal to it. I argue that versions of the classical, logical, propensity and subjectivist interpretations also fall prey to their own variants of the reference (...) class problem. Other versions of these interpretations apparently evade the problem. But I contend that they are all “no-theory” theories of probability - accounts that leave quite obscure why probability should function as a guide to life, a suitable basis for rational inference and action. The reference class problem besets those theories that are genuinely informative and that plausibly constrain our inductive reasonings and decisions. I distinguish a “metaphysical” and an “epistemological” reference class problem. I submit that we can dissolve the former problem by recognizing that probability is fundamentally a two-place notion: conditional probability is the proper primitive of probability theory. However, I concede that the epistemological problem remains. (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)

This paper offers an account of what it is for a physical system to be a computing mechanism—a system that performs computations. A computing mechanism is a mechanism whose function is to generate output strings from input strings and (possibly) internal states, in accordance with a general rule that applies to all relevant strings and depends on the input strings and (possibly) internal states for its application. This account is motivated by reasons endogenous to the philosophy of computing, namely, doing (...) justice to the practices of computer scientists and computability theorists. It is also an application of recent literature on mechanisms, because it assimilates computational explanation to mechanistic explanation. The account can be used to individuate computing mechanisms and the functions they compute and to taxonomize computing mechanisms based on their computing power. (shrink)

Hájek (Erkenntnis 70(2):211–235, 2009) argues that probabilities cannot be the limits of relative frequencies in counterfactual infinite sequences. I argue for a different understanding of these limits, drawing on Norton’s (Philos Sci 79(2):207–232, 2012) distinction between approximations (inexact descriptions of a target) and idealizations (separate models that bear analogies to the target). Then, I adapt Hájek’s arguments to this new context. These arguments provide excellent reasons not to use hypothetical frequencies as idealizations, but no reason not to use them as (...) approximations. (shrink)

Although the formalizations of computability provided in the 1930s have proven to be equivalent, two different accounts of computability may be distinguished regarding computability as an epistemic concept. While computability, according to the epistemic account, should be based on epistemic constraints related to the capacities of human computers, the non-epistemic account considers computability as based on manipulations of symbols that require no human capacities other than the capacity of manipulating symbols according to a set of rules. In this paper, I (...) shall evaluate, both from a logical and physical point of view, whether computability should be regarded as an epistemic concept, i.e., whether epistemic constraints should be added on computability for considering functions as computable. Specifically, I shall argue that the introduction of epistemic constraints have deep implications for the set of computable functions, for the logical and physical Church-Turing thesis—cornerstones of logical and physical computability respectively—might turn out to be false according to which epistemic constraints are accepted. (shrink)

Just as theory of representation is deficient if it can’t explain how misrepresentation is possible, a theory of computation is deficient if it can’t explain how miscomputation is possible. Nonetheless, philosophers have generally ignored miscomputation. My primary goal in this paper is to clarify both what miscomputation is and how to adequately explain it. Miscomputation is a special kind of malfunction: a system miscomputes when it computes in a way that it shouldn’t. To explain miscomputation, you must provide accounts of (...) computational behavior, computational norms, and how computational behavior can deviate from computational norms. A secondary goal of this paper is to defend an (quasi-)individualist, mechanistic theory of miscomputation. Computational behavior is narrowly individuated. Computational norms are widely individuated. A system miscomputes when its behavior manifests a narrow computational structure that the widely individuated norms say that it should not have. (shrink)

Hans Reichenbach is well known for his limiting frequency view of probability, with his most thorough account given in The Theory of Probability in 1935/1949. Perhaps less known are Reichenbach's early views on probability and its epistemology. In his doctoral thesis from 1915, Reichenbach espouses a Kantian view of probability, where the convergence limit of an empirical frequency distribution is guaranteed to exist thanks to the synthetic a priori principle of lawful distribution. Reichenbach claims to have given a purely objective (...) account of probability, while integrating the concept into a more general philosophical and epistemological framework. A brief synopsis of Reichenbach's thesis and a critical analysis of the problematic steps of his argument will show that the roots of many of his most influential insights on probability and causality can be found in this early work. (shrink)

This is the sequel to my “Fifteen Arguments Against Finite Frequentism” ( Erkenntnis 1997), the second half of a long paper that attacks the two main forms of frequentism about probability. Hypothetical frequentism asserts: The probability of an attribute A in a reference class B is p iff the limit of the relative frequency of A ’s among the B ’s would be p if there were an infinite sequence of B ’s. I offer fifteen arguments against this analysis. I (...) consider various frequentist responses, which I argue ultimately fail. I end with a positive proposal of my own, ‘hyper-hypothetical frequentism’, which I argue avoids several of the problems with hypothetical frequentism. It identifies probability with relative frequency in a hyperfinite sequence of trials. However, I argue that this account also fails, and that the prospects for frequentism are dim. (shrink)

My dissertation explores the ways in which Rudolf Carnap sought to make philosophy scientific by further developing recent interpretive efforts to explain Carnap’s mature philosophical work as a form of engineering. It does this by looking in detail at his philosophical practice in his most sustained mature project, his work on pure and applied inductive logic. I, first, specify the sort of engineering Carnap is engaged in as involving an engineering design problem and then draw out the complications of design (...) problems from current work in history of engineering and technology studies. I then model Carnap’s practice based on those lessons and uncover ways in which Carnap’s technical work in inductive logic takes some of these lessons on board. This shows ways in which Carnap’s philosophical project subtly changes right through his late work on induction, providing an important corrective to interpretations that ignore the work on inductive logic. Specifically, I show that paying attention to the historical details of Carnap’s attempt to apply his work in inductive logic to decision theory and theoretical statistics in the 1950s and 1960s helps us understand how Carnap develops and rearticulates the philosophical point of the practical/theoretical distinction in his late work, offering thus a new interpretation of Carnap’s technical work within the broader context of philosophy of science and analytical philosophy in general. (shrink)

This is the most comprehensive book ever published on philosophical methodology. A team of thirty-eight of the world's leading philosophers present original essays on various aspects of how philosophy should be and is done. The first part is devoted to broad traditions and approaches to philosophical methodology. The entries in the second part address topics in philosophical methodology, such as intuitions, conceptual analysis, and transcendental arguments. The third part of the book is devoted to essays about the interconnections between philosophy (...) and neighbouring fields, including those of mathematics, psychology, literature and film, and neuroscience. (shrink)

An early, very preliminary edition of this book was circulated in 1962 under the title Set-theoretical Structures in Science. There are many reasons for maintaining that such structures play a role in the philosophy of science. Perhaps the best is that they provide the right setting for investigating problems of representation and invariance in any systematic part of science, past or present. Examples are easy to cite. Sophisticated analysis of the nature of representation in perception is to be found already (...) in Plato and Aristotle. One of the great intellectual triumphs of the nineteenth century was the mechanical explanation of such familiar concepts as temperature and pressure by their representation in terms of the motion of particles. A more disturbing change of viewpoint was the realization at the beginning of the twentieth century that the separate invariant properties of space and time must be replaced by the space-time invariants of Einstein's special relativity. Another example, the focus of the longest chapter in this book, is controversy extending over several centuries on the proper representation of probability. The six major positions on this question are critically examined. Topics covered in other chapters include an unusually detailed treatment of theoretical and experimental work on visual space, the two senses of invariance represented by weak and strong reversibility of causal processes, and the representation of hidden variables in quantum mechanics. The final chapter concentrates on different kinds of representations of language, concluding with some empirical results on brain-wave representations of words and sentences. (shrink)

For over a decade, the hypercomputation movement has produced computational models that in theory solve the algorithmically unsolvable, but they are not physically realizable according to currently accepted physical theories. While opponents to the hypercomputation movement provide arguments against the physical realizability of specific models in order to demonstrate this, these arguments lack the generality to be a satisfactory justification against the construction of any information-processing machine that computes beyond the universal Turing machine. To this end, I present a more (...) mathematically concrete challenge to hypercomputability, and will show that one is immediately led into physical impossibilities, thereby demonstrating the infeasibility of hypercomputers more generally. This gives impetus to propose and justify a more plausible starting point for an extension to the classical paradigm that is physically possible, at least in principle. Instead of attempting to rely on infinities such as idealized limits of infinite time or numerical precision, or some other physically unattainable source, one should focus on extending the classical paradigm to better encapsulate modern computational problems that are not well-expressed/modeled by the closed-system paradigm of the Turing machine. I present the first steps toward this goal by considering contemporary computational problems dealing with intractability and issues surrounding cyber-physical systems, and argue that a reasonable extension to the classical paradigm should focus on these issues in order to be practically viable. (shrink)

Olszewski claims that the Church-Turing thesis can be used in an argument against platonism in philosophy of mathematics. The key step of his argument employs an example of a supposedly effectively computable but not Turing-computable function. I argue that the process he describes is not an effective computation, and that the argument relies on the illegitimate conflation of effective computability with there being a way to find out . ‘Ah, but,’ you say, ‘what’s the use of its being right twice (...) a day, if I can’t tell when the time comes?’ Why, suppose the clock points to eight o’clock, don’t you see that the clock is right at eight o’clock? Consequently, when eight o’clock comes round your clock is right. Lewis Carroll. (shrink)

The investigation of probabilistic causality has been plagued by a variety of misconceptions and misunderstandings. One has been the thought that the aim of the probabilistic account of causality is the reduction of causal claims to probabilistic claims. Nancy Cartwright (1979) has clearly rebutted that idea. Another ill-conceived idea continues to haunt the debate, namely the idea that contextual unanimity can do the work of objective homogeneity. It cannot. We argue that only objective homogeneity in combination with a causal interpretation (...) of Bayesian networks can provide the desired criterion of probabilistic causality. (shrink)

In October 2009 I decided to stop doing philosophy. This meant, in particular, stopping work on the book that I was writing on the nature of probability. At that time, I had no intention of making my unfinished draft available to others. However, I recently noticed how many people are reading the lecture notes and articles on my web site. Since this draft book contains some important improvements on those materials, I decided to make it available to anyone who wants (...) to read it. That is what you have in front of you. The account of Laplace’s theory of probability in Chapter 4 is very different to what I said in my seminar lectures, and also very different to any other account I have seen; it is based on a reading of important texts by Laplace that appear not to have been read by other commentators. The discussion of von Mises’ theory in Chapter 7 is also new, though perhaps less revolutionary. And the final chapter is a new attempt to come to grips with the popular, but amorphous, subjective theory of probability. The material in the other chapters has mostly appeared in previous articles of mine but things are sometimes expressed differently here. I would like to say again that this is an incomplete draft of a book, not the book I would have written if I had decided to finish it. It no doubt contains poor expressions, it may contain some errors or inconsistencies, and it doesn’t cover all the theories that I originally intended to discuss. Apart from this preface, I have done no work on the book since October 2009. (shrink)

The main objective of the paper is to propose a frequentist interpretation of probability in the context of model-based induction, anchored on the Strong Law of Large Numbers (SLLN) and justifiable on empirical grounds. It is argued that the prevailing views in philosophy of science concerning induction and the frequentist interpretation of probability are unduly influenced by enumerative induction, and the von Mises rendering, both of which are at odds with frequentist model-based induction that dominates current practice. The differences between (...) the two perspectives are brought out with a view to defend the model-based frequentist interpretation of probability against certain well-known charges, including [i] the circularity of its definition, [ii] its inability to assign ‘single event’ probabilities, and [iii] its reliance on ‘random samples’. It is argued that charges [i]–[ii] stem from misidentifying the frequentist ‘long-run’ with the von Mises collective. In contrast, the defining characteristic of the long-run metaphor associated with model-based induction is neither its temporal nor its physical dimension, but its repeatability (in principle); an attribute that renders it operational in practice. It is also argued that the notion of a statistical model can easily accommodate non-IID samples, rendering charge [iii] simply misinformed. (shrink)

This article explores the connection between objective chance and the randomness of a sequence of outcomes. Discussion is focussed around the claim that something happens by chance iff it is random. This claim is subject to many objections. Attempts to save it by providing alternative theories of chance and randomness, involving indeterminism, unpredictability, and reductionism about chance, are canvassed. The article is largely expository, with particular attention being paid to the details of algorithmic randomness, a topic relatively unfamiliar to philosophers.

What are the limits of physical computation? In his ‘Church’s Thesis and Principles for Mechanisms’, Turing’s student Robin Gandy proved that any machine satisfying four idealised physical ‘principles’ is equivalent to some Turing machine. Gandy’s four principles in effect define a class of computing machines (‘Gandy machines’). Our question is: What is the relationship of this class to the class of all (ideal) physical computing machines? Gandy himself suggests that the relationship is identity. We do not share this view. We (...) will point to interesting examples of (ideal) physical machines that fall outside the class of Gandy machines and compute functions that are not Turing-machine computable. (shrink)

This chapter contains sections titled: Highlights of Past Literature Current Work Future Work.

My title is intended to recall Terence Fine's excellent survey, Theories of Probability [1973]. I shall consider some developments that have occurred in the intervening years, and try to place some of the theories he discussed in what is now a slightly longer perspective. Completeness is not something one can reasonably hope to achieve in a journal article, and any selection is bound to reflect a view of what is salient. In a subject as prone to dispute as this, there (...) will inevitably be many who will disagree with any author's views, and I take the opportunity to apologize in advance to all such people for what they will see as the narrowness and distortion of mine. (shrink)

A pure significance test would check the agreement of a statistical model with the observed data even when no alternative model was available. The paper proposes the use of a modified p -value to make such a test. The model will be rejected if something surprising is observed. It is shown that the relation between this measure of surprise and the surprise indices of Weaver and Good is similar to the relationship between a p -value, a corresponding odds-ratio, and a (...) logit or log-odds statistic. The s -value is always larger than the corresponding p -value, and is not uniformly distributed. Difficulties with the whole approach are discussed. (shrink)

Theoria , the international Swedish philosophy journal, was founded in 1935. Its contributors in the first 75 years include the major Swedish philosophers from this period and in addition a long list of international philosophers, including A. J. Ayer, C. D. Broad, Ernst Cassirer, Hector Neri Castañeda, Arthur C. Danto, Donald Davidson, Nelson Goodman, R. M. Hare, Carl G. Hempel, Jaakko Hintikka, Saul Kripke, Henry E. Kyburg, Keith Lehrer, Isaac Levi, David Lewis, Gerald MacCallum, Richard Montague, Otto Neurath, Arthur N. (...) Prior, W. V. Quine, Nicholas Rescher, Ernest Sosa, Robert C. Stalnaker, P. F. Strawson, Patrick Suppes, Johan van Benthem, Georg Henrik von Wright and many others. Hempel's confirmation paradoxes, Ross's deontic paradox, Montague's universal grammar and Lindström's theorem are among the contributions to philosophy that were first published in Theoria. (shrink)

“Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.”1 John von Neumann’s famous dictum points an accusing finger at all who set their ordered minds to engender disorder. Much as in times past thieves, pimps, and actors carried on their profession with an uneasy conscience, so in this day scientists who devise random number generators suffer pangs of guilt. George Marsaglia, perhaps the preeminent worker in the field, quips when he asks his (...) colleagues, “Who among us has not sinned?” Marsaglia’s work at the Supercomputer Computations Research Institute at Florida State University is well-known. Inasmuch as Marsaglia’s design and testing of random number generators depends on computation, and inasmuch as computation is fundamentally arithmetical, Marsaglia is by von Neumann’s own account a sinner. Working as he does on a supercomputer, Marsaglia is in fact a gross sinner. This he freely admits. Writing of the best random number generators he is aware of, Marsaglia states, “they are the result of arithmetic methods and those using them must, as all sinners must, face Redemption [sic] Day. But perhaps with better understanding we can postpone it.”. (shrink)

We consider the meaning of the assignment of probabilities to events implied by the kind of model regularly used by Statisticians. Traditional frequentist understandings are reviewed and rejected. It is argued that many statistical models may be justified purely on the basis of the symmetry properties enjoyed by the observables being modelled.

We survey a variety of possible explications of the term “Individual Risk.” These in turn are based on a variety of interpretations of “Probability,” including classical, enumerative, frequency, formal, metaphysical, personal, propensity, chance and logical conceptions of probability, which we review and compare. We distinguish between “groupist” and “individualist” understandings of probability, and explore both “group to individual” and “individual to group” approaches to characterising individual risk. Although in the end that concept remains subtle and elusive, some pragmatic suggestions for (...) progress are made. (shrink)

A survey of the field of hypercomputation, including discussion of a variety of objections.

In 1866, the young John Venn published The Logic of Chance, motivated largely by the desire to correct what he saw as deep fallacies in the reasoning of historical determinists such as Henry Buckle and in the optimistic heralding of a true social science by Adolphe Quetelet. Venn accepted the inevitable determinism implied by the physical sciences, but denied that the stable social statistics cited by Buckle and Quetelet implied a similar determinism in human actions. Venn maintained that probability statements (...) were intelligible solely as projections of the ultimate frequency of an outcome in an unlimited series of trials and therefore led to no inferences about free will. An issue here was Venn's claim that although the aggregate probability may be stable, the individual events were completely irregular and, in fact, displayed randomness. Venn's concept of randomness was really apparent, or pseudo-, randomness, which could be totally determined. Ironically, Venn's frequentist position was very useful to the growing field of statistics, which could develop correlations and predictive models empirically without having to address implications for personal freedom or fatalism. (shrink)

To clarify and illuminate the place of probability in science Ellery Eells and James H. Fetzer have brought together some of the most distinguished philosophers ...

Randomness, a core concept of gambling, is seen in problem gambling as responsible for the formation of the math-related cognitive distortions, especially the Gambler’s Fallacy. In problem-gambling research, the concept of randomness was traditionally referred to as having a mathematical nature and categorized and approached as such. Randomness is not a mathematical concept, and I argue that its weak mathematical dimension is not decisive at all for the randomness-related issues in gambling and problem gambling, including the correction of the misconceptions (...) and fallacies about probability and statistical concepts applied in gambling. I distinguish between mathematical and nonmathematical dimensions of randomness (the epistemic, the theoretical-methodological, the functional, and the ethical) falling within the general concept, and I argue that both the studies having as object the math-related cognitive distortions among gamblers and the educational programs aiming at correcting them should employ this distinction in their design and content. (shrink)