# Memorial tribute to John Shepherdson

A Memorial Service celebrating the life of John Shepherdson was held at Goldney Hall in Bristol on Saturday 21 February 2015. Angus MacIntyre delivered a tribute:

**John Shepherdson (1926-2015).**

I have the privilege of representing the mathematical logic community today, to honour the memory of one of the most admired people in the field. Not only did John create beautiful and fundamental mathematics, but his gentle and sunny demeanour, and his enduring modesty, made him exemplary at a personal level too.

Yiannis Moschovakis (of UCLA) and I are old friends, who have certainly had ideological differences over the years. We both spent time at Bristol because of John, and recently found ourselves using exactly the same image about John. On January 9, after hearing from Philip Welch the shocking news, I wrote to Yiannis to let him know (not knowing that Philip had already done so). Yiannis wrote:

John was a model for me in his approach to mathematics and mathematicians.Quite independently, I had written to Philip:

This news has shaken me. I knew John since 1967 personally, and I knew a lot of his work before that. He was for me really a model, as a man and a mathematician. There was a special grace and gentleness about him.To this I add some comments of Michael Atiyah, who like John was a Manchester

Grammar School and Trinity man (about three years later). He had a long time ago

spoken very strongly of the cleverness and problem solving power of the young John.

Now, on hearing of his death, he added:

He was always quiet and shy with a sly sense of humour, modest and unassuming - not typical of mathematicians in general, more X than Y ...I happen to know the solutions for $X$ and $Y$, but will not reveal them, except to stress their eminence. On the mathematical quickness, Dana Scott told me lately:

Of course John was always a quick study.John's mathematical publications stretch from 1946 into this century. The first I found, connected to Heilbronn, is on simple additive combinatorics (and was reviewed by Erdös). The second is on matrix theory. This early evidence of versatility reminded me of Abraham Robinson, who was ten years older, but got going much later because of the war.

When John began at Bristol in 1946, mathematical logic (as opposed to philosophy of mathematics) was a very young subject, in its teens. Great work had come suddenly in the 1930's, on formal systems, set theory, recursion theory and computability theory, on model theory, and on proof theory. Two of the contributors, Gödel and Turing, have been partially assimilated to popular culture, though Gödel not to stage and screen. Among others most relevant to John's mathematical life were Church and Kleene, Americans from Princeton. The only UK contributions were from Ramsey, Turing, and Max Newman. Goodstein (who became in 1958 the first Professor in the UK to specialize in mathematical logic), was already active in logic pre-war, but his famous contributions came in the 1940's. Robin Gandy, another crucial figure in the development of mathematical logic in the UK, and whom we associate with John in establishing our community, was about ten years older than John, but, like Robinson, had his research development slowed by the war, and did not finish his D.Phil. until 1951, with Turing. We do not know if John ever met Turing.

John, in a long life, was to contribute in depth across the entire spectrum, and to subjects then unknown or just emerging, such as logic programming, computable mathematics, and finite automata.

The first work to make him known internationally was the series of papers, beginning in 1951, on the minimal model for set theory, inspired by Gödel's monograph from the late 1930's, and manifesting a deep understanding of that great work. This is surely here to stay. Cohen rediscovered it, en route to his sensational work of 1963 on AC and CH. John's purpose was almost methodological, to show severe limitations on the method of standard transitive inner models as far as proving consistency results is concerned. Another puzzle for us is whether John was self-taught on the Gödel monograph. His 1953 stay at the Institute for Advanced Study was presumably arranged through Gödel.

Thereafter John's publications were, for a long time, on computability and formal systems (both notions in a broad sense), where he began to compete and/or collaborate with the likes of Rabin, Scott, Feferman, Myhill, Ehrenfeucht, Kreisel. Much later he wrote, in an obituary of Elgot, a viewpoint on recursion theory, or rather on how Elgot (and surely he) wanted it to evolve. John wrote with exceptional clarity, and it was almost inevitable that he foresaw a recursion theory free from excessive coding and decoding, one whose basic insights would be useful in algebra and analysis, and which would interact productively with the ways of those involved in programming, automated theorem proving, numerical analysis and the like. Here and there in his writing there is emphasis on the need, not merely for natural algebraic foundations, but also for really hard algorithms. He speaks almost wistfully of Smale's "great and daunting" work. It may surprise people to learn that John wrote a paper with Eilenberg, and in the Elgot obituary speaks with evident approval of the relevance of category theory to recursion theory/computability.

