We consider Luciano Floridi's proposal for a structural realism based on an Informational Structural Realism which, as he describes in his book (p. 339): ‘As a form of realism … is committed to the existence of a mind-independent reality addressed by, and constraining knowledge’. In doing this, we inform and reform aspects of the argument within a mathematical and, specifically, computability theoretic context.

S. Barry Cooper, Mariya I. Soskova; The incomputable, Journal of Logic and Computation, Volume 23, Issue 6, 1 December 2013, Pages 1143–1144, https://doi.o

The scope of computation has expanded dramatically beyond the rubric of discrete, deterministic sequential computation under which it has been studied for many decades. That focus, of course, led to a great deal of deep and beautiful theory, but our focus in this special issue of Mathematical Structures in Computer Science is on new directions that have emerged from the study of computational phenomena in other settings, and thus on a celebration of the diversity of ideas, methods, new applications and novel sources of inspiration that have marked the modern era. The papers in this issue come from sources extending far beyond the core of computer science, yet using many of the central ideas that have evolved within computer science and mathematics. The nexus of all this activity has been, on the one hand, the boundary between logic and computation, and, on the other hand, the natural sciences, particularly physics and biology. The papers in this collection are expanded versions of selected papers from the DCM 2010 workshop, which was held in Edinburgh in July 2010. The theme of the workshop was Causality, Computation and Physics.

Alexandra Soskova, S. Barry Cooper, Andrea Sorbi; Computability at Logic Colloquium 2009, Journal of Logic and Computation, Volume 22, Issue 4, 1 August 20

Albert Einstein encapsulated a commonly held view within the scientific community when he wrote in his book Out of My Later Years (Einstein 1950, page 54) ‘When we say that we understand a group of natural phenomena, we mean that we have found a constructive theory which embraces them.’ This represents a dual challenge to the scientist: on the one hand, to explain the real world in a very basic, and if possible, mathematical, way; but on the other, to characterise the extent to which this is even possible. Recent years have seen the mathematics of computability play an increasingly vital role in pushing forward basic science and in illuminating its limitations within a creative coming together of researchers from different disciplines. This special issue of Mathematical Structures in Computer Science is based on the special session ‘Computability of the Physical’ at the International Conference Computability in Europe 2010, held at Ponta Delgada, Portugal, in June 2010, and it, together with the individual papers it contains, forms what we believe to be a special contribution to this exciting and developing process.

The Theory and Applications of Models of Computation (TAMC) conference series is both international and interdisciplinary in character, bringing together researchers working in computer science, mathematics (especially logic) and the physical sciences. It is this, together with its predominantly computational and computability theoretic focus, that gives the series its special character.

Theory and Applications of Models of Computation (TAMC) is an international conference series with an interdisciplinary character bringing together researchers working in computer science, mathematics (especially logic) and the physical sciences. This interdisciplinary approach, with an emphasis on the theory of computation in a broad sense, gives the series its special appeal within China and internationally. At a time when the pressures are increasingly towards narrowly ad hoc research, and scientific fragmentation, meetings that reassert the importance of theory, fundamental concepts and a wider perspective have an important role to play.

§1. Introduction. Sacks [16] showed that every computably enumerable (c.e.) degree > 0 has a c.e. splitting. Hence, relativising, every c.e. degree has a Δ2 splitting above each proper predecessor (by ‘splitting’ we understand ‘nontrivial splitting’). Arslanov [1] showed that 0′ has a d.c.e. splitting above each c.e. a < 0′. On the other hand, Lachlan [11] proved the existence of a c.e. a < 0 which has no c.e. splitting above some proper c.e. predecessor, and Harrington [10] showed that one could take a = 0′. Splitting and nonsplitting techniques have had a number of consequences for definability and elementary equivalence in the degrees below 0′. Heterogeneous splittings are best considered in the context of cupping and non-cupping. Posner and Robinson [15] showed that every nonzero Δ2 degree can be nontrivially cupped to 0′, and Arslanov [1] showed that every c.e. degree > 0 can be d.c.e. cupped to 0′ (and hence since every d.c.e., or even n-c.e., degree has a nonzero c.e. predecessor, every n-c.e. degree > 0 is d.c.e. cuppable). Cooper [4] and Yates (see Miller [13]) showed the existence of degrees noncuppable in the c.e. degrees. Moreover, the search for relative cupping results was drastically limited by Cooper [5], and Slaman and Steel [17] (see also Downey [9]), who showed that there is a nonzero c.e. degree a below which even Δ2 cupping of c.e. degrees fails. We prove below what appears to be the strongest possible of such nonsplitting and noncupping results.

