S. Barry Cooper (1943

Abstract

Barry’s life and work were incredibly multi-faceted, ranging from research in pure mathematics via interests in artificial intelligence to long-distance running and jazz. A memorial special issue of an academic journal is not the place to celebrate all of these facets. Even the many academic facets of his life and work are difficult to condense into a single obituary; as a consequence, we decided to organise this obituary as a compilation of various viewpoints from different perspectives and in different formats: Section 1 is a brief obituary written by Barry’s Leeds colleagues and based on a shorter text published in the London Mathematical Society Newsletter [70]; Section 2 is a printed version of the words spoken by Dag Normann, then the President of the Association CiE, at Barry’s funeral in Leeds; Section 3 surveys Barry’s work and influence in the study of the partial or enumeration degrees; Section 4 gives a personal account of Barry’s relationship to the logic community in Bulgaria; and Section 5 recollects several scientific and academic aspects of Barry’s life. The sections of this obituary are supplemented by [71], published in 2016 in this journal and describing Barry’s rôle in the formation of the Association CiE. These diverse viewpoints allow the reader a triangulation via a number of episodes of Barry’s life and work in order to obtain a multi-dimensional picture of this special researcher and academic. The text is illustrated by many pictures in chronological order, starting from Barry’s childhood and continuing until the year 2015. Many of these pictures come from Peter van Emde Boas’s vast collection of conference photos and Section 6 provides some commentary on the collection in general and these pictures in particular.

Figure 1.

Left: The Bognor Boys. Right: Barry during his time in Berkeley, U.S.A.

1. Richard Elwes, Andy Lewis-Pye, Dugald Macpherson, Stan Wainer: Obituary reprinted from the Notices of the London Mathematical Society

Professor S. Barry Cooper passed away on 26 October 2015. He was a key and influential member of the logic group in Leeds since 1969, championing the cause of computability theory and popular with staff and students alike.

Barry attended Chichester High School for Boys, and graduated from Oxford in 1966. He studied for a Ph.D., formally under R.L. Goodstein at Leicester, but worked mainly in Manchester with Mike Yates, the only established British researcher in Barry’s chosen field: the structure-theory of the Turing degrees. He was appointed Lecturer at the University of Leeds in 1969, where he remained, except for regular sabbaticals and invited visits abroad. He was awarded his Professorship in 1996.

By this time, the study of degree structures had matured into a mathematical discipline of great technical sophistication. Known for his deep, complex constructions, Barry played a prominent international role in this growth. He defined and intensively studied the jump classes, now objects of central importance, and he struggled hard with difficult, long-standing problems to do with definability and automorphisms. His theorem that every degree computably enumerable in and above $0^{'}$ is the jump of a minimal degree, is regarded as a classic. He championed the study of the enumeration degrees, establishing many of their fundamental properties. In later years, Barry also became interested in the practical and philosophical significance of the limits of computability.

The year 2012 marked the centenary of the birth of Alan Turing, a celebration which Barry led with boundless energy, and which did much to bring Turing the public recognition he deserves. Barry became the event’s media spokesman and co-organised a six month long programme on Semantics and Syntax at the Isaac Newton Institute for Mathematical Sciences in Cambridge. His edited volume with Jan van Leeuwen Alan Turing: His Work and Impact (2013) later won the Association of American Publishers’ R.R. Hawkins Award.

Popular with undergraduates as an outstanding and charismatic teacher, Barry was a well-known and respected figure around the University of Leeds. Within the School of Mathematics he was always actively involved and sympathetic with students at all levels.

From 2005 to 2008, he took on the lead role in designing and planning the first two phases of a major, and long-overdue, refurbishment and expansion of the mathematics building (a further major phase three was only recently completed). This required enormous energy, diplomacy and negotiating skill in dealings with the University Estates Office, the architects, and with members of the mathematics staff concerned about what their new office would be like, and where it would be. All of this he handled with great delicacy, vision, and firmness when it was needed.

He supervised many successful Ph.D. students, secured many successful research grants, and was founder and president of the Association Computability in Europe, a flourishing association that now has more than 1000 members. He was awarded an honorary degree from Sofia University in 2011 (cf. Fig. 11).

Figure 2.

Left: Barry at CoLoReT 1994 in Amsterdam, The Netherlands; picture taken on 24 July 1994 by Peter van Emde Boas. Right: Group picture with Barry (second from the left) in front of the Agnietenkapel at CoLoReT 1994, The Netherlands; picture taken on 24 July 1994 by Peter van Emde Boas.

Many older computability theorists will recall the Recursive Function Theory Newsletter, an informally distributed news-sheet of abstracts which Barry invented in the 1970s after returning from a two-year sabbatical in Berkeley. Aided by Len Smith, who sadly passed away just months after Barry’s death, and Stan Wainer, he perhaps already foresaw the growth of the subject, and maybe the eventual birth of CiE?

Beyond mathematics, Barry played rugby for England under-16s and became a keen long distance runner, with a personal best marathon time of 2 hours and 48 minutes (cf. Fig. 9). He co-founded the Leeds Jazz non-profit organisation in 1984, and was involved in numerous political campaigns, notably the Chile Solidarity Campaign for refugees from 1973 (a letter of thanks from the Chilean Embassy was read out at the funeral).

He was a special person. Barry is survived by his wife, Kate, herself a one-time computability theorist and student of Barry, and their sons Evan and Mark; and by his daughters Carrie and Shirin with his former partner Sue Buckle.

2. Dag Normann: Words at the funeral of S. Barry Cooper, 12 November 2015

Dear family, dear friends and colleagues of Barry,

It is difficult to recall when I first met Barry, it must have been in 1974 or 1975. In any case, I learned to know him well during my visit to Leeds during the autumn of 1979; I found him to be a colleague who is easy to be with and has research interests touching my own. This is actually a fair description of my relationship with Barry up to August 2003. In that month, he e-mailed me, inviting me to take part in a project proposal for a European network of researchers doing computability theory. He envisaged a network with twelve nodes spread out over Europe, with Leeds as the organisational centre. The proposal was submitted after a process and exchange of viewpoints, and it was based on the insight that there is research on issues of computability in various research communities, in mathematics, in computer science, in physics, linguistics and so on, but that these communities often only have limited insights in each others research. The head figures might be invited to conferences across community borders, but in particular students and young researchers do not see what goes on outside their own limited area. The main philosophy behind the proposal was that European research will benefit from tighter links between these communities. In fact, already in the first proposal, the legacy of Alan Turing was highlighted as something that brought us together and formed our joint platform.

The proposal was rejected, but Barry pressed on for another try. We proposed a network with the same nodes, and based on the same philosophy, but this time making the educational aspect clearer. This involved proposing and organizing a series of conferences with a focus on the needs of students. The University of Amsterdam was hosting the first in 2005. Some of us saw this conference as a singular event where we could bring together people belonging to the communities of computability, and discuss our future, but Barry had a wider view. During a two-day preparatory meeting of a few people, held in Amsterdam in February 2005, plans for further four conferences, with tutorials for students and young (and not so young) researchers, were made, always keeping the basic philosophy in mind. The plans were made for the meetings that eventually took place in Swansea (2006), Siena (2007), Athens (2008) and Heidelberg (2009); for more details, cf. [71].

Once again, the proposal was rejected by the European Union, but the conference series, bridging the cultural gap between mathematics and computer science conferences, was a definite success. The attendance numbers matched, and for some years exceeded, those of the Logic Colloquium. The CiE conference has been an annual event ever since.

Figure 3.

Left: Barry speaks at CoLoReT 1995 in Siena, Italy, in front of the last supper in the meeting hall of the Certosa di Pontignano; picture taken on 1 June 1995 by Peter van Emde Boas. Right: Barry and his family in Siena at CoLoReT 1995; picture taken on 1 June 1995 by Peter van Emde Boas.

In Athens 2008, the Association CiE was formalised, with its own constitution, its own membership, and a board elected by an Annual General Meeting. Barry had been the driving force behind preparing for this, partly because he saw the rôle of CiE as more than being an informal body organizing conferences. At this stage, we already had a governance structure, and more people participated in the running of CiE, reflecting the wide perspective. Barry was elected as the first President of the Association, bringing with him enthusiastic ideas about how to develop the Association further. We had a very pleasant meal under the clear Athens sky celebrating the decision to turn CiE into an association. Maybe this is the only time the board of the Association CiE went out for a meal without an agenda.

Today, the Association CiE has over 1250 members, and it runs its own journal and book series. There are of course many people who have worked hard to achieve this level of activity, but it is fair to say that Barry has been a driving force in the quite rapid expansion of CiE.

There is one recent conference worth mentioning, the one in Cambridge in 2012 connected to the Turing Centenary. Barry played an essential rôle in the organisation of the Alan Turing Year, and it was a coup for CiE to have its annual conference at Turing’s university during the week leading up to Turing’s birthday. This manifested CiE as the association that represent researchers and research communities in the keel-water of Turing.

The Association CiE is the product of many people, but among them Barry stands out as one with visions for what the Association should be, and without his enthusiasm, hard work, ideas and sometimes persistence, the unsuccessful proposals of 2003 and 2005 would never have been transformed into the thriving association it is today.

CiE will live on without Barry. We shall see to it that the Association will develop further following his visions and in his spirit. Of course, we shall miss him, his enthusiasm and commitment. Board meetings and committee meetings will not be the same without him. We shall always remember him, and the community at large, and us involved in CiE in particular, are truly grateful for what he as given us and for his deep involvement in forming and running the Association Computability in Europe.

Figure 4.

Left: Barry at lunch with Piergiorgio Odifreddi, Andrea Sorbi, and Stan Wainer during CoLoReT 1995 in Siena, Italy; picture taken on 1 June 1995 by Peter van Emde Boas. Right: Conference photo of the conference CiE 2005, Amsterdam, The Netherlands.

3. Andrea Sorbi, Barry Cooper and the partial or enumeration degrees

3.1. Barry’s interest in enumeration reducibility

The following quotation from Barry Cooper’s textbook [27, p. 180], expresses better than any other word the extent to which he regarded enumeration reducibility as important and relevant to computability theory:

I am not sure what is more surprising – the way in which enumeration reducibility crops up in all sorts of unexpected places. Or how e-reducibility is not even mentioned in almost every basic text on computability, logic or theoretical computer science.

Indeed, enumeration reducibility (e-reducibility) and the enumeration degrees (e-degrees) have been a special interest of Barry. With a few remarkable exceptions (e.g., Soskov in Bulgaria, and a few Russian scholars including Polyakov, Rozinas, Solon, Zacharov), nobody by the end of the 1970s was studying e-reducibility. In the early 1980s, Barry set up a long term program of thorough study and investigation of the e-degrees. In this project he had the collaboration of very good Ph.D. students: Kevin McEvoy, Kate Copestake, and Phil Watson; and, later, Charles Harris, Mariya Soskova, and Liliana Badillo [8,44,56,72,93,102]. Thanks to his work and charisma, he rapidly and contagiously spread the e-degree bug. Almost all the papers in the field written over the last 30 years originate from problems or questions raised by Barry, or are a consequence of work done by him. He promoted, even if not directly managed, international research projects with lots of space devoted to e-reducibility: the 1994–97 Human and Capital Mobility European network CoLoReT (Complexity, Logic and Recursion Theory, based in Siena, and including Leeds, Amsterdam, Barcelona, Heidelberg, Turin; and, later on, Prague, Kazan, Novosibirsk); the 2000–2002 INTAS project Computability and Models; the 2008-14 project Computing with partial information, managed by Soskov and sponsored by the Bulgarian National Science Foundation. And, of course, he was the demiurge of Computability in Europe. It is due to Barry that e-reducibility and e-degrees are fully alive today, and he was very pleased to see this as one of his most important achievements.

Figure 5.

Left: Barry during a talk at CiE 2005 in Amsterdam, The Netherlands; picture taken on 12 June 2005 by Peter van Emde Boas. Right: Barry and Costas Dimitracopoulos at CiE 2007 in Siena, Italy; picture taken on 20 June 2007 by Peter van Emde Boas.

Barry’s interest in the topic probably dates back to his Berkeley’s years in the early 1970s (cf. Fig. 1), at a time when there still were wide interest and discussion about the issue of “computing using partial information”. The following two quotations from Barry’s papers show Barry’s strong feelings about the importance of this issue:

The main motivation for the study of relative computability of partial functions is the need for a theoretical counterpart to real computational situations in which incomplete or restricted information is available [20].

In a computation using auxiliary informational inputs one can think of the external resource making itself available in different ways. One way is via an oracle as in Turing reducibility, where information is supplied on demand without any time delay. Alternatively the Scott graph model for lambda calculus suggests a situation where new information, only some of it immediately related to the current computation, is constantly being generated (or enumerated) over a period of time in an order which is not under the control of the computer. For some purposes, such as in classifying the relative computability of total functions without any time restrictions, it makes no difference whether oracles or enumerations supply auxiliary informational inputs. But this is not generally the case in situations involving partially accessible information or time-bounds, where nondeterministic computations are involved [22].

Several models of relative computability of partial functions were around in those years, including: Kleene’s relative computability of partial functions [64]; Sasso’s T-degrees of partial functions (cf. [84], and Sasso’s survey paper [85]); Davis’ WT-degrees of partial functions [46, final chapter]. In addition to these models, Rogers [79] observed that, via identification of partial functions with their graphs, e-reducibility on sets of numbers, as formalised in [50], can be used to provide a model of relative computability of partial functions equivalent to Kleene’s. Myhill’s clarification in [74] led to a full understanding of the fact that in this sense e-reducibility is the most comprehensive model of relative computability of partial functions, and can be viewed as the most comprehensive model of the informal notion of relative enumerability of sets of numbers. Enumeration reducibility has also the nonnegligible advantages of a great simplicity and an extreme elegance.

Figure 6.

Left: Barry in Slaveykov Square, Sofia, Bulgaria, 2008. Right: Barry gives a keynote lecture at Logic Colloquium 2009 in Sofia, Bulgaria; picture taken on 5 August 2009.

It is important to observe that all the above models of relative computability using partial information embed the Turing degrees, which correspond to the total degrees (i.e., degrees containing some total function), via the embedding ${deg}_{T} (A) \mapsto deg (c_{A})$ .

If e-reducibility was a special interest of Barry’s, within the field he was specially keen on:

density/minimality: Turing reducibility and almost all of the most popular reducibilities have minimal elements, including Sasso’s reducibility, [84];

investigation of the local structure: to investigate the e-degrees below the first enumeration jump, which coincide with the $Σ_{2}^{0}$ e-degrees;

the Turing degrees viewed as a substructure of the e-degrees: to prove theorems for e-degrees that extend, recapture in the wider context, and yield as a special case, phenomena already known in the Turing degrees;

strong positive reducibilities: to investigate similar density, minimality and local structure questions for strong positive reducibilities (i.e., reducibilities $⩽_{r}$ contained in e-reducibility), in particular for the ones (called strong enumeration reducibilities) such that $0_{r}$ consists of all the computably enumerable (c.e.) sets).

In the following, we review some of Barry’s contributions to the field, with reference not only to Barry’s papers, but also to some of the many papers in the literature which would not have appeared without Barry’s work.

3.2. Minimality and density in the enumeration degrees

The first problem tackled by Barry in the field was the minimal degree problem. Two curious research announcements in a same issue of the Notices of the American Mathematical Society 1971, show the extent to which the minimality problem was popular in the early 1970s: Gutteridge announced that the partial degrees are dense; on the next page Barry announced that there is a minimal partial degree. (Although contradicting each other, we now know that these two claims are both false, as is clear from what we observe later.) This shows that initially Barry strongly believed in the existence of minimal e-degrees, probably motivated by what happens in the Turing degrees where every degree has continuum many minimal covers, and so continuum many minimal Turing degrees exist.

That the e-degrees do not have minimal elements was eventually proved by Gutteridge in his Ph.D. thesis [55] written under the supervision of Lachlan.

So the problem was settled, but as we shall see, Barry was still intrigued by it.

The early 1980s. After a few years leave from mathematics for politics, Barry came back to research in the early 1980s, when he decided to give e-reducibility the space it deserves in recursion theory, and so he set things into motion.

Barry’s 1982 and 1984 JSL papers: Partial degrees and the density problem, Part I and Part II. Barry squared accounts with non-minimality, and published a paper (based on some handwritten notes by Sasso from around 1972) which clarified the situation once and for all:

Theorem 3.1.
There is no minimal e-degree [ 18 ].

Very influential (surely read by all e-degree addicts), masterly written, the paper does justice to Gutteridge’s ingenious argument. The paper turned out to be even more useful since Gutteridge did not publish any paper from his dissertation.
Theorem 3.2.
The $Σ_{2}^{0}$ e-degrees are dense [ 19 ].

This is a less known paper, not easy to read, due also to Barry’s unconventional way to present proofs and constructions. The proof is very clever (finite injury along true stages) and is the paradigm of many later investigations on density in the e-degrees (e.g., Lachlan and Shore’s generalisations of density to other classes of e-degrees in their [66]).

Figure 7.
Left: Preparations for the conference picture at TAMC 2009 in Changsha, China; picture taken on 19 May 2009 by Peter van Emde Boas. Right: Barry with Leslie Valiant at TAMC 2009 in Changsha, China; picture taken on 19 May 2009 by Peter van Emde Boas.

The e-jump operation. In the 1984 paper, Barry (acknowledging McEvoy’s help for this) introduced a jump operation (called the e-jump) in the e-degrees: If ${Φ_{e} : e \in ω}$ is an acceptable listing of the e-operators then for every set A define $K (A) = {x : x \in Φ_{x} (A)}$ , $J (A) = K (A) \oplus \overline{K (A)}$ (where the second addendum denotes the complement of $K (A)$ ); finally let ${deg}_{e}^{'} (A) = {deg}_{e} (J (A))$ : this operation on e-degrees commutes with the Turing jump under the embedding of Turing degrees into the e-degrees. (Curiously, in a first draft of the paper, Barry had proposed ${deg}_{e}^{'} (A) = {deg}_{e} (\overline{K (A)})$ , i.e., the operation that is now called in Madison the skip operation.) Having a jump allows one to talk about jump classes (low, high, etc.), and brings attention to the local structure $D_{e} (⩽_{e} 0_{e}^{'})$ , which partitions the collection of the $Σ_{2}^{0}$ sets. The total e-degrees below $0_{e}^{'}$ correspond to the $Δ_{2}^{0}$ Turing degrees. The $Π_{1}^{0}$ e-degrees correspond to the c.e. Turing degrees.

Open questions raised in [ 19 ]. The 1984 paper on density contains four questions, all successfully worked out by e-degree theorists in future papers. In particular:

It suggested an analogy between the c.e. Turing degrees and the $Σ_{2}^{0}$ e-degrees, asking whether the two structures are elementarily equivalent. This was a very successful and fruitful question. It was solved by work done in Ahmad’s thesis [2]: embedding the diamond [3], the existence of join-irreducible elements, and the discovery of the so-called Ahmad pairs [4], very important in later developments. Ahmad pairs have turned out to be a distinguishing ingredient of a decision procedure for the extension of embedding problem (for partial posets) relatively to $D_{e} (⩽ 0_{e}^{'})$ [67], and were also used by Kent [62], to interpret true first order arithmetic in the $Δ_{2}^{0}$ e-degrees, undecidability of the $Π_{3}$ theory of $D_{e} (⩽ 0_{e}^{'})$ , and other related questions.

It invited to study the jump classes in the local structure. This topic has become very successful by work of Harris [59], and Ganchev and Soskova who have recently proved in [53] that all jump classes are first order definable.

It asked to clarify the context of various subclasses ( $Π_{1}^{0}$ , $Δ_{2}^{0}$ , total e-degrees, etc.) of the $Σ_{2}^{0}$ e-degrees within the local structure. This task was taken up by Barry himself and his early students. (Later on, Ganchev and Soskova proved definability of the total e-degrees in the local structure [52].)

Figure 8.
Left: Conference dinner at TAMC 2009 in Changsha, China; picture taken on 21 May 2009 by Peter van Emde Boas. Right: Barry on a rainy post conference tour for TAMC 2009 in Zhangjiajie nature park; picture taken on 23 May 2009 by Peter van Emde Boas.
3.3. Barry’s work with his student Kevin McEvoy

The 1984 paper started a period of intensive work, lasting until the end of the 1980s, with an emphasis on the e-degrees below $0_{e}^{'}$ . Barry supervised McEvoy’s thesis The Structure of the Enumeration Degrees [72]: extremely well written, the thesis set the standard of most of today’s terminology and notation in the field. It gave a proof that e-reducibility is nondeterministic Sasso’s relative computability of partial functions. McEvoy and Cooper’s paper On minimal pairs of the enumeration degrees [73] (based on McEvoy’s thesis) addressed several issues concerning the local structure: it characterised lowness, clarifies delicate issues regarding approximations, investigates the distribution of minimal pairs in the high/low hierarchy, provides lattice embeddings, and, again, raised (implicitly or explicitly) a number of open questions.

3.4. Barry’s work with Copestake: The properly $Σ_{2}^{0}$ e-degrees

A natural question to ask is if there are $Σ_{2}^{0}$ e-degrees which are not $Δ_{2}^{0}$ : in other words, are there properly $Σ_{2}^{0}$ e-degrees? In [45] (based on Copestake’s 1987 thesis, The Enumeration Degrees of $Σ_{2}^{0}$ Sets [44]) Copestake and Cooper get in working order the properly $Σ_{2}^{0}$ -strategy, and use it in difficult constructions (e.g., to build properly $Σ_{2}^{0}$ e-degrees that are: high, or quasi-minimal, or set 1-generic). The paper brought attention to the downwards properly $Σ_{2}^{0}$ (no nonzero e-degree below it contains $Δ_{2}^{0}$ sets), and upwards properly $Σ_{2}^{0}$ e-degrees (no incomplete e-degree above it contains $Δ_{2}^{0}$ sets), and gave (as a corollary of a much stronger result) a proof that there are $Σ_{2}^{0}$ e-degrees which are both downwards-properly $Σ_{2}^{0}$ and upwards-properly $Σ_{2}^{0}$ .

These notions (thoroughly studied by Harris in [59]) are intimately connected with the jump classes. Sometimes they are implied by familiar algebraic properties (all shown to be nonempty), e.g., for e-degrees,

the property of being downwards properly $Σ_{2}^{0}$ is implied by the property of being noncuppable [42], and by the property of being nonbounding [38];

the property of being upwards properly $Σ_{2}^{0}$ is implied by the property of being nonsplitting (that is incomplete and such that no pair of bigger incomplete e-degrees join to $0_{e}^{'}$ ), see [94], and [7].

Recently Ganchev and Soskova [51] have proved that the downwards properly

Σ_{2}^{0}

e-degrees, and the upwards properly

Σ_{2}^{0}

e-degrees, are first order definable in the local structure.

3.5. Minimal covers (the best one can do) and the 1987 paper

In 1987, Barry published the paper Enumeration reducibility using bounded information: Counting minimal covers, [20]; it combined the old interest in minimality and density with another special interest of Barry’s, namely strong positive reducibilities. His student Phil Watson investigated the structure of the s-degrees inside $Σ_{2}^{0}$ e-degrees in his Ph.D. thesis [102], and in [101]. These topics were later taken up again and further clarified by Kent [63], and Barry’s student Charles Harris in a series of publications including [56] (his Ph.D. thesis), [57], and [58].

If one looks at Gutteridge’s non-minimality proof, one sees that if B is an e-minimal cover of A, then B is $Δ_{2}^{0}$ in A: so minimal covers are very rare in the e-degrees, in fact every e-degree may have at most countably many minimal covers. Barry gives a sufficient condition for this to hold of any strong enumeration reducibility $⩽_{r}$ . In particular he singles out the notion of an anticompact e-operator:

Theorem 3.3.
If there is an anticompact r-operator then each r-degree has at most countably many minimal covers.

An example of an anticompact e-operator is what Barry calls the Slaman operator, [20, Example 2.8], suggested by Slaman when Barry was visiting the University of Illinois at Chicago during 1985–1986: most of the work on minimality and density for strong positive reducibilities, as well as on properly $Σ_{2}^{0}$ e-degrees was carried out or initiated while Barry was visiting Chicago.

Figure 9.
Left: Barry at CiE 2009 in Heidelberg; picture taken on 19 July 2009 by Peter van Emde Boas. Right: Barry at the London Marathon 2010; picture taken on 25 April 2010.

On the contrary, minimal covers may abound in the so-called combinatorially compact strong enumeration reducibilities, like in s-reducibility:
Theorem 3.4.
There are continuum many minimal covers of $0_{s}^{'}$ (the s-degree of the complement $\overline{K}$ of the halting set).

Once it was clear that there is no minimal e-degree, Barry still believed in the existence of a nontrivial linearly ordered initial segment, which in a structure without minimal elements is perhaps the closest phenomenon to minimality one can think of. This conjecture had the merit of motivating lots of research clarifying the issue of how density can be combined with incomparability (cf., e.g., [96] and [90]): eventually it was shown in [90] that no such linearly ordered initial segment exists.
3.6. The 1990 survey paper

In the 1987 paper [20], Barry also introduced a new complicated technique, called celling, to prove non-density in e-degree: a few years later, using this technique, in his important survey paper [22], Enumeration reducibility, nondeterministic computations and relative computability of partial functions (proceedings of an Oberwolfach meeting), he sketches a proof of the existence of a minimal cover in the $Σ_{6}^{0}$ e-degrees. Unfortunately there was going to be no follow-up to this sketch, since in 1996 Calhoun and Slaman, [10], exhibited a minimal cover in the $Π_{2}^{0}$ e-degrees.

Despite a few incorrect claims, or a couple of insufficient sketched proofs, the 1990 paper was extremely influential, exhaustive, and with many beautiful open questions, some of which are still waiting for a solution. Solutions to two of these problems (definability of the e-jump by Kalimullin [61], and, inherited from the 1967 book by Rogers [79], definability of the total degrees by Cai, Ganchev, Lempp, Miller, and Soskova [9]) can be viewed as some of the most important achievements in the subject.

The paper raises twenty-one open problems, of which (at least) eight have been solved.

3.7. The Turing degrees inside the e-degrees

Barry viewed the e-degrees as the “right” degree structure: the Turing degrees were just a part of it. Most of his projects in the local structure (noncupping, noncapping, nonbounding) always started with the goal that there should be a $Π_{1}^{0}$ e-degree (hence a c.e. Turing degree inside the e-degrees) with some desired property, thus proving something in the local structure of the e-degrees that yields immediately a corresponding result in the c.e. Turing degrees. As evidence of this attitude, he was extremely pleased with the following theorem [95] that stretches to its limit in the wider e-degree context a classic in the c.e. Turing degrees (the well known theorem stating that there is an incomplete c.e. Turing degree such that no two bigger incomplete c.e. Turing degrees join to $0_{T}^{'}$ ):

Theorem 3.5.
There is a $Π_{1}^{0}$ e-degree $a <_{e} 0_{e}^{'}$ such that there are no b , c with $b \in Π_{1}^{0}$ and $c \in Σ_{2}^{0}$ such that $a ⩽_{e} b, c <_{e} 0_{e}^{'}$ and $b \cup c = 0_{e}^{'}$ . (Also there is a $Π_{1}^{0}$ such that no two incomplete $Δ_{2}^{0}$ ones above it join to $0_{e}^{'}$ .)

3.8. The Arslanov, Cooper and Kalimullin 2003 paper

We conclude with an anecdote to illustrate how many things started from Barry, and his work. When he visited Siena 1989, he worked very hard with myself on a couple of smaller projects on join-reducibility. One of them was to show that every nonzero total $Δ_{2}^{0}$ e-degree is join-reducible. Although this project temporarily failed, it had a fortunate butterfly effect, as successive efforts by Arslanov, Cooper and Kalimullin came eventually to a positive solution, [6]: they show in fact that every nonzero total e-degree (not just the $Δ_{2}^{0}$ ones) is the top of a diamond with bottom $0_{e}$ . The proof makes use of properties of semirecursive sets (discovered by Jockusch), which later led Kalimullin to discover what have been called Kalimullin pairs, successfully used to prove important results including definability of the e-jump, and definability of totality.

4. Alexandra Soskova: Barry Cooper and the Sofia logic school

I will never forget Barry Cooper, a fantastic person, an ingenious scientist and a very good friend. In this article, I should like to pay tribute to the great impact he had on the development of the Sofia logic school.

Barry visited Bulgaria for the first time in September 1988. He was invited to participate in the second of our Logic Biennials, the Summer School and Conference on Mathematical Logic called Heyting ’88 [76]. The goal of these events was to bring together prominent logicians from the West and the East. At that time, Bulgaria was still under a socialist regime and travel outside the iron curtain was almost impossible for us. However, it was possible and in fact easy for logicians from all over the world to travel to Bulgaria. Thus, this was a fantastic opportunity for us to meet in person many people who we knew only from their papers, books and theories. Dimitar Skordev and Petyo Petkov were the main organisers of these events, but the whole project was instigated by the postgraduate students in logic at Sofia University, in particular Solomon Passy and Lyubomir Ivanov, courageous enough to ignore the potential risks for their careers that came with inviting westerners. Barry came with his student Kate Copestake. She had just received her doctoral degree under his supervision at Leeds University and this was her first talk at an international conference. I was still a doctoral student and this was also a first for me: my first talk in English in front of so many famous people. So Kate and I became very good friends, bonding over our shared stage fright. Barry was very kind to us, constantly reassuring us.

Figure 10.

Left: Barry at WCT 2011, San Francisco, U.S.A., March 2011. Right: Conference picture of CiE 2011 in Sofia, Bulgaria, June 2011.

The evenings in Varna were filled with many fascinating discussions about mathematical logic, its history and future and sometimes about politics. It was then that Robin Gandy gave a speech, in which he expressed his negative views on communism and the totalitarian regime. Every participant remembers his words vividly until this day, especially the organisers, who were aware of the dangers of free speech at the time. This speech sparked much discussion; Barry – while disapproving and condemning our lack of freedom – remained true to his communist beliefs.

Barry was enthusiastic about Bulgarian culture. He told us about his interest in music and so Mitko Yanchev, who shares this passion, introduced him to Bulgarian folklore and Bulgarian jazz music. Barry was tolerant about the imperfections in our country. In later years, when we reminisced about these times, he would fondly remember searching for an English-Bulgarian dictionary. The only one he could find in a bookstore in Varna was a two-part edition, one containing words from A to L and the second containing words from M to Z, however the bookstore only had the first part. After the conference was finished, he traveled to Veliko Tarnovo and there in a bookstore he found a similar situation, except this time the only available part was the second one.

During that meeting in 1988, Barry became a friend of the Sofia Logic Group and after that, we knew we could count on his unwavering support. In 1990, he joined the programme committee of the third Logical Biennial called Kleene ’90. This was a challenging time for us, just a few months after the fall of the Berlin wall and with it the socialist regime in many countries, including Bulgaria. Many of the logicians in our group became more interested in politics. Solomon Passy and Lyubomir Ivanov founded the Green Party in Bulgaria and were elected to the new democratic parliament. Barry’s input on these matters was extremely valuable to us. The next few years were poor years for Bulgarian logicians, however we maintained contact with Barry as much as possible and with his support, one of our students, Vladimir Soskov, could attend the Logic Colloquium 1997 in Leeds.

Figure 11.

Left: Barry receives the degree of Doctor Honoris Causa at Sofia University, Bulgaria, October 2011. Right: Barry’s note of gratitude in the Book of Honour of Sofia University, October 2011.

In 2003, Barry contacted us with a proposal. He had come up with the idea of establishing an European science network of people working in computability with the following nodes: Leeds, Amsterdam, Athens, Barcelona and Lisbon, Heidelberg, Munich, Novosibirsk, Oslo, Prague, Siena, Swansea. The name of the network was going to be Computability in Europe (CiE). He invited the Sofia logic group to be part of the network as a subnode of Athens, partly because at the time Bulgaria was not yet an EU member, only an associated country. Barry’s idea was to apply for funding under the Marie Curie Research Training Network program. We saw this as an exciting opportunity and were grateful to be included. This invitation was very stimulating for the whole group, as it motivated us to concentrate on our research and prove that we would be a useful participant in the network.

Even though the attempts to obtain funding from the European Commission for this project were ultimately not successful, the CiE network was established along with a series of annual conferences. The first CiE conference was organised in Amsterdam in 2005 and that is where we met Barry once again.

Barry’s idea for a network on computability was realised in a different way. A proposal for a smaller scale network focused on research training in logic and with fewer nodes – Leeds, Lyon, Munich and Manchester – was successful and the EU Marie Curie Early Stage Training program MATHLOGAPS (Mathematical Logic and Applications), was established in 2004. At the time we had a strong master’s program “Logic and Algorithms” and four of our students were accepted to continue their training within this program: Mariya Soskova obtained a three-year fellowship based at Leeds, Trifon Trifonov and Bogomil Kovachev obtained three-year fellowships based in Munich and Hristo Ganchev obtained a three-month scholarship, based in Leeds. Three of these students are now associate professors at Sofia University, and one of them served as a Vice Dean of the Faculty. In 2012, Stefan Vatev spent five months in Leeds under Barry’s supervision as a fellow of the program MALOA, the successor of MATHLOGAPS. Stefan Vatev is currently a chief assistant professor at Sofia University. So, in fact, Barry is responsible for the training of a very large portion of the younger members of our department.

During Mariya’s three years at Leeds University, the bond between Barry and the Bulgarian logic group grew tighter. We met every year at the annual CiE conference, which always had a large group of participants from Bulgaria. Ivan and I visited Leeds and presented our work at the Leeds Logic Seminar. Barry was a great host, he invited us to his home and took us on a trip to Whitby.

In 2006, on one such visit, right after the CiE conference in Swansea, Barry and Michael Rathjen suggested that Sofia University host the Logic Colloquium. We had very little experience with conference organisation and had never organised a conference of this size. Barry strongly encouraged us since he had a vision for the development of Sofia University as a recognised center in logic and knew that such an event would, in his words, “put Sofia back on the logic map”. We anxiously agreed to this and started planning for Logic Colloquium 2009. Only a year later in Siena at CiE 2007, one of the most exciting meetings for us, Barry, Benedikt Löwe and Dag Normann convinced us to organise a second large conference, CiE 2011. It was a very strategic move on their part to ask us so early, as at the time we were not aware of how much work we were committing to.

In 2008, after CiE 2008 in Athens, right around the time Mariya was finishing her doctoral degree, we invited Barry to visit Sofia and were so happy to be able to return the hospitality that he had showed us. When he got to Sofia we started working on a joint proposal to fund a new project: “Computability with Partial Information”. For the first time in our academic life, the Bulgarian National Science Fund had opened a call to fund scientific research projects. Prior to that we had very little means to fund academic travel and no possibility to pay for visitors to come to Sofia University. The upcoming conferences, that we had agreed to host, presented us with funding problems as well. We also had no experience with writing proposals for funding, and so Barry’s help was essential to our success. Right before Christmas in 2008, we received the happy news that our application was approved. The project’s goal was to continue our collaboration with the computability group at Leeds, represented by Barry and his students and the computability group in Siena, represented by Andrea Sorbi and his students.

It funded a series of research visits between these three centers, as well as our participation at many academic events: CiE 2009 in Heidelberg, CiE 2010 in Ponta Delgada, Logic Colloquium 2010 in Paris and Logic Colloquium 2011 in Barcelona. The project was extremely beneficial to our research. During this time, Hristo and Mariya solved two questions from Barry’s famous 1990 paper on enumeration reducibility: they characterised the complexity of the local theory of the enumeration degrees and proved the first order definability of the total enumeration degrees in the local structure of the enumeration degrees. Just as importantly, the project provided us with a large portion of the necessary funds for the organisation of Logic Colloquium 2009 and CiE 2011.

Logic Colloquium 2009 was a very successful meeting [92]. Barry was an invited speaker and delivered a fascinating lecture entitled “Definability in the Real Universe”, generously acknowledging Dimitar Skordev’s contribution to the early development of the subject to a very wide audience (cf. Fig. 6). Mariya had the idea of organizing a further workshop on computability theory as a satellite event and through this we were able to attract a great number of computability theorists, including Julia Knight, Marat Arslanov, Sergej Goncharov, Noam Greenberg, Joe Miller, Antonio Montálban, Andy Lewis-Pye, and Charles Harris who later also became our collaborators.

Figure 12.

Left: Announcement of Barry’s Turing Lecture as part of the Alan Turing Year in China 2012; picture taken on 20 May 2012 by Peter van Emde Boas. Right: Barry announces the next TAMC venue at TAMC 2012 in Beijing, China; picture taken on 21 May 2012 by Peter van Emde Boas.

The satellite meeting was well accepted by the computability community and Barry encouraged Mariya to transform it into a series. His enthusiasm for this workshop series was contagious and he did not try to take over the steering of the workshop series, as he believed that it was important that the younger members of the community take charge of this series, but gave much valuable advice when such was needed. And so the Workshop in Computability Theory series was initiated and has been ongoing ever since, with workshops in Ponta Delgada (2010), Paris (2010), San Francisco (2011), Barcelona (2011), Chicheley Hall (2012), Prague (2014), Bucharest (2015), and, most recently, Ghent (2016). Barry participated in the organisation of two of these workshops – the one at Chicheley Hall and the one in Bucharest.

The experience we gained during the organisation of the Logic Colloquium proved to be very valuable and in 2011, we were ready to host the conference Computability in Europe (cf. Fig. 10). This was a special honour for us, as we were aware that we owed a lot of our success to our participation in the network CiE.

On 27 October 2011, Sofia University awarded Barry the honorary degree of Doctor Honoris Causa for his contribution towards and support of the development of Bulgarian mathematical logic (cf. Fig. 11). During the formal award ceremony, Barry gave an academic lecture entitled “Computing in an Incomputable World” and wrote in the Sofia University Book of Honour and wrote the following:

I am very grateful to Sofia University for this great honour. I have a special regard and affection for this historic seat of learning and am very happy to be with academic friends and colleagues on this auspicious occasion. My area of research – the theory of computability – has an important history in Bulgaria, being part of the early history of the computer. Thank you. S. Barry Cooper, 27th October 2011.

After the ceremony, the Bulgarian logicians celebrated with Barry at the research center in Gyulechica in the Rila mountain range, where we had organised a small conference in his honour (cf. Fig. 15).

In the next few years Barry was extremely busy with the many events that he organised in honour of Turing’s centenary. He would start every email to us with the phrase “I am swamped”. Yet, he made sure that we were included in the celebration, inviting us to participate in the Isaac Newton Institute programme “Semantics and Syntax: A Legacy of Alan Turing” in Cambridge and its major workshop “The Incomputable”, organised by himself and Mariya. And even though Barry was so overwhelmed with work, he still managed to support Bulgarian research as an expert in our government funded project for training graduate students and young scientist in our faculty, and later on as a PC member for the doctoral conference “Mathematics, Informatics and Education 2014” in Sofia.

Figure 13.

Left: Barry with Joost Joosten at CiE 2012 in Cambridge; picture taken on 19 June 2012 by Peter van Emde Boas. Right: Barry with Piergiorgio Odifreddi and Paola Bonizzoni at CiE 2013 in Milan, Italy, July 2013.

When Ivan Soskov passed away in 2013, Barry was the first friend that I called. He helped us by spreading the sad news among logicians worldwide. His words about Ivan in an article that Stela Nikolova wrote for the journal Computability [75] were special to us:

Ivan was a man with a mission, it seemed to his friends and family. And the mission was to look after you. He was on your side… He knew the world was a dangerous (and wonderful) place. Walking the earth with Ivan was a very real and rewarding experience. Because he cared about the real things…

Barry was a very good friend indeed.

In the autumn of 2014 we organised a conference in memory of Ivan Soskov, once again in Gyulechica (Figs 16 and 17). Barry, Andy Lewis-Pye, and Yiannis Moschovakis, came to honour Ivan’s memory. The conference was a very special event. Barry’s talk was entitled “Some Things Happen for No Reason”. This was a quote from Robin Gandy, and the talk discussed the relevance of higher order computation, and definability over structures involving relative computation. He said very warm words about Ivan and the Sofia Logic school.

One of our last memories with Barry was a very happy one. He joined us in celebrating the wedding of Mariya Soskova and Joe Miller on 16 May 2015 (cf. Fig. 17). Mariya and I thought of Barry as part of our family. His wedding gift was a copy of his book “Alan Turing: His Work and Impact”, an accomplishment he was extremely proud of. On the next day on his way to Singapore he wrote: “… still smiling from a very Bulgarian evening, in all the best senses”.

When I heard that Barry had a terminal illness, I immediately bought a ticket to visit Leeds, because I wanted very much to see him and offer my support to his family. Unfortunately I was too late, I missed him. I shall always remember the moments that I spent with Barry, they too were always “a very real and rewarding experience”. Barry was an amazing person, generous, charismatic and beloved by so many people. His impact on our lives, both academically and personally, is enormous. The world is not the same without him.

5. Mariya I. Soskova: S. Barry Cooper

Figure 14.

Left: Barry with student at CiE 2013 in Milan, Italy, July 2013. Right: Dinner of the CiE conference series steering committee at CiE 2013 in Milan, Italy, July 2013 (from left to right: Viv Kendon, Peter van Emde Boas, Mariya Soskova, Barry, Benedikt Löwe, Arnold Beckmann, Nataša Jonoska).

On October 26, 2015, we lost an extraordinary scholar, mentor, and friend. It is a difficult task to tell the full story of his life and I do not claim to have come even close to it. Rather, I hope to tell a small fraction of this story as I have learned it through our many conversations and through the many wonderful articles and dedications that people wrote after his death, focusing inevitably on what I understand best, his mathematical work in computability theory.

Barry Cooper grew up in Bognor Regis. His mother Edna, with whom he maintained a close relationship until her passing in 2006, ran a grocery shop. His father Richard was a cabinet maker. Barry attended the Chichester High School for Boys and there he formed lasting friendships with a number of classmates. Some of them were with him on the last day of his life, telling stories about their mischievous boyish adventures in a typically humorous way, a trademark for the “Bognor boys” (cf. Fig. 1). It was then that I learned that Barry played scrum-half for the under-16s England rugby team, that he stood up to bullies, and that he had the courage to fight for his rights when faced with the kind of injustice that boys in school might face. His friends spoke of him with respect, recalling his creativity and sense of fun. The school alumni society, the Old Cicestrians, called Barry “one of our most prestigious Old Boys” and told a story from his high school days: “Once, he made himself especially popular with his classmates by setting off the school bell via a battery-powered switch in his desk so that lessons finished earlier.”

Barry Cooper won a scholarship to read mathematics at Jesus College in Oxford. Upon his graduation in 1966, he decided to pursue a doctoral degree in Logic at Leicester under the supervision of Reuben Goodstein. In Leicester, he became interested in computability theory, and specifically degree theory. Computability theory studies the limits on what problems can be solved using an algorithm. It has its roots in Alan Turing’s seminal 1936 paper [99], in which he introduced Turing machines to give a precise mathematical meaning to the term “algorithm”, used informally until then. Post [77] introduced a reducibility between sets of natural numbers, based on an extended model of Turing machines, giving rise to a structure that is ordered with respect to information content, the structure of the Turing degrees. The study of structures of this type is now called degree theory. Even though this field began in the United Kingdom, when Barry was a student, most of the exciting breakthroughs in it were done by researchers in North America. Barry quickly absorbed highly advanced works by Lachlan, Rogers, Sacks, Spector, and others, going far beyond the expertise that his supervisor could offer him. It was decided that in his final year he would move to Manchester and work with Mike Yates, the only established researcher in the United Kingdom in degree theory, who became his second supervisor. Barry wrote an impressive thesis, entitled “Degrees of unsolvability”, consisting of five fully formed papers. In later years, he would proudly tell me how he just stapled these five papers together and submitted the resulting manuscript as a thesis, but that I should under no circumstances follow his example. If one looks at the page numbering in his thesis, this story checks out.

Mike Yates was an academic descendant of Alan Turing, through Turing’s only student, Robin Gandy. His work in computability theory had been largely influenced by Post’s program: to find a natural example of a computably enumerable degree that is neither the least degree (that of computable sets), nor the greatest one (that of the halting problem), by isolating an appropriate combinatorial property. In the 1960s, he expanded his interest to initial segments of the Turing degrees, and in particular the distribution of minimal elements in the structure. Minimal degrees were first constructed by Spector [97], using the method of forcing with trees. This method is powerful and important, but crude in the sense that the objects it produces are complex and require a strong oracle to be computed. Sacks [80] improved the method to produce a minimal degree computable from the degree of the halting problem, $0^{'}$ . Yates [104] invented the full approximation method, which allowed him to greatly limit the power of the oracle: he showed that every nonzero computably enumerable degree computes a minimal degree. The question that he gave Barry to work on for his thesis was the following: Are there two minimal degrees whose least upper bound is $0^{'}$ ? Barry later recalled many meetings with his supervisor at which he would be excited to share his solutions to problems he had stumbled upon in his work. He found a solution to a problem of Sacks related to upper bounds of uniform sequences of c.e. degrees [13] and showed that the difference hierarchy does not collapse [11]. Yates would always respond kindly, and with interest, however at the end of the meeting, he would insist on getting an answer to his original problem. Finally, Barry [12] was able to show that, in fact, there are such minimal degrees, thereby generalizing an earlier result of Shoenfield [87]. In his review of the paper, Shoenfield describes the method that Barry used: “The proof combines Spector’s technique of constructing minimal degrees with the priority method in a very complicated way” [88].

Barry’s most celebrated theorem from his thesis combines the method of full approximation with jump inversion. The jump is a monotone operator that maps a degree to a strictly higher one; it is obtained by relativizing the halting set. Friedberg’s jump inversion theorem [49] proves that every degree greater than $0^{'}$ is in the range of the jump operator, thus every degree that could possibly be the jump of a degree is the jump of some degree. Shoenfield [86] showed a similar local version of this theorem: if one restricts the jump operator to the degrees below $0^{'}$ then the image consists of all degrees of sets that are c.e. in and above $0^{'}$ . Barry [15] showed that one only needs to consider minimal degrees in order to achieve every possible jump: every degree above $0^{'}$ is the jump of a minimal degree. On the other hand, he showed that the expected analog of the local jump inversion theorem fails, as no minimal degree below $0^{'}$ has jump $0^{″}$ . This left an interesting problem open: how can one characterise the degrees that are jumps of minimal degrees in the local structure of the Turing degrees? Many researchers have since tried to tackle this problem, slowly achieving progress towards its solution. Sasso proved the existence of a minimal degree a that does not have the property that $a^{'} = a \lor 0^{'}$ [83], in contrast to all degrees used for the proof of Friedberg’s jump inversion. In the same paper, he outlines an idea of Barry Cooper, Richard Epstein, and himself, giving an example of such a minimal degree below $0^{'}$ . Jockusch and Posner showed, on the other hand, that every minimal degree a has least possible double jump: $a^{″} = {(a \lor 0^{'})}^{'}$ [60]. In particular, all minimal degree below $0^{'}$ are ${low}_{2}$ . This shows that the jump of a minimal degree below $0^{'}$ must be a degree of a set that is c.e. in, above, and low with respect to $0^{'}$ . The question now becomes, can all degrees with these three properties be realised as jumps of minimal degrees below $0^{'}$ ? Downey, Lempp, and Shore showed that the answer to this question is also negative, so the range of the jump operator on minimal degrees below $0^{'}$ cannot be characterised in terms of jump classes of degrees recursively enumerable in and above $0^{'}$ [47]. In 1996, nearly 30 years after he had stumbled upon this problem, Barry finally gave a complete solution [28], a dynamic characterisation of the degrees that comprise the range of the jump operator restricted to the minimal degrees in the local structure: the almost $Δ_{2}^{0}$ degrees. This story illustrates the kind of mathematician Barry was becoming: unafraid to engage in technically complicated work, interested and persistent in the pursuit of answers, even when they took years to find, and creative in expanding the known methods.

In 1969, Barry was appointed as a lecturer at the University of Leeds. This happened, in fact, before he defended his thesis, in 1971. He remained in Leeds throughout his career, except for a few sabbaticals and invited visits abroad, becoming a professor of pure mathematics in 1996.

Barry spent the years 1971 to 1973 as a lecturer in mathematics at the University of California at Berkeley, supported by a Fulbright scholarship (cf. Fig. 1). This was a very important time for him in many ways and he would very often reminisce about it. Mathematically he was thriving; he collaborated with Richard Epstein, then a graduate student working under the supervision of Robert W. Robinson on the full approximation method for constructing minimal degrees. Barry developed further the results from his thesis, concentrating on the interactions between the jump operator and the local structure of the Turing degrees. In 1972, he introduced the jump hierarchy [14], a hierarchy of degrees based on the strength of their jumps, which is very widely used today. (Soare [91] introduced this hierarchy independently in 1974.) He also developed and incorporated a new method in his investigations: the method of high permitting. Using this method, he showed that every high degree has a minimal predecessor [15] and that every high c.e. degree bounds a minimal pair [16]. The high permitting technique was further developed by Shore and Slaman [89], and played an important role in the separation between different levels of the jump hierarchy by first order definable properties.

It was in Berkeley that Barry’s vision for an open and inclusive community of scientists interested in computability theory began to crystalise. Degree theory was confined mainly to researchers in the United States of America and at that time, when travel and communication was not as easy as it is today, this meant that developments were slow to filter to the rest of the community, especially to people living beyond the iron curtain. In 1972, Barry and Richard Epstein founded the Recursive Function Theory Newsletter and became its first editors. The purpose of this newsletter is best explained by Barry himself:

The original aim, which was maintained for over twenty years, was to provide, for the increasingly far-flung recursion theoretic community, access to the latest developments in the subject. The ideals and enthusiasm behind the Newsletter were characteristic of that period. It was to be free, both to receive and to contribute to, essential for those from the then Soviet Union, Eastern Europe, P. R. of China, etc. It was to be informal, and denied to libraries (there were a number of requests), to encourage researchers to share information while fresh and in provisional form. It was to be open to contributors from all strands of the subject [29].

This philosophy was crucial in many of Barry’s later initiatives and should be quite familiar to the members of the association “Computability in Europe”. The newsletter remained active until 1997 and included a total of nearly four-hundred research announcements by more than two-hundred contributing members, including Epstein, Jockusch, Yates, Lachlan, Soare, Harrington, and Sacks. Barry was also an active contributor, with at least one or two announcements in every issue of the newsletter, including a piece especially useful for welcoming researchers into the field, the annotated bibliography for the structure of the degrees below $0^{'}$ with special reference to that of the recursively enumerable degrees [17].

In Berkeley, Barry deepened his passion for music and literature. He would spend long hours in Moe’s bookstore and in record shops, such as Rasputin Records on Telegraph Avenue. It is probably in these record stores that he started his immense collection, which took up more than a full wall in his home in Leeds. When we visited San Francisco for the Workshop in Computability Theory (WCT) in 2011 (cf. Fig. 10), Barry was excited to show me his favorite places: Haight-Ashbury and the record store Amoeba Music, founded by former employees of Rasputin Records. Barry’s love for music lasted his whole life: in 1984 he became a founding member of Leeds Jazz and an active member of the more experimental Termite Club. A fellow jazz enthusiast, Bill White, wrote in a letter to the Guardian:

For many years I knew the mathematician Barry Cooper solely as an avid jazz fan. At that time, we regretted that when high-profile performers visited Leeds at all, it was for late-night performances. Barry marched to a different drum from most people – he actually did things. One night he rang to tell me that he had accessed some funding, and a meeting in a pub led to the foundation of Leeds Jazz. It lasted for more than 25 years and achieved great things. Various members came and went: some were more publicly associated with the name than Barry, but its genesis was undoubtedly the result of his determination [103].

Living in Berkeley also influenced Barry’s left-wing politics; he was fascinated by student activism and the civil rights movement. Upon his return to Leeds, Barry remained politically active. He was even a candidate in local elections for the Communist Party of Great Britain. After the 1973 military coup in Chile, hundreds of political prisoners were saved from execution by being given refuge in European countries, including the United Kingdom. Barry welcomed some of the Chilean refugees to Leeds, helping them find homes and work. He was also involved with the miners’ strike in 1984 and 1985, collecting food donations for the families of miners on strike in Leeds.

After the charm of political activism had faded, Barry returned to academic life with renewed enthusiasm and a new theme – the structure of the enumeration degrees. Enumeration reducibility was introduced by Friedberg and Rogers [50] in 1959. Like Turing reducibility, it orders sets according to their information content, however to define this ordering one only uses positive information. The natural degree structure associated with this reducibility, the enumeration degrees, is an extension of the Turing degrees and so provides a wider context for degree theory. Barry’s contribution to the study of the enumeration degrees is immense and deserves a separate detailed account, which I shall leave to his main collaborator, Andrea Sorbi (cf. Section 3).

In the Turing degrees, his focus remained on the local structures: the structure of the c.e. Turing degrees, the structure of the d.c.e. degrees and all other levels of the difference hierarchy, and of course the structure of the $Δ_{2}^{0}$ Turing degrees. The motivating force that drove this research was already clearly stated in his thesis: “We feel that we should be able to identify $0^{'}$ by some simple structure of the degrees surrounding it” [11, Chapter 3, p. 1]. This goal was now complemented by the desire to understand the distribution of the degrees among the different jump classes. The first main challenge was to find properties of a degree with respect to its neighbors that structurally distinguish $0^{'}$ from other degrees. The construction of a c.e. degree without the complementation property by Barry and Richard Epstein [30] gave one such example. Further, Barry [21] investigated the strong anticupping property, providing an example of a c.e. degree that is structurally different from every high c.e. degree. This search for a natural combinatorial property that distinguishes $0^{'}$ from the other degrees has continued to provoke interest. Most recently, the theme has been revisited in a very systematic way by a group of current and former students of Barry, lead by Andy Lewis-Pye [48,68,69].

The next big theme in local degree theory, more focused on the c.e. degrees, is the analysis of algebraic properties in terms of continuity or discontinuity. A property P is continuous if whenever P is true of a, there is an interval of degrees containing a such that P is true of all members of this interval. A longstanding open problem related to continuity, serving as additional motivation, was Lachlan’s major subdegree problem in the c.e. degrees. A c.e. degree c is a major subdegree of a c.e. degree a if $c < a$ , however this strict ordering cannot be demonstrated through cupping: every degree that cups a to $0^{'}$ also cups c to $0^{'}$ . The problem is whether every nonzero c.e. degree has a major sub-degree. The first example of a discontinuous property was given by Stob [98], who exhibited an interval of c.e. degrees where continuity of cupping fails. Barry [25] believed that understanding this phenomenon would reveal a lot about the local structure of the c.e. degrees and possibly provide a path towards identifying a nontrivial definable element. In collaboration with Xiaoding Yi [43], he showed the discontinuity of splitting in the c.e. degrees. Lachlan’s non-splitting theorem [65] and Harrington’s extension of it provided a related example of discontinuity. Splitting and non-splitting became a theme that Barry enjoyed very much both in the c.e. degrees and in the enumeration degrees. In fact, the question that Barry gave me when I started my graduate studies with him was an analog of Harrington’s non-splitting theorem for the local structure of the enumeration degrees. In the c.e. degrees, Barry together with Angsheng Li and Xiaoding Yi [35,39] investigated the distribution of Lachlan and Harrington non-splitting bases, once again in terms of his jump hierarchy. In 2008, Barry and Angsheng Li [37] finally proved that every c.e. degree has a major subdegree, tying up one of the loose ends in the study of the c.e. degrees.

Another avenue of research that Barry pursued in parallel concerned the structure of the d.c.e. degrees. A set A is d.c.e. if it is the difference of two c.e. sets. Extending this idea to any boolean combination of c.e. sets, we obtain the difference hierarchy, introduced by Putnam [78] and Gold [54]. As I mentioned earlier, Barry showed in his thesis that the corresponding hierarchy of degrees does not collapse. The difference hierarchy, therefore, gives raise to a chain of substructures sitting between the structure of the c.e. degrees and the structure of the $Δ_{2}^{0}$ Turing degrees. The structure of the d.c.e. degrees is the substructure closest to the c.e. degrees. Barry co-authored a series of papers aimed at understanding the algebraic differences and similarities between these two structures. Two properties of the c.e. degrees, both due to Sacks, were natural starting points: density [82] and splitting [81]. Barry worked with Steffen Lempp and Philip Watson [32] to show a weak form of density for the d.c.e. degrees. This result was later improved by Barry [23] to show full density for the ${low}_{2}$ d.c.e degrees. Full density, however, was shown to fail by the existence of a maximal d.c.e. degree, which was proved by a unique collaboration, involving Barry Cooper, Leo Harrington, Alistair Lachlan, Steffen Lempp, and Robert Soare [31]. The analog of Sacks’s splitting theorem was shown by Barry [24] for every level of the difference hierarchy. With Angsheng Li [33], he showed that, in contrast to the c.e. degrees, splitting cannot be combined with cone avoidance. Just as with the c.e. degrees, all of these phenomena were examined in terms of the jump hierarchy and in terms of Post’s program in a further series of articles [1,5,34,36]. A beautiful summary of all these themes and their surrounding context can be found in Barry’s chapter for the Handbook of Computability Theory entitled “Local degree theory” [26].

The collaborations described above were not easy to achieve due to Barry’s geographic isolation. Barry was determined to make the University of Leeds a center for computability theory, a hard task, given that he was the only appointed faculty member working in this field. To counteract this, Barry ensured that his group, if not constant, always had critical mass. Barry supervised many students, starting with Kevin McEvoy, who graduated in 1984, and Kate Copestake, who graduated in 1986, both working on the structure of the enumeration degrees. Barry visited the United States for a second time in the academic year 1985/86. His second sabbatical was at the University of Chicago, and this time he took along Kate and his next student, Philip Watson. In Chicago, Barry formed lasting friendships with Robert Soare and Ted Slaman, and distinguished himself as an extraordinary marathon runner (cf. Fig. 9), achieving an impressive time of 2 hours 48 minutes at the Chicago marathon. Back in Leeds, Barry was determined to maintain these academic connections and continuously applied for grants whose sole purpose was to secure funding for longterm visitors at the University of Leeds. Ted Slaman was able to spend a year in Leeds in 1993, Steffen Lempp spent eight months in Leeds in 1996. Gerald Sacks, Bob Soare, and Leo Harrington were among the many short term visitors.

The University of Leeds hosted the Logic Colloquium twice while Barry was working there. The first time was in 1979 and Barry participated in the organizing committee. The second was in 1997; this time Barry was the chairman of the program committee. The event was his first masterpiece in the art of conferences. It had his characteristic touches: a poster and two special issues published in the LMS Lecture Notes Series, one entitled “Models and Computability” and a second one entitled “Sets and Proofs”, complete with a webpage containing a bulleted list of submissions with bullets in different colors corresponding to their status. More importantly, the Logic Colloquium 1997 attracted an amazing 236 participants, including almost everyone active in computability theory. Logic Colloquium 2016 was held once more in Leeds and was devoted to the memory of Barry Cooper.

Barry continued to work towards his goal for a wide and open community of computability theorists. He coordinated a series of grants supporting collaboration with research groups from all over the world. Examples of this are the INTAS/RFBR Research Project Computability and Models, involving researchers from four West European centers (Leeds, Heidelberg, Siena, and Turin) and four centers in Russia and Kazakhstan (Ivanovo, Kazan, Novosibirsk, and Almaty), and a Royal Society/Chinese NSF joint project “New Directions in Theory and Applications of Models of Computation”, involving researchers from the United Kingdom, China, New Zealand, Singapore, the United States of America, Russia, and Italy.

In the 1990s, Barry attempted to tackle the two main open problems in global Turing degree theory: the definability of the jump operator and the automorphism problem. In 1990, he announced his definition of the Turing jump, based on a combination of Jockusch and Shore’s pseudo jump operator and a non-splitting theorem for the d.c.e. Turing degrees. This solution came with many beautiful consequences, such as the definability of the relation “c.e. in”. This lead to Slaman and Woodin’s announcement that the c.e. degree are an automorphism base for the Turing degrees, providing convincing evidence in support of their conjecture that the Turing universe is rigid. In 1997, Barry announced a surprising new achievement – he had found a way to construct a non-trivial automorphism of the Turing degrees. This result was met with great interest from the community. In 1999, Barry was invited to present his construction at the AMS-IMS-SIAM Summer Research Conference on Computability Theory and Applications at the University of Colorado in Boulder. He was given a full afternoon to talk and had prepared a total of 195 slides. His audience included many of the active computability theorists at the time. According to their reports, however, the complexity of his idea prevented him from giving a convincing presentation. The timing of this lecture was also extremely unfortunate, as it followed Shore and Slaman’s refutation of Barry’s non-splitting theorem, the one that formed the basis of his definition of the jump operation. Shore and Slaman gave an alternative and more indirect proof of the definability of the Turing jump. The construction of a nontrivial automorphism remains Barry’s unfinished goal. It is one to which he often returned, most recently in 2014, when a series of new definability result in the enumeration degrees provided a new perspective on the problem. Barry, Ted Slaman, and I planned to resume work on the automorphism problem and had even arranged a first meeting in Berkeley in November 2015, which sadly could not happen.

Figure 15.

Left: Barry with Dag Normann at CiE 2014 in Budapest, Hungary; picture taken on 23 June 2014 by Peter van Emde Boas. Right: Barry in the Rila mountain range, Bulgaria, 2014.

Barry’s scientific interests slowly drifted away from technical results in degree theory and in the remaining years he focused on the practical implications of this body of work for the real world. I am tempted to conjecture that his change in focus was a consequence of a collaboration with Odifreddi (cf. Fig. 13), in which they investigated “Incomputability in Nature” [41]. This article was published in the book Computability and Models, which collected articles from the corresponding joint research project and was edited by Barry and Sergey Goncharov. More substantially, I think the change was a consequence of Barry’s work on his book Computability Theory, which allowed him to reflect on the historic development, meaning, and future directions of this rather abstract field. This book was the first scientific textbook that I read through cover to cover during my graduate studies. It claimed to be “unlike any other” and, indeed, its novelty was immediately apparent. It treated the subject computability theory in a very broad way, providing a concise and comparatively informal introduction to modern computability theory. It started gently with an overview of basic concepts, placed in their historical and philosophical context, and swiftly lead the reader to advanced topics, such as forcing, priority, determinacy, randomness, and computable structure theory. The final section of this book is devoted to “Computability and Incomputability in Science”, marking the shift in Barry’s philosophy:

There are many areas in which the connection between small scale mechanisms and large scale structure is not really understood. What is the mathematics behind the emergence of subatomic structure, where there is not much more to build on than the algorithmic implications of causality itself? How can computability theory help us avoid arbitrary basic assumptions in explaining the way the Universe is? …Anyway, a whole swathe of fundamental issues raise questions about the algorithmic content of the world we live in. Computability theorists cannot lose, you have to admit. Things which can be done computably are best done with some knowledge of algorithmic structures and complexity of programs. Even at the most practical level, a little theory can often smooth the way in surprising ways. And if computability breaks down – great! – computability theorists are on hand to give us reasons and analyses of how to deal with incomputability [27, p. 380].

With this philosophy in mind and with the longstanding desire for a truly inclusive scientific community, Barry initiated the most celebrated project of his career: the scientific network Computability in Europe. Initially the plan was to create a research network of nodes, European universities with people interested in computability theory, and apply for funding from the European Commission that would support travel between these centers for research and training purposes, as well as an annual conference. The structure of this project was similar to the INTAS research project Computability and Models that Barry had already successfully completed in 2000–2002. There were two major differences: the network was much larger with nodes in twelve countries and the term “computability” was defined according to Barry’s evolved understanding. From the small abstract field of recursive function theory in which Barry had started his academic career, the term had grown into a huge interdisciplinary field combining many topics from mathematics, computer science, physics, biology, and philosophy.

Even though the application for funding was rejected, the network was formed and held its first conference in Amsterdam under the motto “New Computational Paradigms” (cf. Fig. 4). The goals of this conference were many, including to provide a venue for the participants to discuss the future of CiE after its first failed attempt at funding and to provide proof that such an organisation is needed in Europe for a possible future application. The goal was as follows:

The researchers from [the different communities will] exchange ideas, approaches and techniques in their respective work, thereby generating a wider community for work on [computational issues] that allows uniform approaches to diverse areas, the transformation of theoretical ideas into applicable projects, and general cross-fertilisation transcending disciplinary borders [40, pp. V–VI].

The quality of the first meeting is apparent in the first of many books and journal special issues of the CiE network, New Computational Paradigms, Changing Conceptions of What is Computable, edited by Barry Cooper, Benedikt Löwe, and Andrea Sorbi. Its success lead to the decision that there would be four more meetings in the following four years: in Swansea, Siena, Athens, and Heidelberg. The development and history of CiE is once again a topic that received a detailed account by Benedikt Löwe (who has invested just as much effort in it as has Barry) in [71]. The network grew into an association with its own book series and scientific journal and over 1300 members. Barry Cooper was the president of this association until 2015.

The conference CiE 2005 in Amsterdam was very important to me. It was my first scientific conference and it was the first time that I met Barry, a long haired professor in black jeans and a leather jacket, always with a smile on his face and full of energy and enthusiasm. A few months later I started working with Barry on my thesis. At our first meeting, he insisted that it is extremely important that I have a personal webpage and created one for me, the same one that I still use, right there on the spot. He then gave me a problem to work on, the problem whose solution was the most substantial part of my theses.

He always pushed his students towards the hard and challenging problems, problems whose solution would impress. Barry was very generous with his time; our weekly hour-long meetings usually took more than two hours. He offered support and advice, suggested many papers that I should read, but was never tempted to solve the problem instead of me. Mathematics usually took up only a part of our conversation. The rest was filled with historical accounts and personal stories, music and politics, books and films. Barry was extremely well-read, as one can obviously tell from the style in which he wrote. I often tried to impress him with a new book that I had discovered, but I never managed to suggest something that he was not already aware of. In the realm of music, I had more success: Barry was enthusiastic about sharing his music and he often invited us, his students, to gigs at the Terminte club and Leeds jazz. But he was also open to discovering new types of music and joined me for a couple of concerts of my favorite bands. Most recently, he talked about how very impressed he was by a Lady Gaga concert: “it’s not just the music, it’s the information content…I like people with histories…like degree-theoretic pathology feeds into richness of definable relations, messy inner psychology fuels individual creativity, received like an open fire on a winter’s night”. I learned so much more from him than I had ever imagined.

Barry’s commitment to his students was always beyond expectation. He helped us to overcome our shyness and encouraged us to present our work, first at the Computability Seminar in Leeds and then at one of the many conferences that we attended together. He was always present at our talks and always asked at least one question at the end, even when he was the single person most familiar with the work presented, just to make us feel better about our accomplishment. He cared about our careers and supported us on our search for jobs after we had graduated. He often applied successfully for funding that secured a postdoc position for a couple of years at Leeds for graduating students that did not have or want a better alternative. In his last week, he managed to convince his doctors that he absolutely must attend the computability seminar, because one of his students was presenting his recent research. And one of the final things on his last to do list, marked with highest priority, was a reference letter that he was asked to write for my job application.

Barry frequently talked about Turing’s life and work, impressed with his scientific breadth, creativity, and natural curiosity. In 2004, Barry had already turned his interest in Alan Turing into a research topic and delivered a couple of lectures devoted to the memory of this great scientist 50 years after his death. But it was Turing’s life that fascinated Barry, and soon an idea emerged for a grand celebration in honour of Turing’s 100th birthday. The year 2012 came to be known as “The Alan Turing Year” and Barry was at the center of numerous activities that were organised all over the world. Barry founded the Turing Centenary Advisory Committee, which coordinated conferences, workshops, scientific programs, and many other projects throughout the year. He maintained a webpage, a newsletter, a twitter account, and a facebook page of the Alan Turing Year, as well as column in the Guardian’s Northerner, thanks to which he made great progress in bringing Turing the recognition that he deserved, leading ultimately to Turing’s royal pardon in 2013.

Figure 16.

Conference in memory of Ivan Soskov 2014, Gyulechica, Bulgaria.

With Arnold Beckmann, Benedikt Löwe, Elvira Mayordomo, and Nigel Smart, Barry organised a six-month program, “Syntax and Semantics”, at the Isaac Newton Research Institute in Cambridge, meant to bring together researchers whose mathematical work related to the that of Alan Turing in Logic, Complexity, Cryptography, and Randomness. One of the special events within this program was the workshop “The Incomputable” in Chicheley Hall, an extraordinary venue maintained by the Royal Society. The workshop was unique in its focus on the mathematical theory of incomputability and its relevance for the real world, attempting for the first time to reunite (in)computability theory and “big science”. It was Barry’s attempt to properly introduce his old friends and colleagues from his degree theory days to the exciting part of science that he had entered. He never liked the idea of having a conference organised in his own honour for an anniversary and he did not even want to hear the word “retirement”, but this was a special event for him and I was truly honoured when he asked me to join him as an organiser. Of course, the main event in this year was the CiE conference entitled “Turing centenary conference: How the world computes”. The program committee for this conference was co-chaired by Barry Cooper and Anuj Dawar. For the first time in the history of CiE, the conference had more than 400 participants. With an excursion to Bletchley Park and a banquet at King’s College, it truly was unforgettable.

Apart from conferences and special events, Barry was involved in many publications arising from the centenary. Back in 2010, Barry had come up with the idea to republish Sara Turing’s biography of her son, Alan M. Turing. He tracked the copyright down to John Turing’s widow Beryl and approached Cambridge University Press with this idea. The book appeared just in time for Turing’s birthday, in June 2012. Barry published articles on Turing’s life, work, and legacy, in journals such as Communications of the ACM, Notices of the AMS, and Nature. The Once and future Turing, edited by Barry Cooper and Andrew Hodges and containing original essays on Turing’s ideas and their relevance to modern research, was published in April 2016. The Incomputable, journeys beyond the Turing barrier, arising from the workshop The Incomputable, appeared in 2017. The best recognised book, and the one that Barry was most proud of, was Alan Turing: his work and impact, edited by Barry Cooper and Jan van Leeuwen, winner of the prestigious R. R. Hawkins Award from the Association of American Publishers, as well as the 2013 PROSE Awards for Mathematics.

Figure 17.

Left: Barry presents at the conference in memory of Ivan Soskov, Gyulechica, Bulgaria, 2014. Right: Barry at the wedding of Mariya Soskova and Joe Miller, 2015.

Barry’s seventy-second birthday was blackened by devastating news: he was told that he is terminally ill with only a very short time to live. He generously devoted all this time to his family and friends, to his students, to his numerous projects, to science. The disease was unexpected and unexpectedly treacherous. Less then three weeks later Barry Cooper passed away. He left a great legacy to us, a legacy from which we have much more to learn and one which it will be our duty to maintain. I will miss him forever.

6. Peter van Emde Boas: Pictures of Barry Cooper from the van Emde Boas photo collection

I interacted with Barry Cooper at meetings starting with the CoLoRet program in the 1990s, and later in the context of CiE and TAMC. A sample of the 132 pictures I found in my archives is presented to illustrate this obituary.

My contacts with Barry Cooper. Since August 1976, I have followed the policy of making pictures of the people I encountered at work during seminars and meetings. This has resulted in a collection of approximately 100,000 pictures on film and prints, and a collection of digital files of comparable size. When invited to contribute to this special issue, I agreed to search in my collection for pictures showing Barry. The search resulted in a collection of 132 photos, not all of which will be presented here; some pictures have already appeared in this journal in the obituary [71]. I shall let the pictures speak for themselves.

Aside from these real life contacts, we encountered each other frequently during programme committee discussions for conferences where we were both members of the programme committee. I remember Barry as a participant who would not hesitate to stand up for unorthodox, if not outright strange papers. I did not always agree with his preferences but I have always appreciated the fact that he did.

As an example of his pragmatism: when I entered the conference room of the TAMC meeting in Beijing unexpectedly (I had not registered since I would not arrive in time) Barry was discussing with Andy Yao the issue of a missing session chair for the afternoon that day. If I remember correctly, Barry remarked “here is the solution to your problem”, and I was asked to serve a session chair that afternoon.

CoLoReT: Complexity, logic, and recursion theory. My earliest encounters with Barry occurred in the context of the European project Complexity, Logic and Recursion Theory (CoLoReT) initiated by Andrea Sorbi from Siena, where Barry was the representative participant from the Leeds group. Fig. 2 shows images from CoLoReT 1994 held in Amsterdam, and Figs 3 and 4 show images from CoLoReT 1995 in Siena. CoLoReT 1995 was the only occasion on which I met Barry’s family (as shown in Fig. 3).

CiE: Computability in Europe. By 2005, Barry had become the centre of the new network Computability in Europe (CiE). As such he attended all CiE meetings from 2005 until 2015; I attended all of these as well except for the meeting in Sofia in 2011. At the tenth meeting of the series (CiE 2014 in Budapest), I have reported about this period during the opening session [100]. Fig. 5 shows Barry at CiE 2005 in Amsterdam and at CiE 2007 in Siena, Fig. 9 shows Barry at CiE 2009 in Heidelberg, Fig. 13 shows him at the Turing Centenary Conference CiE 2012 in Cambridge, and Figs 13 and 14 at CiE 2013 in Milan. At CiE 2014 in Budapest, Barry handed over the reigns of the Association CiE to his successor as President, Dag Normann: Fig. 15, showing the old and the new President, was taken at CiE 2014 around the time of the transfer of responsibility.

TAMC: Theory and applications of models of computation. The final series represented in my collection is the China-based conference series Theory and Applications of Models of Computation (TAMC). Barry Cooper invited me for the program committee of TAMC 2009 in Changsha, and I attended that meeting as the start of a six week residence in Guangzhou (cf. Figs 7 and 8). I also served on the programme committee for the following TAMC meeting in Prague in 2010, but as far as I can reconstruct from my pictures Barry did not attend that one. He was again active for the 2012 meeting in Beijing dedicated to Alan Turing (cf. Fig. 12), where I met him on the final day of the conference, the day after I had arrived for another lecturing trip at the Tsinghua University.

References

Afshari,

Barmpalias,

S.B.

Cooper and

Stephan, Post’s programme for the Ershov hierarchy, J. Log. Comput.17(6) (2007), 1025–1040. doi:10.1093/logcom/exm032.

Ahmad, Some results on enumeration reducibility, PhD thesis, Simon Fraser University, 1989.

Ahmad, Embedding the diamond in the

Σ_{2}

enumeration degrees, J. Symb. Log.56(1) (1991), 195–212. doi:10.2307/2274914.

Ahmad and

A.H.

Lachlan, Some special pairs of

Σ_{2}

e-degrees, Math. Log. Q.44(4) (1998), 431–439. doi:10.1002/malq.19980440402.

Arslanov,

S.B.

Cooper and

Li, There is no low maximal d.c.e. degree, Math. Log. Q.46(3) (2000), 409–416. doi:10.1002/1521-3870(200008)46:3<409::AID-MALQ409>3.0.CO;2-P.

M.M.

Arslanov,

S.B.

Cooper and

I.S.

Kalimullin, Splitting properties of total enumeration degrees, Algebra Log.42(1) (2003), 1–13. doi:10.1023/A:1022660222520.

M.M.

Arslanov and

Sorbi, Relative splittings of

0_{e}^{'}

in the

Δ_{2}^{0}

enumeration degrees, in: Logic Colloquium ’98. Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic, University of Economics, Prague, August 9–15, 1998, S.R. Buss, P. Hájek and P. Pudlák, eds, Lecture Notes in Logic, Vol. 13, Association for Symbolic Logic, 1999, pp. 44–56.

Badillo Sánchez, Genericity in the enumeration degrees, PhD thesis, University of Leeds, 2013.

Cai,

H.A.

Ganchev,

Lempp,

J.M.

Miller and

M.I.

Soskova, Defining totality in the enumeration degrees, J. Amer. Math. Soc.29(4) (2016), 1051–1067. doi:10.1090/jams/848.

10.

W.C.

Calhoun and

T.A.

Slaman, The

Π_{2}^{0}

e-degrees are not dense, J. Symb. Log.61(4) (1996), 1364–1379. doi:10.2307/2275821.

11.

S.B.

Cooper, Degrees of unsolvability, PhD thesis, University of Leicester, 1971.

12.

S.B.

Cooper, Degrees of unsolvability complementary between recursively enumerable degrees. I, Ann. Math. Log.4 (1972), 31–73. doi:10.1016/0003-4843(72)90011-3.

13.

S.B.

Cooper, Minimal upper bounds for sequences of recursively enumerable degrees, J. London Math. Soc. (2)5 (1972), 445–450. doi:10.1112/jlms/s2-5.3.445.

14.

S.B.

Cooper, Distinguishing the arithmetical hierarchy, Preprint, 1972.

15.

S.B.

Cooper, Minimal degrees and the jump operator, J. Symb. Log.38 (1973), 249–271. doi:10.2307/2272061.

16.

S.B.

Cooper, Minimal pairs and high recursively enumerable degrees, J. Symb. Log.39 (1974), 655–660. doi:10.2307/2272849.

17.

S.B.

Cooper, An annotated bibliography for the structure of the degrees below

0^{'}

, with special reference to that of the recursively enumerable degrees, Recursive Function Theory Newsletter8(Suppl. 3) (1974).

18.

S.B.

Cooper, Partial degrees and the density problem, J. Symb. Log.47(4) (1982), 854–859. doi:10.2307/2273104.

19.

S.B.

Cooper, Partial degrees and the density problem. Part 2: The enumeration degrees of the

Σ_{2}

sets are dense, J. Symb. Log.49(2) (1984), 503–513. doi:10.2307/2274181.

20.

S.B.

Cooper, Enumeration reducibility using bounded information: Counting minimal covers, Z. Math. Log. Grundlag. Math.33 (1987), 537–560. doi:10.1002/malq.19870330608.

21.

S.B.

Cooper, The strong anticupping property for recursively enumerable degrees, J. Symb. Log.54(2) (1989), 527–539. doi:10.2307/2274867.

22.

S.B.

Cooper, Enumeration reducibility, nondeterministic computations and relative computability of partial functions, in: Recursion Theory Week. Proceedings of the Conference Held at the Mathematisches Forschungsinstitut, Oberwolfach, March 19–25, 1989,

Ambos-Spies,

G.H.

Müller and

G.E.

Sacks, eds, Lecture Notes in Mathematics, Vol. 1432, Springer-Verlag, 1990, pp. 57–110. doi:10.1007/BFb0086114.

23.

S.B.

Cooper, The density of the

{low}_{2} n

-r.e. degrees, Arch. Math. Log.31(1) (1991), 19–24. doi:10.1007/BF01370692.

24.

S.B.

Cooper, A splitting theorem for the n-r.e. degrees, Proc. Amer. Math. Soc.115(2) (1992), 461–471.

25.

S.B.

Cooper, Discontinuous phenomena and Turing definability, in: Algebra and Analysis. Proceedings of the International Centennial Chebotarev Conference, Kazan, June 5–11, 1994,

M.M.

Arslanov,

A.N.

Parshin and

I.R.

Shafarevich, eds, Walter de Gruyter, 1996, pp. 41–55.

26.

S.B.

Cooper, Local degree theory, in: Handbook of Computability Theory,

E.R.

Griffor, ed., Studies in Logic and the Foundations of Mathematics, Vol. 140, North-Holland, 1999, pp. 121–153. doi:10.1016/S0049-237X(99)80020-2.

27.

S.B.

Cooper, Computability Theory, Chapman & Hall/CRC Mathematics, 2004.

28.

S.B.

Cooper, A characterisation of the jumps of minimal degrees below

0^{'}

, in: Computability, Enumerability, Unsolvability. Directions in Recursion Theory, S.B. Cooper, T.A. Slaman and S.S. Wainer, eds, London Mathematical Society Lecture Note Series, Vol. 224, Cambridge University Press, 1996, pp. 81–92. doi:10.1017/CBO9780511629167.004.

29.

S.B.

Cooper, Recursive function theory newsletter 1972–1997. Webpage hosted on the author’s website by Leeds University, 2010.

30.

S.B.

Cooper and

R.L.

Epstein, Complementing below recursively enumerable degrees, Ann. Pure Appl. Log.34(1) (1987), 15–32. doi:10.1016/0168-0072(87)90039-X.

31.

S.B.

Cooper,

Harrington,

A.H.

Lachlan,

Lempp and

R.I.

Soare, The d.r.e. degrees are not dense, Ann. Pure Appl. Log.55(2) (1991), 125–151. doi:10.1016/0168-0072(91)90005-7.

32.

S.B.

Cooper,

Lempp and

Watson, Weak density and cupping in the d-r.e. degrees, Isr. J. Math.67(2) (1989), 137–152. doi:10.1007/BF02937291.

33.

S.B.

Cooper and

Li, Non-uniformity and generalised Sacks splitting, Acta Math. Sin.18(2) (2002), 327–334. doi:10.1007/s101140100150.

34.

S.B.

Cooper and

Li, Splitting and cone avoidance in the d.c.e. degrees, Sci. China Ser. A45(9) (2002), 1135–1146.

35.

S.B.

Cooper and

Li, Splitting and nonsplitting. II. A

{low}_{2}

C.E. degree about which

0^{'}

is not splittable, J. Symb. Log.67(4) (2002), 1391–1430. doi:10.2178/jsl/1190150292.

36.

S.B.

Cooper and

Li, Turing definability in the Ershov hierarchy, J. London Math. Soc. (2)66(3) (2002), 513–528. doi:10.1112/S0024610702003691.

37.

S.B.

Cooper and

Li, On Lachlan’s major sub-degree problem, Arch. Math. Log.47(4) (2008), 341–434. doi:10.1007/s00153-008-0083-5.

38.

S.B.

Cooper,

Li,

Sorbi and

Yang, Bounding and nonbounding minimal pairs in the enumeration degrees, J. Symb. Log.70(3) (2005), 741–766. doi:10.2178/jsl/1122038912.

39.

S.B.

Cooper,

Li and

Yi, On the distribution of Lachlan nonsplitting bases, Arch. Math. Log.41(5) (2002), 455–482. doi:10.1007/s001530100095.

40.

S.B.

Cooper,

Löwe and

Torenvliet, Preface, in: New Computational Paradigms. First Conference on Computability in Europe, CiE 2005,

S.B.

Cooper,

Löwe and

Torenvliet, eds, Amsterdam, The Netherlands, June 8–12, 2005, Proceedings, Lecture Notes in Computer Science, Vol. 3526, Springer-Verlag, 2005, pp. V–X.

41.

S.B.

Cooper and

Odifreddi, Incomputability in nature, in: Computability and Models. Perspectives East and West,

S.B.

Cooper and

S.S.

Goncharov, eds, The University Series in Mathematics, Kluwer Academic/Plenum Publishers, 2003, pp. 137–160. doi:10.1007/978-1-4615-0755-0_6.

42.

S.B.

Cooper,

Sorbi and

Yi, Cupping and noncupping in the enumeration degrees of

Σ_{2}^{0}

sets, Ann. Pure Appl. Log.82(3) (1997), 317–342. doi:10.1016/S0168-0072(96)00009-7.

43.

S.B.

Cooper and

Yi, The discontinuity of splitting in the recursively enumerable degrees, Arch. Math. Log.34(4) (1995), 247–256. doi:10.1007/BF01469381.

44.

C.S.

Copestake, The enumeration degrees of the

Σ_{2}^{0}

sets, PhD thesis, University of Leeds, 1987.

45.

C.S.

Copestake and

S.B.

Cooper, Properly

Σ_{2}

enumeration degrees, Z. Math. Log. Grundlag. Math.34 (1988), 491–522. doi:10.1002/malq.19880340603.

46.

Davis, Computability and Unsolvability, Dover, 1982.

47.

R.G.

Downey,

Lempp and

R.A.

Shore, Jumps of minimal degrees below

0^{'}

, J. London Math. Soc. (2)54(3) (1996), 417–439. doi:10.1112/jlms/54.3.417.

48.

Durrant,

Lewis-Pye,

K.M.

Ng and

Riley, Computably enumerable Turing degrees and the meet property, Proc. Amer. Math. Soc.144(4) (2016), 1735–1744. doi:10.1090/proc/12808.

49.

Friedberg, A criterion for completeness of degrees of unsolvability, J. Symb. Log.22 (1957), 159–160. doi:10.2307/2964177.

50.

R.M.

Friedberg and

RogersJr., Reducibility and completeness for sets of integers, Z. Math. Log. Grundlag. Math.5 (1959), 117–125. doi:10.1002/malq.19590050703.

51.

A.H.

Ganchev and

M.I.

Soskova, The high/low hierarchy in the local structure of the

Σ_{2}^{0}

-enumeration degrees, Ann. Pure Appl. Log.163(5) (2012), 547–566. doi:10.1016/j.apal.2010.10.004.

52.

A.H.

Ganchev and

M.I.

Soskova, Definability via Kalimullin pairs in the structure of the enumeration degrees, Trans. Amer. Math. Soc.367(7) (2014), 4873–4893. doi:10.1090/S0002-9947-2014-06157-6.

53.

A.H.

Ganchev and

M.I.

Soskova, The jump hierarchy in the enumeration degrees, Submitted.

54.

E.M.

Gold, Limiting recursion, J. Symb. Log.30 (1965), 28–48. doi:10.2307/2270580.

55.

Gutteridge, Some results on enumeration reducibility, PhD thesis, Simon Fraser University, 1971.

56.

C.M.

Harris, Enumeration reducibility and polynomial time bounds, PhD thesis, University of Leeds, 2006.

57.

C.M.

Harris, On the symmetric enumeration degrees, Notre Dame J. Form. Log.48(2) (2007), 175–204. doi:10.1305/ndjfl/1179323263.

58.

C.M.

Harris, Goodness in the enumeration and singleton degrees, Arch. Math. Log.49(6) (2010), 673–691. doi:10.1007/s00153-010-0192-9.

59.

C.M.

Harris, On the jump classes of noncuppable enumeration degrees, J. Symb. Log.76(1) (2011), 177–197. doi:10.2178/jsl/1294170994.

60.

C.G.

JockuschJr. and

D.B.

Posner, Double jumps of minimal degrees, J. Symb. Log.43(4) (1978), 715–724. doi:10.2307/2273510.

61.

I.S.

Kalimullin, Definability of the jump operator in the enumeration degrees, J. Math. Log.3(2) (2003), 257–267. doi:10.1142/S0219061303000285.

62.

T.F.

Kent, The

Π_{3}

-theory of the

Σ_{2}^{0}

-enumeration degrees is undecidable, J. Symb. Log.71(4) (2006), 1284–1302. doi:10.2178/jsl/1164060455.

63.

T.F.

Kent, The structure of the s-degrees contained within a single e-degree, Ann. Pure Appl. Log.160(1) (2009), 13–21.

64.

S.C.

Kleene, Introduction to Metamathematics, Van Nostrand, 1952.

65.

A.H.

Lachlan, A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Log.9(4) (1976), 307–365. doi:10.1016/0003-4843(76)90016-4.

66.

A.H.

Lachlan and

R.A.

Shore, The n-r.e.a. enumeration degrees are dense, Arch. Math. Log.31(4) (1992), 277–285. doi:10.1007/BF01794984.

67.

Lempp,

T.A.

Slaman and

Sorbi, On extensions of embeddings into the enumeration degrees of the

Σ_{2}^{0}

sets, J. Math. Log.5(2) (2005), 247–298. doi:10.1142/S0219061305000432.

68.

A.E.M.

Lewis, A note on the join property, Proc. Amer. Math. Soc.140(2) (2012), 707–714. doi:10.1090/S0002-9939-2011-10908-0.

69.

A.E.M.

Lewis, Properties of the jump classes, J. Log. Comput.22(4) (2012), 845–855. doi:10.1093/logcom/exq047.

70.

London Mathematical Society, Barry Cooper, LMS Newsletter454 (2016), 49–50.

71.

Löwe, Barry Cooper (1943–2015): The engine of computability in Europe, Computability5(1) (2016), 3–11. doi:10.3233/COM-160052.

72.

McEvoy, The Structure of the enumeration degrees, PhD thesis, University of Leeds, 1984.

73.

McEvoy and

S.B.

Cooper, On minimal pairs of enumeration degrees, J. Symb. Log.50(4) (1985), 983–1001. doi:10.2307/2273985.

74.

Myhill, A note on degrees of partial functions, Proc. Amer. Math. Soc.12 (1961), 519–521. doi:10.1090/S0002-9939-1961-0125794-X.

75.

Nikolova, Shared thoughts on Ivan Soskov (1954–2013), Computability3(1) (2014), 63–72.

76.

Petkov (ed.), Mathematical Logic: Proceedings of the Summer School and Conference on Mathematical Logic, Honourably Dedicated to the 90th Anniversary of Arend Heyting (1898–1980), Chaika (near Varna), Bulgaria, September 13–23, 1988, Plenum Press, 1990.

77.

E.L.

Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc.50 (1944), 284–316. doi:10.1090/S0002-9904-1944-08111-1.

78.

Putnam, Trial and error predicates and the solution to a problem of Mostowski, J. Symb. Log.30 (1965), 49–57. doi:10.2307/2270581.

79.

RogersJr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967.

80.

G.E.

Sacks, A minimal degree less than

0^{'}

, Bull. Amer. Math. Soc.67 (1961), 416–419. doi:10.1090/S0002-9904-1961-10652-6.

81.

G.E.

Sacks, On the degrees less than

0^{'}

, Ann. Math. (2)77 (1963), 211–231. doi:10.2307/1970214.

82.

G.E.

Sacks, The recursively enumerable degrees are dense, Ann. Math. (2)80 (1964), 300–312. doi:10.2307/1970393.

83.

L.P.

SassoJr., A minimal degree not realizing least possible jump, J. Symb. Log.39 (1974), 571–574. doi:10.2307/2272899.

84.

L.P.

Sasso, Degrees of unsolvability of partial functions, PhD thesis, University of California, Berkeley, 1971.

85.

L.P.

Sasso, A survey of partial degrees, J. Symb. Log.40(2) (1975), 130–140. doi:10.2307/2271892.

86.

J.R.

Shoenfield, On degrees of unsolvability, Ann. Math. (2)69 (1959), 644–653. doi:10.2307/1970028.

87.

J.R.

Shoenfield, A theorem on minimal degrees, J. Symb. Log.31 (1966), 539–544. doi:10.2307/2269688.

88.

J.R.

Shoenfield, MR0294126, Review of “S. B. Cooper, Degrees of unsolvability complementary between recursively enumerable degrees, I”, Math. Rev.45 (1973), #3199.

89.

R.A.

Shore and

T.A.

Slaman, Working below a high recursively enumerable degree, J. Symb. Log.58(3) (1993), 824–859. doi:10.2307/2275099.

90.

T.A.

Slaman and

Sorbi, A note on initial segments of the enumeration degrees, J. Symb. Log.79(2) (2014), 633–643. doi:10.1017/jsl.2013.1.

91.

R.I.

Soare, Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets, Ann. Math. (2)100 (1974), 80–120. doi:10.2307/1970842.

92.

Soskova,

S.B.

Cooper and

Sorbi (eds), Computability at Logic Colloquium 2009, J. Log. Comput.22(4) (2012), 667.

93.

M.I.

Soskova, The local structure of the enumeration degrees, PhD thesis, University of Leeds, 2008.

94.

M.I.

Soskova, A non-splitting theorem in the enumeration degrees, Ann. Pure Appl. Log.160(3) (2009), 400–418. doi:10.1016/j.apal.2009.01.009.

95.

M.I.

Soskova and

S.B.

Cooper, How enumeration reducibility yields extended Harrington non-splitting, J. Symb. Log.73(2) (2008), 634–655. doi:10.2178/jsl/1208359064.

96.

M.I.

Soskova and

I.N.

Soskov, Embedding countable partial orderings in the enumeration degrees and the ω-enumeration degrees, J. Log. Comput.22(4) (2012), 927–952. doi:10.1093/logcom/exq051.

97.

Spector, On degrees of recursive unsolvability, Ann. of Math. (2)64 (1956), 581–592. doi:10.2307/1969604.

98.

Stob,

wtt

-degrees and T-degrees of r.e. sets, J. Symb. Log.48(4) (1983), 921–930. doi:10.2307/2273658.

99.

A.M.

Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc.42 (1936), 230–265.

100.

van Emde Boas, Three funerals and a group wedding; CoLoRet, Recolet and Coin; the prehistory of CiE, presentation at CiE 2014, Budapest, Hungary, 23 June 2014.

101.

Watson, On restricted forms of enumeration reducibility, Ann. Pure Appl. Log.49(1) (1990), 75–96. doi:10.1016/0168-0072(90)90051-3.

102.

P.R.

Watson, Concerning d-recursively enumerable sets and s-reducibility of

Σ_{2}

sets, PhD thesis, University of Leeds, 1988.

103.

White, Letter: Barry Cooper obituary, The Guardian, online 27 January 2016.

104.

C.E.M.

Yates, Initial segments of the degrees of unsolvability. II. Minimal degrees, J. Symb. Log.35 (1970), 243–266. doi:10.2307/2270517.

S. Barry Cooper (1943–2015)

Abstract

3.1. Barry’s interest in enumeration reducibility

3.4. Barry’s work with Copestake: The properly Σ 2 0 e-degrees

3.5. Minimal covers (the best one can do) and the 1987 paper

3.7. The Turing degrees inside the e-degrees

4. Alexandra Soskova: Barry Cooper and the Sofia logic school

References

3.4. Barry’s work with Copestake: The properly $Σ_{2}^{0}$ e-degrees