We study connections between classical asymptotic density, computability and computable enumerability. In an earlier paper, the second two authors proved that there is a computably enumerable set A of density 1 with no computable subset of density 1. In the current paper, we extend this result in three different ways: The degrees of such sets A are precisely the nonlow c.e. degrees. There is a c.e. set A of density 1 with no computable subset of nonzero density. There is a (...) c.e. set A of density 1 such that every subset of A of density 1 is of high degree. We also study the extent to which c.e. sets A can be approximated by their computable subsets B in the sense that A\B has small density. There is a very close connection between the computational complexity of a set and the arithmetical complexity of its density and we characterize the lower densities, upper densities and densities of both computable and computably enumerable sets. We also study the notion of "computable at density r" where r is a real in the unit interval. Finally, we study connections between density and classical smallness notions such as immunity, hyperimmunity, and cohesiveness. (shrink)

We classify the asymptotic densities of the sets according to their level in the Ershov hierarchy. In particular, it is shown that for, a real is the density of an n‐c.e. set if and only if it is a difference of left‐ reals. Further, we show that the densities of the ω‐c.e. sets coincide with the densities of the sets, and there are ω‐c.e. sets whose density is not the density of an n‐c.e. set for any.

We prove that there exists a noncomputable c.e. real which is low for weak 2-randomness, a definition of randomness due to Kurtz, and that all reals which are low for weak 2-randomness are low for Martin-Löf randomness.

Schnorr randomness is a notion of algorithmic randomness for real numbers closely related to Martin-Löf randomness. After its initial development in the 1970s the notion received considerably less attention than Martin-Löf randomness, but recently interest has increased in a range of randomness concepts. In this article, we explore the properties of Schnorr random reals, and in particular the c.e. Schnorr random reals. We show that there are c.e. reals that are Schnorr random but not Martin-Löf random, and provide a new (...) characterization of Schnorr random real numbers in terms of prefix-free machines. We prove that unlike Martin-Löf random c.e. reals, not all Schnorr random c.e. reals are Turing complete, though all are in high Turing degrees. We use the machine characterization to define a notion of "Schnorr reducibility" which allows us to calibrate the Schnorr complexity of reals. We define the class of "Schnorr trivial" reals, which are ones whose initial segment complexity is identical with the computable reals, and demonstrate that this class has non-computable members. (shrink)

We characterize the class of c.e. degrees that bound a critical triple as those degrees that compute a function that has no ω-c.e. approximation.

Physical activity can prevent and treat multiple diseases. Exercise referral schemes have been used extensively as one healthcare pathway. Schemes typically involve the referral of an inactive individual, with a long term condition, for a time limited exercise programme. Evidence has shown limited benefit, yet the exploration of implementation is under researched. National guidance, in the United Kingdom, recommends that exercise referral schemes should not be commissioned unless behaviour change practices are implemented. Nonetheless, novel evaluations, which are sensitive to the (...) complex nature of behaviour change implementation, have not been undertaken. Therefore, this research sought to answer how, why, and in which circumstances behaviour change practices are implemented by exercise referral practitioners. Realist evaluation, a form of theory driven evaluation, was adopted to address the research question. Programme theory, the envisaged causal workings of implementation, was developed and tested to advance knowledge on how behaviour change practice can be achieved by exercise referral practitioners. An 8-month focused ethnography was used to develop programme theory. Subsequently, a survey was validated to empirically test programme theory. Adjudication between theory required an assessment of the fidelity to behaviour change practices. Therefore, vignettes were created and validated, which acted as a proxy to observations. The survey was then completed through online, and facilitated interviews, using a ‘think aloud’ methodology. The analysis showed that practice frameworks augment motivation when there is congruent practitioner characteristics and practice monitoring is utilised, whereas frameworks improve capability when faced with challenging attendees. Supportive leadership improves motivation when there is an organisational commitment to behaviour change and practitioners are passionate to empower attendees. Supportive leadership improves capability for implementation when a learning climate is created. Partnerships with medical professionals enhance implementation, through changes to motivation, when medical professionals commit and recognise the value of schemes, and partnerships enhance capability where medical professionals reinforce practice via congruent communication. On-going support enhances capability where practitioners are cognizant of their role and have lower behaviour change competencies, conversely, motivation is enhanced as practitioners become more capable. Exercise referral schemes risk being labelled ineffective without considering the implementation climate and fidelity to best practice guidance. This thesis provides portable and actionable findings, which could lead to a greater translation of behaviour change practices to applied settings in exercise referral and in other medically led community based self-management interventions. (shrink)

Descartes is widely portrayed as the arch proponent of “the epistemological transparency of thought” (or simply, “Transparency”). The most promising version of this view—Transparency-through-Introspection—says that introspecting (i.e., inwardly attending to) a thought guarantees certain knowledge of that thought. But Descartes rejects this view and provides numerous counterexamples to it. I argue that, instead, Descartes’s theory of self-knowledge is just an application of his general theory of knowledge. According to his general theory, certain knowledge is acquired only through clear and distinct (...) intellection. Thus, in his view, certain knowledge of one’s thoughts is acquired only through clear and distinct intellection of one’s thoughts. Introspection is a form of intellection and it can be clear and distinct. Ordinarily, however, introspection isn’t clear and distinct but is instead confused with dubitable perceptions of bodies. To make introspection clear and distinct, we need to “sharply separate” it from all perceptions of bodies by doubting all perceptions of bodies. Without such radical doubt, introspection remains confused and we lack certain knowledge not just of the specific features of our thoughts, but even of the minimal claim that a thought exists. Far from being the high priest of Transparency, Descartes is radically opposed to it. (shrink)