This article extends Post's; programme to finite levels of the Ershov hierarchy of Δ2 sets. Our initial characterization, in the spirit of Post (1994, Bulletin of the American Mathematical Society, 50, 284–316), of the degrees of the immune and hyperimmune n-enumerable sets leads to a number of results setting other immunity properties in the context of the Turing and wtt-degrees derived from the Ershov hierarchy. For instance, we show that any n-enumerable hyperhyperimmune set must be co-enumerable, for each n ≥ 2. The situation with regard to the wtt-degrees is particularly interesting, as demonstrated by a range of results concerning the wtt-predecessors of hypersimple sets. Finally, we give a number of results directed at characterizing basic classes of n-enumerable degrees in terms of natural information content. For example, a 2-enumerable degree contains a 2-enumerable dense immune set iff it contains a 2-enumerable r-cohesive set iff it bounds a high enumerable set. This result is extended to a characterization of n-enumerable degrees which bound high enumerable degrees. Furthermore, a characterization for n-enumerable degrees bounding only low2 enumerable degrees is given.

The ten papers in this special issue arose from the conference CiE 2005: New Computational Paradigms, held at the University of Amsterdam in June, 2005. CiE 2005 was the first of a new series of conferences associated with the interdisciplinary network Computability in Europe focused on computability in theoretical computer science and mathematical logic, and ranging over a broad spectrum of research areas from the application of novel approaches to computation, through computability-theoretic aspects of physical systems to set-theoretic analyses of infinitary computing models.

Abstract We show that every nonzero Δ20, e-degree bounds a minimal pair. On the other hand, there exist Σ20, e-degrees which bound no minimal pair.

Abstract It is shown that there exists a low2 Harrington non-splitting base — that is, a low2 computably enumerable (c.e.) degree a such that for any c.e. degrees x, y, if 0′ = x ∨ y, then either 0′ = x ∨ a or 0′ = y ∨ a. Contrary to prior expectations, the standard Harrington non-splitting construction is incompatible with the low2-ness requirements to be satisfied, and the proof given involves new techniques with potentially wider application.

We prove the following three theorems on the enumeration degrees of ∑20 sets. Theorem A: There exists a nonzero noncuppable ∑20 enumeration degree. Theorem B: Every nonzero Δ20enumeration degree is cuppable to 0′e by an incomplete total enumeration degree. Theorem C: There exists a nonzero low Δ20 enumeration degree with the anticupping property.

Abstract We prove that there exists a noncappable enumeration degree strictly below 0e′.

Friedberg [3] showed that every degree of unsolvability above 0′ is the jump of some degree, and Sacks [9] showed that the degrees above 0′ which are recursively enumerable (r.e.) in 0′ are the jumps of the r.e. degrees. In this paper we examine the extent to which the Sacks jump theorem can be combined with the minimal pair theorem of Lachlan [4] and Yates [13]. We prove below that there is a degree c > 0′ which is r.e. in 0′ but which is not the jump of half a minimal pair of r.e. degrees. This extends Yates' result [13] proving the existence of noncappable degrees (that is, r.e. degrees a < 0′ for which there is no corresponding r.e. b > 0 with a ∩ b = 0). It also throws more light on the class PS of promptly simple degrees. It was shown by Ambos-Spies, Jockusch, Shore and Soare [1] that PS coincides with the class NC of noncappable degrees, and with the class LC of all low-cuppable degrees, and (using earlier work of Maass, Shore and Stob [5]) that PS splits every class Hn or Ln, n ≥ 0, in the high-low hierarchy of r.e. degrees. If c > 0′, with c r.e. in 0′, let and call c−1 the jump class for c. It is easy to see that every jump class contains members of PS (= NC = LC). By Sacks [8] there exists a low a ∈ LC, where of course [a, 0′] (= {br.e. ∣a ≤ b ≤ 0′}) ⊆ LC = PS. But by Robinson [7] [a, 0′] intersects with every jump class.

Following Soare [11] we say a recursively enumerable (r.e.) degree a has the anticupping (a.c.) property if there is a nonzero r.e. degree b < a such that for no r.e. c < a does a = b ∪ c. Cooper [2] and Yates showed that 0′ has the a.c. property, while Harrington (see Miller [6]) proved that every high r.e. degree a has the a.c. property. The recent paper by Ambos-Spies, Jockusch, Shore and Soare [1] describes a general theoretical framework for cupping and capping below 0′ which seems likely to be useful in a wider context. Definition. (1) We say b is strongly noncuppable belowa if 0 < b < a and, for each d < a, b ∪ d ≠ a. (2) We say an r.e. a has the strong anticupping property if there is an r.e. b which is strongly noncuppable below a. The main results on cupping in (≤ 0′) are due to Epstein, Posner and Robinson. For instance it is known (Posner and Robinson [8]) that the s.a.c. property fails for 0′. We prove below that r.e. degrees with the s.a.c. property do exist, hence obtaining a nonzero r.e. degree a such that (≤ a) ≢e (≤h) for any high r.e. degree h. This result, obtained by means of an infinite injury construction in (≤ 0′), extends Theorem 2 of [3], proved using a finite injury construction in (≤ 0′). Our main source of notation and terminology is [3].