I should say that John's own work on computable algebra is relevant to some major issues in contemporary model theory. In the last year the Frohlich-Shepherdson paper, from 1956, was permanently on my desk, and frequently consulted, as I tried to finish a complicated paper on computable models for Zilber's exponential. Rabin's subsequent paper was there too, and greatly valued, but there was something special in the style of Frohlich-Shepherdson which guided me in a rather arduous task of effectivizing various delicate algebraic and model-theoretic constructions. Bear in mind that the paper was written 60 years ago. I had anticipated writing to him to tell him about this work, but did not know he was ill and put things off. Rereading that paper, and reading others in preparation for this tribute, I became keenly aware of the exceptional lucidity of John's writing, combining technical assurance with a notable attention to methodology.

In the famous case of Shepherdson-Sturgis register machines there are two things to remark:

1. A huge simplification of the technical foundations of Turing computability theory, and one which greatly simplified access to undecidability results in algebra.

2. In the published paper, scrupulous attention to the somewhat complex priority issues arising on the road to this simplification.

2. In the published paper, scrupulous attention to the somewhat complex priority issues arising on the road to this simplification.

Though never involved in the pure theory of Turing degrees, John did some of the first work on showing that certain natural families of decision problems turn up all recursively enumerable degrees. The basic result for word and conjugacy problems in groups is due to John's colleague, Chris Clapham.

The reader with a good memory will remember that the last full page of Smullyan's beautiful book gives an "extremely ingenious" proof by John, and the bibliography refers to his work (independently of Ehrenfeucht-Feferman) on numeralwise representability. One virtue of this work is to demystify to a great extent the coding and self-reference aspect of the Gödel (First) Incompleteness Theorem, and to provide a basic technique in undecidability proofs. Related to this is his work, often in collaboration, on Raphael Robinson's $Q$ and other weak systems. This is done with great elegance, and again is here to stay, I think. I will return to this topic below, but stress now John's capacity for going rather deeper than others, for example in studying non-standard models of such systems (not at all routine, but then none of John's published work is routine), and of initiating the study of the Diophantine equations solvable in models of such systems. Most of his contemporaries turned from non-standard models of arithmetic in the aftermath of Tennenbaum's Theorem that there are no recursive non-standard models of sufficiently strong axiom systems, but John continued to produce difficult and suggestive constructions for weak systems.

Kreisel had a strong influence on John, by isolating "philosophical" issues, in the mathematics, serious analysis of which might lead to mathematical advances. A nice example, related to $Q$ and some of its non-standard models, comes from Kreisel's insistence that discussion of "unprovability of consistency" was very sloppy indeed, and that one should be constantly stressing the Hilbert-Bernays derivability conditions and issues of naturality. Kreisel induced Shepherdson and Bezboruah to produce a paper in which, inter alia, a "natural" notion of formalized proof is given, for which $Q$ proves its own consistency. The mathematics is rather tricky, involving non-standard models of $Q$, and the accompanying methodological, or philosophical, discussion is scrupulous and entertaining. The authors look ahead to a time when a more compelling such result for $Q$ will be obtained (as was done by Paris and Wilkie in the 1980's, by a highly nontrivial proof).

John Crossley, in his touching contribution, told an amusing story about Kreisel, departing Temple Meads, continuing to explain, through the window of a departing train, some subtle point (almost surely worth pursuing) to the two Johns. Kreisel is three years older than John, and, despite ill health, still looks for shifts of emphasis, revealing neglected possibilities in results which are admired for the wrong reasons. I believe Kreisel has had an important influence on John, and in turn John's strengths have appealed to Kreisel. I speak as someone on whom Kreisel has had a unique and decisive influence (right down to my excessive use of brackets). The train image brought back to me the day in the mid to late 1980's when I met Kreisel at Oxford station, as he arrived, with minimalist baggage, for what was promised as a visit of a couple of weeks. It lasted for a couple of years, and transformed the intensity of life in logic at Oxford.

