We prove a number of elementary facts about computability in partial combinatory algebras. We disprove a suggestion made by Kreisel about using Friedberg numberings to construct extensional pca’s. We then discuss separability and elements without total extensions. We relate this to Ershov’s notion of precompleteness, and we show that precomplete numberings are not 1–1 in general.

Transfinite recursion is an essential component of set theory. In this paper, we seek intrinsically justified reasons for believing in recursion and the notions of higher computation that surround it. In doing this, we consider several kinds of recursion principles and prove results concerning their relation to one another. We then consider philosophical motivations for these formal principles coming from the idea that computational notions lie at the core of our conception of set. This is significant because, while the iterative (...) conception of set has been widely recognized as insufficient to establish replacement and recursion, its supplementation by considerations pertaining to algorithms suggests a new and philosophically well-motivated reason to believe in such principles. (shrink)

In this paper, I evaluate the claim that the equivalence of multiple intensionally distinct definitions of random sequence provides evidence for the claim that these definitions capture the intuitive conception of randomness, concluding that the former claim is false. I then develop an alternative account of the significance of randomness-theoretic equivalence results, arguing that they are instances of a phenomenon I refer to as schematic equivalence. On my account, this alternative approach has the virtue of providing the plurality of definitions (...) of randomness with conceptual unity and a rationale for certain investigations that are carried out in the field. (shrink)

L'auteur a voulu définir deux orientations principales dans les recherches sur les fondements des mathématiques, le constructivisme et le structuralisme . Il montre à l'aide d'exemples tirés de la théorie axiomatique des ensembles, e.g. l'hypothèse du continu, et de l'intuitionnisme, e.g. la notion de séquence de choix, que les deux approches constituent des voies complémentaires dans les recherches sur les fondements. L'auteur propose quelques idées nouvelles, en particulier sur le continu et l'horizon constructif, tout au long de l'article et dans (...) un appendice. L'article se résume à la défense et l'illustration d'une philosophie constructivisme en voie d'élaboration.The author has endeavoured to define two main trends in the research on the foundations of mathematics, constructivism and structuralism . He gives many examples in axiomatic set theory, e.g. the continuum hypothesis, and in intuitionism, e.g. the notion of choice sequence, in order to show that the two approaches are complementary. The paper contains some original ideas, concerning the structure of the continuum and the constructive horizon, and is completed by an appendix. The paper is an attempt at the justification of a constructivist philosophy in the making. (shrink)

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

We describe an emerging field, that of nonclassical computability and nonclassical computing machinery. According to the nonclassicist, the set of well-defined computations is not exhausted by the computations that can be carried out by a Turing machine. We provide an overview of the field and a philosophical defence of its foundations.

We give an introduction to Turing categories, which are a convenient setting for the categorical study of abstract notions of computability. The concept of a Turing category first appeared in the work of Longo and Moggi; later, Di Paolo and Heller introduced the closely related recursion categories. One of the purposes of Turing categories is that they may be used to develop categorical formulations of recursion theory, but they also include other notions of computation, such as models of combinatory logic (...) and of the lambda calculus. In this paper our aim is to give an introduction to the basic structural theory, while at the same time illustrating how the notion is a meeting point for various other areas of logic and computation. We also provide a detailed exposition of the connection between Turing categories and partial combinatory algebras and show the sense in which the study of Turing categories is equivalent to the study of PCAs. (shrink)