For sets of natural numbers A and B, A is enumeration reducible to B if there is some effective algorithm which when given any enumeration of B will produce an enumeration of A. Gutteridge [5] has shown that in the upper semilattice of the enumeration degrees there are no minimal degrees (see Cooper [3]), and in this paper we study those pairs of degrees with gib 0. Case [1] constructed a minimal pair. This minimal pair construction can be relativised to any gib, and following a suggestion of Jockusch we can also fix one of the degrees and still construct the pair. These methods yield an easier proof of Case's exact pair theorem for countable ideals. 0″ is an upper bound for the minimal pair constructed in §1, and in §2 we improve this bound to any Σ2-high Δ2 degree. In contrast to this we show that every low degree c bounds a degree a which is not in any minimal pair bounded by c. The structure of the co-r.e. e-degrees is isomorphic to that of the r.e. Turing degrees, and Gutteridge has constructed co-r.e. degrees which form a minimal pair in the e-degrees. In §3 we show that if a, b is any minimal pair of co-r.e. degrees such that a is low then a, b is a minimal pair in the e-degrees (and so Gutteridge's result follows). As a corollary of this we can embed any countable distributive lattice and the two nondistributive five-element lattices in the e-degrees below 0′. However the lowness assumption is necessary, as we also prove that there is a minimal pair of (high) r.e. degrees which is not a minimal pair in the e-degrees (under the isomorphism). In §4 we present more concise proofs of some unpublished work of Lagemann on bounding incomparable pairs and embedding partial orderings. As usual, {Wi}i ∈ ω is the standard listing of the recursively enumerable sets, Du is the finite set with canonical index u and {‹ m, n ›}m, n ∈ ω is a recursive, one-to-one coding of the pairs of numbers onto the numbers. Capital italic letters will be variables over sets of natural numbers, and lower case boldface letters from the beginning of the alphabet will vary over degrees.

As in Rogers [3], we treat the partial degrees as notational variants of the enumeration degrees (that is, the partial degree of a function is identified with the enumeration degree of its graph). We showed in [1] that there are no minimal partial degrees. The purpose of this paper is to show that the partial degrees below 0′ (that is, the partial degrees of the Σ2 partial functions) are dense. From this we see that the Σ2 sets play an analagous role within the enumeration degrees to that played by the recursively enumerable sets within the Turing degrees. The techniques, of course, are very different to those required to prove the Sacks Density Theorem (see [4, p. 20]) for the recursively enumerable Turing degrees. Notation and terminology are similar to those of [1]. In particular, We, Dx, 〈m, n〉, ψe are, respectively, notations for the e th r.e. set in a given standard listing of the r.e. sets, the finite set whose canonical index is x, the recursive code for (m, n) and the e th enumeration operator (derived from We). Recursive approximations etc. are also defined as in [1]. Theorem 1. If B and C are Σ2sets of numbers, and B ≰e C, then there is an e-operator Θ with Proof. We enumerate an e-operator Θ so as to satisfy the list of conditions: Let {Bs ∣ s ≥ 0}, {Cs ∣ s ≥ 0} be recursive sequences of approximations to B, C respectively, for which, for each х, х ∈ B ⇔ (∃s*)(∀s ≥ s*)(х ∈ Bs) and х ∈ C ⇔ (∃s*)(∀s ≥ s*)(х ∈ Cs).

A notion of relative reducibility for partial functions, which coincides with Turing reducibility on the total functions, was first given by S.C. Kleene in Introduction to metamathematics [4]. Following Myhill [7], this was made more explicit in Hartley Rogers, Jr., Theory of recursive functions and effective computability [8, pp. 146, 279], where some basic properties of the partial degrees or (equivalent, but notationally more convenient) the enumeration degrees, were derived. The question of density of this proper extension of the degrees of unsolvability was left open, although Medvedev's result [6] that there are quasi-minimal partial degrees (that is, nonrecursive partial degrees with no nonrecursive total predecessors) is proved. In 1971, Sasso [9] introduced a finer notion of partial degree, which also contained the Turing degrees as a proper substructure (intuitively, Sasso's notion of reducibility between partial functions differed from Rogers' in that computations terminated when the oracle was asked for an undefined value, whereas a Rogers computation could be thought of as proceeding simultaneously along a number of different branches of a ‘consistent’ computation tree—cf. Sasso [10]). His construction of minimal ‘partial degrees’ [11], while of interest in itself, left open the analogous problem for the more standard partial degree structure.