[Added March 1, 2015. With Kreisel's death this morning, our community has now lost two of its most outstanding members in the course of two months].

In several publications around 1963 John responded to Kreisel's "unflagging correspondence" (I, who once received five Kreisel letters in one day, take this as an example of John's sly humour) about making some sense of the notion of direct proof in arithmetic, by producing a computable model of open induction, and giving a suggestive alternative axiomatization (induction-free) of open induction. He used Tarski's work on real-closed fields, in a simple but brilliant way (and elsewhere alludes to doing things with open induction for exponentiation). After quite a long neglect, this paper has inspired many others (by Wilkie, van den Dries, Macintyre-Marker, Ressayre, …) and has proved relevant even to the major problem on real exponentiation. When, many years later, I told John of the big following this paper had, he was bemused. Again we see beautiful work, and a natural modesty. The problem of which Diophantine equations have solutions in models of open induction remains open after 50 years. Alex Wilkie and I have different intuitions on this, and a longstanding bet on the outcome.

A major contribution to pure recursion theorem came (earlier than the above) in the Myhill-Shepherdson Theorem stated suggestively (by Moschovakis) as: algorithms which call their computable, partial function arguments by name (by a Kleene code) can be simulated by nondeterministic algorithms that call their function arguments by value. This, again, is beautiful, ingenious, here to stay.

Long after Shepherdson-Frohlich, he wrote, with admirable enthusiasm, of Harvey Friedman's work on algorithmic procedures and computational complexity of real functions (in this he was in a small majority of "big names"). His commentary points out, gently (as he always seemed to do when detecting errors) some flaws in what Harvey wrote, but mainly expresses his intense admiration for Harvey's courage, and recounts his own chagrin at not having taken the risks Harvey took. His papers on Harvey shine with the altruism of his entire opus, and further exemplify a particular moral force he had. The word "chagrin" came up in another place when I was preparing this talk. Rabin and Scott, in 1957, did fundamental work on finite automata (leading to their Turing Award in 1976). They were justly proud of an intricate proof that two way automata do not recognize more than one way automata. Dana told me they were amazed and chagrined by a devastatingly clear and direct proof of this, produced quickly by John, the quick study. Once again, we see clear, fundamental work, with no fanfare. Again too, computational issues around Shepherdson's work are studied deeply to this day. The extensive work on logic programming is further from my expertise, as is the late work with Hajek and Paris, but the style and the informal rigour are deeply appealing. In an official Obituary all this must be covered, by a well-informed team. John's versatility makes it almost impossible for just one person to cover it all.

John was very bright, of mind and of appearance. He looked very sporting, was gentle in his professional ways, and witty but deadly serious in his writing.

When I finished my doctoral work at Stanford I wanted to return to UK, and Bristol was the most attractive place for me. I had not yet met him, but knew much of his work, and was deeply attracted by it. I got a SERC Postdoc for a year at Bristol, in 1967-8, hoping I might be able to stay. I did not know about the number of logicians already in John's orbit, achieving a ratio of logic to the rest perhaps never equalled anywhere! I had a very happy year at Bristol, sharing an office with Ken Appell, spending a lot of time talking to him about free groups. These were the days before Matejasevic, and I tried hard to use forcing to destroy primes (now known to be doomed to failure). I met Harry Simmons and we started a lively collaboration. It was a time of freedom, thinking all day about then impossible things, effort reports unknown. I did not write a single paper, but years later I wrote many that germinated from my time at Bristol. There was a marvellous MSc course, sampling all the great new ideas bubbling up in logic. At the centre of it all was this lovely man, whom we now mourn, from whom many of us learned subtle things about mathematics and our common purpose.

Let us not forget his selfless contributions to initiating the ASL European Meetings, and the BLC, and to the Oxford Logic Guides.

Bill Craig of Berkeley is one of the same kind as John, graceful and who leaves work of enduring importance. He has made it to 96, and is still lively. He asked me to pass his condolences to the family. Given his eminence, and the respect in which he is held, this represents the condolences of a very broad international community.

I know John and Margaret were sailors. I tried to end with a sailing motif, but failed, but two images around John and the sea have been in my imagination lately. Let me end with those, without elaboration.

A long time ago, John told me of sailing (it may have been kayaking) in Dunstaffnage Bay, near the mouth of Loch Etive in Argyll, a couple of miles from where I was raised. This is a place of very great beauty, and he clearly remembered it intensely. He described navigating between the two islands in the bay, Eilean Beag, and Eilean Mhor (nothing beautiful here, just Wee island and Big Island). Now, when we drive past on our way to or from Oban, I think fondly of John in that setting, and I am sure I will continue to do so. Bill Craig, in his message to me a couple of weeks ago, chose to remember overnight sailing with John in San Francisco Bay. Thank you.

Last Updated October 2015