Can we deploy creative practices to critically address the fatal interlocking of global surveillance technologies, neo-colonial expansionism, environmental degradation and the lethal threat of drone warfare? Throughout the following conversation, Shona Illingworth and Anthony Downey examine these and other questions in relation to the recent publication of Topologies of Air (Sternberg Press and The Power Plant, 2022). Edited by Downey, the book includes discussion and documentation of two major bodies of work by Illingworth, including Topologies of Air (2021) (...) and Lesions in the Landscape (2015), alongside an extended series of essays that analyse the psychological and environmental impact of military, industrial and corporate transformations of airspace and outer space. Employing interdisciplinary research and collaborative processes, Illingworth’s practice, as detailed in the discussion below, uses creative methodologies to visualize and interrogate this proliferating exploitation of airspace. The conversation between Illingworth and Downey also outlines the work of the Airspace Tribunal, an ongoing series of public hearings that brings together diverse disciplines, methodologies, knowledge and lived experiences to propose a new human right that will counter the colonization of the sky and, in time, protect individuals, communities and ecologies from ever-increasing threats from above. (shrink)

We describe punctual categoricity in several natural classes, including binary relational structures and mono-unary functional structures. We prove that every punctually categorical structure in a finite unary language is${\text {PA}}(0')$-categorical, and we show that this upper bound is tight. We also construct an example of a punctually categorical structure whose degree of categoricity is$0''$. We also prove that, with a bit of work, the latter result can be pushed beyond$\Delta ^1_1$, thus showing that punctually categorical structures can possess arbitrarily complex (...) automorphism orbits.As a consequence, it follows that binary relational structures and unary structures are not universal with respect to primitive recursive interpretations; equivalently, in these classes every rich enough interpretation technique must necessarily involve unbounded existential quantification or infinite disjunction. In contrast, it is well-known that both classes are universal for Turing computability. (shrink)

A problem is a multivalued function from a set of instances to a set of solutions. We consider only instances and solutions coded by sets of integers. A problem admits preservation of some computability-theoretic weakness property if every computable instance of the problem admits a solution relative to which the property holds. For example, cone avoidance is the ability, given a noncomputable set A and a computable instance of a problem ${\mathsf {P}}$, to find a solution relative to which A (...) is still noncomputable.In this article, we compare relativized versions of computability-theoretic notions of preservation which have been studied in reverse mathematics, and prove that the ones which were not already separated by natural statements in the literature actually coincide. In particular, we prove that it is equivalent to admit avoidance of one cone, of $\omega $ cones, of one hyperimmunity or of one non- $\Sigma ^{0}_1$ definition. We also prove that the hierarchies of preservation of hyperimmunity and non- $\Sigma ^{0}_1$ definitions coincide. On the other hand, none of these notions coincide in a nonrelativized setting. (shrink)

We give a systematic technical exposition of the foundations of the theory of computably compact metric spaces. We discover several new characterizations of computable compactness and apply these characterizations to prove new results in computable analysis and effective topology. We also apply the technique of computable compactness to give new and less combinatorially involved proofs of known results from the literature. Some of these results do not have computable compactness or compact spaces in their statements, and thus these applications are (...) not necessarily direct or expected. (shrink)

An oracle A is low-for-speed if it is unable to speed up the computation of a set which is already computable: if a decidable language can be decided in time $t(n)$ using A as an oracle, then it can be decided without an oracle in time $p(t(n))$ for some polynomial p. The existence of a set which is low-for-speed was first shown by Bayer and Slaman who constructed a non-computable computably enumerable set which is low-for-speed. In this paper we answer (...) a question previously raised by Bienvenu and Downey, who asked whether there is a minimal degree which is low-for-speed. The standard method of constructing a set of minimal degree via forcing is incompatible with making the set low-for-speed; but we are able to use an interesting new combination of forcing and full approximation to construct a set which is both of minimal degree and low-for-speed. (shrink)

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.

Journal of Political Philosophy, EarlyView.

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)

This book presents new results in computability theory, a branch of mathematical logic and computer science that has become increasingly relevant in recent years. The field's connections with disparate areas of mathematical logic and mathematics more generally have grown deeper, and now have a variety of applications in topology, group theory, and other subfields. This monograph establishes new directions in the field, blending classic results with modern research areas such as algorithmic randomness. The significance of the book lies not only (...) in the depth of the results contained therein, but also in the fact that the notions the authors introduce allow them to unify results from several subfields of computability theory. (shrink)

Informal construction -- Formal construction -- Limiting results.

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)

Loïc Wacquant argues for a radicalization of the habitus concept provided by Pierre Bourdieu, suggesting that habitus is a site and mode for conducting research, not simply an explanatory or theoretical mechanism. Taking seriously this call to examine skills and communities of practice through apprenticeship, however, requires that the theoretical account of habitus be subject to empirical testing. Moreover, enquiry into communities of practice, especially the subtle psychological, behavioural and even neurological consequences of skill acquisition, means that claims about the (...) habitus can be scrutinized by fields such as psychology, neurology and even human biology. Habitus as a truly open path of inquiry will demand, not wholly novel concepts, but a recognition of when claims about practice are simultaneously testable, and falsifiable, by other forms of empirical enquiry, including the human sciences. (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)