We construct a $\Delta^0_2$ degree which fails to be computably enumerable in any computably enumerable set strictly below $\emptyset'$.

In _Matter and Consciousness_, Paul Churchland presents a concise and contemporary overview of the philosophical issues surrounding the mind and explains the main theories and philosophical positions that have been proposed to solve them. Making the case for the relevance of theoretical and experimental results in neuroscience, cognitive science, and artificial intelligence for the philosophy of mind, Churchland reviews current developments in the cognitive sciences and offers a clear and accessible account of the connections to philosophy of mind. For (...) this third edition, the text has been updated and revised throughout. The changes range from references to the iPhone's "Siri" to expanded discussions of the work of such contemporary philosophers as David Chalmers, John Searle, and Thomas Nagel. Churchland describes new research in evolution, genetics, and visual neuroscience, among other areas, arguing that the philosophical significance of these new findings lies in the support they tend to give to the reductive and eliminative versions of materialism. Matter and Consciousness, written by the most distinguished theorist and commentator in the field, offers an authoritative summary and sourcebook for issues in philosophy of mind. It is suitable for use as an introductory undergraduate text. (shrink)

The options in a decision problem generally have outcomes with common features. Putting aside the common features simplifies deliberations, but the simplification requires a philosophical justification that this book provides.

This book demonstrates how children's imagination makes a continuing contribution to their cognitive and emotional development.

We describe new results in parametrized complexity theory. In particular, we prove a number of concrete hardness results for W[P], the top level of the hardness hierarchy introduced by Downey and Fellows in a series of earlier papers. We also study the parametrized complexity of analogues of PSPACE via certain natural problems concerning k-move games. Finally, we examine several aspects of the structural complexity of W [P] and related classes. For instance, we show that W[P] can be characterized in (...) terms of the DTIME ) and NP. (shrink)

The twentieth century has witnessed an unprecedented 'crisis in the foundations of mathematics', featuring a world-famous paradox (Russell's Paradox), a challenge to 'classical' mathematics from a world-famous mathematician (the 'mathematical intuitionism' of Brouwer), a new foundational school (Hilbert's Formalism), and the profound incompleteness results of Kurt Gödel. In the same period, the cross-fertilization of mathematics and philosophy resulted in a new sort of 'mathematical philosophy', associated most notably (but in different ways) with Bertrand Russell, W. V. Quine, and Gödel himself, (...) and which remains at the focus of Anglo-Saxon philosophical discussion. The present collection brings together in a convenient form the seminal articles in the philosophy of mathematics by these and other major thinkers. It is a substantially revised version of the edition first published in 1964 and includes a revised bibliography. The volume will be welcomed as a major work of reference at this level in the field. (shrink)

During the past few years significant progress has been made in our understanding of the structure and function of the proteins involved in eukaryotic DNA replication. Data from several laboratories suggest that, in contrast to prokaryotic DNA replication, two distinct DNA polymerases are required for eukaryotic DNA replication, i.e. DNA polymerase delta for the synthesis of the leading strand and DNA polymerase alpha for the lagging strand. Several accessory proteins analogous to prokaryotic replication factors have been identified and some of (...) these are specific for pol delta whereas others affect both DNA replicases. The replicases and their accessory proteins appear to be highly conserved in eukaryotes, as homologous proteins have been found in species ranging from humans to yeast. (shrink)

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)

The survey contains a detailed discussion of methods and results in the new emerging area of online “punctual” structure theory. We also state several open problems.

Zusammenfassungen der Referate in französischer Sprache.

An agent often does not have precise probabilities or utilities to guide resolution of a decision problem. I advance a principle of rationality for making decisions in such cases. To begin, I represent the doxastic and conative state of an agent with a set of pairs of a probability assignment and a utility assignment. Then I support a decision principle that allows any act that maximizes expected utility according to some pair of assignments in the set. Assuming that computation of (...) an option's expected utility uses comprehensive possible outcomes that include the option's risk, no consideration supports a stricter requirement. (shrink)

Schelling und Hegel benutzen in ihren philosophischen Texten mathematische und naturwissenschaftliche Modelle wie Unendlichkeit oder Gleichgewicht. Die Strukturen dieser Begriffe liefern einen Massstab fur den Vergleich der Positionen Schellings und Hegels, der fur Schellings Identitatsphilosophie und Hegels erste Jenaer Schriften durchgefuhrt wird. Als wichtigstes Resultat kann eine grundlegende Differenz zwischen beiden Positionen bereits um 1801 nachgewiesen und gezeigt werden, dass diese auf einer unterschiedlichen Auffassung der Rolle des Absoluten beruht.

Like Plato, Protagoras held that young children learn virtue from fine examples in poetry. Unlike Plato, Protagoras taught adults by correcting the diction of poets. In this paper I ask what his standard of correctness might be, and what benefit he intended his students to take from exercises in correction. If his standard of correctness is truth, then he may intend his students to learn by questioning the content of poems; that would be suggestive of Plato’s program in Republic III. (...) But his standard is more likely to be the accurate use of language; in that case he would intend his students to learn to express their thoughts clearly enough that their audience would understand what they were saying. That standard would be independent of the truth of what they are saying; and that would be a precursor to modern techniques by which we try to teach speaking and writing. Truth is not so easy to escape, however, and we shall see that Protagoras’ exercise must assume that the poet is trying to tell the truth. (shrink)

We solve a longstanding question of Soare by showing that if ${\mathbf d}$ is a non-low $_2$ computably enumerable degree then ${\mathbf d}$ contains a c.e. set with no r-maximal c.e. superset.