A. H. Lachlan [2] and C. E. M. Yates [4] independently showed that minimal pairs of recursively enumerable (r.e.) degrees exist. Lachlan and Richard Ladner have shown (unpublished) that there is no uniform method for producing a minimal pair of r.e. degrees below a given nonzero r.e. degree. It is not known whether every nonzero r.e. degree bounds a r.e. minimal pair, but in the present paper it is shown (uniformly) that every high r.e. degree bounds a r.e. minimal pair. (A r.e. degree is said to be high if it contains a high set in the sense of Robert W. Robinson [3].) Theorem. Let a be a recursively enumerable degree for which a′ = 0″. Then there are recursively enumerable degrees b0 and b1 such that0 < bi < a for each i ≤ 1, and b0 ⋂ b1 = 0. The proof is based on the Lachlan minimal r.e. pair construction. For notation see Lachlan [2] or S. B. Cooper [1]. By Robinson [3] we can choose a r.e. representative A of the degree a, with uniformly recursive tower {As, ∣ s ≥ 0} of finite approximations to A, such that CA dominates every recursive function where We define, stage by stage, finite sets Bi,s, i ≤ 1, s ≥ 0, in such a way that Bi, s + 1 ⊇ Bi,s for each i, s, and {Bi,s ∣ i ≤ 1, s ≥ 0} is uniformly recursive.

The jump a′ of a degree a is defined to be the largest degree recursively enumerable in a in the upper semilattice of degrees of unsolvability. We examine below some of the ways in which the jump operation is related to the partial ordering of the degrees. Fried berg [3] showed that the equation a = x′ is solvable if and only if a ≥ 0′. Sacks [13] showed that we can find a solution of a = x′ which is ≤ 0′ (and in fact is r.e.) if and only if a ≥ 0′ and is r.e. in 0′. Spector [16] constructed a minimal degree and Sacks [13] constructed one ≤ 0′. So far the only result concerning the relationship between minimal degrees and the jump operator is one due to Yates [17] who showed that there is a minimal predecessor for each non-recursive r.e. degree, and hence that there is a minimal degree with jump 0′. In §1, we obtain an analogue of Friedberg's theorem by constructing a minimal degree solution for a = x′ whenever a ≥ 0′. We incorporate Friedberg5s original number-theoretic device with a complicated sequence of approximations to the nest of trees necessary for the construction of a minimal degree. The proof of Theorem 1 is a revision of an earlier, shorter presentation, and incorporates many additions and modifications suggested by R. Epstein. In §2, we show that any hope for a result analogous to that of Sacks on the jumps of r.e. degrees cannot be fulfilled since 0″ is not the jump of any minimal degree below 0′. We use a characterization of the degrees below 0′ with jump 0″ similar to that found for r.e. degrees with jump 0′ by R. W. Robinson [12]. Finally, in §3, we give a proof that every degree a ≤ 0′ with a′ = 0″ has a minimal predecessor. Yates [17] has already shown that every nonzero r.e. degree has a minimal predecessor, but that there is a nonzero degree ≤ 0′ with no minimal predecessor (see [18]; or for the original unrelativized result see [10] or [4]).

An infinite set A is said to be hyperhyperimmune (h.h.i.) if, for any collection of disjoint simultaneously recursively enumerable (r.e.) finite sets, A must fail to intersect with one of those sets. Thus the elements of an h.h.i. set are, in a sense, very elusive. D. A. Martin [3] showed that the degrees of h.h.i. sets with r.e. complements are exactly the r.e. degrees with jump 0″. More generally, C. G. Jockusch [2] found a′ ≥ 0″ to be a sufficient condition for a to be the degree of an h.h.i. set and found a′ ≥ 0′ to be necessary. However, it was also shown that in the degrees as a whole neither condition gave a characterization of the h.h.i. degrees. The purpose of this note is to prove that a′ = 0″does characterize the h.h.i. degrees below 0′. Theorem. The degrees below 0′ containing h.h.i. sets are exactly those degrees below 0′ with jump 0″. Proof. From [2], if a′ ≥ 0″, then a contains an h.h.i. set. Conversely, let A ∈ a where a′ < 0″ and a < 0′. Let {As ∣ s ≥ 0} be a recursive sequence of finite sets such that for each x, lims, Ax(x) exists and equals A(x). For a set B, let B[m] denote B ∩ [0, m], and (if B is finite) let ∣B∣ denote the cardinality of B.