We explore the complexity of Sacks’ Splitting Theorem in terms of the mind change functions associated with the members of the splits. We prove that, for any c.e. set A, there are low computably enumerable sets $A_0\sqcup A_1=A$ splitting A with $A_0$ and $A_1$ both totally $\omega ^2$ -c.a. in terms of the Downey–Greenberg hierarchy, and this result cannot be improved to totally $\omega $ -c.a. as shown in [9]. We also show that if cone avoidance is added then (...) there is no level below $\varepsilon _0$ which can be used to characterize the complexity of $A_1$ and $A_2$. (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.

However, the relation of the novels to ancient philosophy remains under-studied. This volume is intended to open up some of the issues involved.

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.

Volume 33, Issue 3, April 2020, Page 469-473.

Cenzer, D., R. Downey, C. Jockusch and R.A. Shore, Countable thin Π01 classes, Annals of Pure and Applied Logic 59 79–139. A Π01 class P {0, 1}ω is thin if every Π01 subclass of P is the intersection of P with some clopen set. Countable thin Π01 classes are constructed having arbitrary recursive Cantor- Bendixson rank. A thin Π01 class P is constructed with a unique nonisolated point A and furthermore A is of degree 0’. It is shown that (...) no set of degree ≥0” can be a member of any thin Π01 class. An r.e. degree d is constructed such that no set of degree d can be a member of any thin Π01 class. It is also shown that between any two distinct comparable r.e. degrees, there is a degree that contains a set which is of rank one in some thin Π01 class. It is shown that no maximal set can have rank one in any Π01 class, while there exist maximal sets of rank 2. The connection between Π01 classes, propositional theories and recursive Boolean algebras is explored, producing several corollaries to the results on Π01 classes. For example, call a recursive Boolean algebra thin if it has no proper nonprincipal recursive ideals. Then no thin recursive Boolean algebra can have a maximal ideal of degree ≥0”. (shrink)

In this paper I argue that, by combining eliminativist and fictionalist approaches toward the sub-personal representational posits of predictive processing, we arrive at an empirically robust and yet metaphysically innocuous cognitive scientific framework. I begin the paper by providing a non-representational account of the five key posits of predictive processing. Then, I motivate a fictionalist approach toward the remaining indispensable representational posits of predictive processing, and explain how representation can play an epistemologically indispensable role within predictive processing explanations without thereby (...) requiring that representation metaphysically exists. Finally, I outline four consequences of accepting this approach and explain why they are beneficial: we arrive at a victory for metaphysical eliminativism in the ‘representation wars’; my account fits with extant empirical practice; my account provides guidance for future research; and, my account provides the beginnings of a response to Mark Sprevak’s IBE problem for fictionalist approaches toward sub-personal representation. (shrink)

We report on some recent work centered on attempts to understand when one set is more random than another. We look at various methods of calibration by initial segment complexity, such as those introduced by Solovay [125], Downey, Hirschfeldt, and Nies [39], Downey, Hirschfeldt, and LaForte [36], and Downey [31]; as well as other methods such as lowness notions of Kučera and Terwijn [71], Terwijn and Zambella [133], Nies [101, 100], and Downey, Griffiths, and Reid [34]; (...) higher level randomness notions going back to the work of Kurtz [73], Kautz [61], and Solovay [125]; and other calibrations of randomness based on definitions along the lines of Schnorr [117].These notions have complex interrelationships, and connections to classical notions from computability theory such as relative computability and enumerability. Computability figures in obvious ways in definitions of effective randomness, but there are also applications of notions related to randomness in computability theory. For instance, an exciting by-product of the program we describe is a more-or-less naturalrequirement-freesolution to Post's Problem, much along the lines of the Dekker deficiency set. (shrink)

Several papers (e.g. [7, 23, 42]) have recently sought to give general frameworks for online structures and algorithms ([4]), and seeking to connect, if only by analogy, online and computable structure theory. These initiatives build on earlier work on online colouring and other combinatorial algorithms by Bean [10], Kierstead, Trotter et al. [48, 54, 57] and others, as we discuss below. In this paper we will look at such frameworks and illustrate them with examples from the first author’s MSc Thesis (...) ([58]). In this thesis, Askes looks at online, adversarial online and strongly online algorithms and structures. Additionally, we prove some new theorems about online algorithms on graphs of bounded pathwidth as well as some new results on punctually 1-decidable structures. (shrink)

Guided by a life-course perspective, this article uses data from 11 waves of the Michigan Panel Study of Income Dynamics to examine the influence of human capital, family structure, and local labor-market demand variables on the reentry into the labor force of midlife homemakers in the United States in the 1970s. By looking at two contiguous time periods, the first and last halves of the 1970s, it investigates how the influence of these factors varied with social changes in the job-opportunity (...) structure for women in the United States during the 1970s, a time when the service sector expanded and public approval of married women's employment rose. We found that the likelihood of reentry varied with education, age, and marital status, as well as time period. These findings suggest the need for a model of the labor-force reentry of homemakers in midlife that takes account of historical period as well as the distinctive realities of women's lives in middle adulthood. (shrink)

In response to the many pressures facing public higher education, public universities are experimenting with business-oriented practices that seem likely to alter their nature and purposes. In this paper, we examine several hybrid experiments—new organizational strategies intended deliberately, sometimes explicitly, to hybridize the traditional norms and practices associated with academia and business at one emblematic public university. These cases illustrate how each hybrid experiment is a tacit response to existing norms and strategies that govern the university–business boundary, initiated as a (...) hedge against the challenging fiscal and political climate. Taken together, they do not lead to a unitary and/or linear spread of business codes and practices. Instead, what some have referred to as “business logic” appears multifaceted, having many elements that are deployed, institutionalized, and perceived differently in different contexts, even within a single university. (shrink)

We study for each computably bounded $\Pi ^0_1$ class P the set of degrees of c.e. paths in P. We show, amongst other results, that for every c.e. degree a there is a perfect $\Pi ^0_1$ class where all c.e. members have degree a. We also show that every $\Pi ^0_1$ set of c.e. indices is realized in some perfect $\Pi ^0_1$ class, and classify the sets of c.e. degrees which can be realized in some $\Pi ^0_1$ class as exactly (...) those with a computable representation. (shrink)