| Research | Logic | Computability | Seminars | PhD students | Conferences | Personal | Teaching | Leeds |
Date of Birth: 9 October, 1943: Woking, Surrey.
Marital status: Wife (Kate). Four children
- Carrie Lenore (Carrie in Arizona - front right
in picture - February
2005), Shirin Colette,
Evan Coltrane and Natasha Zara (Evan and Tasha
at Bognor, c.2001 - Evan's rugby page).
Education: School at Westloats Primary,
Bognor Regis, 1948--55, and at Chichester High School for Boys, 1955--63.
(Photo from Easter 2002 reunion of "The
Boys" and spouses.)
Research student, Leicester University, 1966--68 (Supervisor: R. L. Goodstein), and at Manchester University, 1968--69 (Supervisor: C. E. M. Yates). Ph.D. (Leicester) Degrees of Unsolvability, 1971.
Employment
1969-1971 and 1973- , University of Leeds (present position:
Professor of Mathematical Logic).
1971-73, Lecturer in Mathematics, University of California, Berkeley (as a Senior Fulbright scholar).
1985-86, Visiting Professor, University of Chicago, and Visiting Associate Professor, University of Illinois, Chicago.
March--June,'89, Visiting Professor, University of Siena, Italy (Supported by a Centro Nazionale Recherche grant).
Research Students:
KEVIN McEVOY, The Structure of the Enumeration Degrees,
Ph.D. (Leeds), November 1984.
CATHERINE S. COPESTAKE, Enumeration Degrees of Sigma-two Sets, Ph.D. (Leeds), June 1986.
PHILIP WATSON, Concerning d-Recursively Enumerable Sets and s-Reducibility of Sigma-two Sets, Ph.D. (Leeds), December 1988.
ALAN SILVER, On polynomial Time Bounded Reducibilities, Ph.D. (Leeds), July 1991.
RICHARD J. COLES, Splittings and Nonsplittings in the Turing Degrees, Ph.D. (Leeds), April 1996.
MATTHEW SALTS, Relative Computability and the Difference Hierarchy, Ph.D. (Leeds), April 1998.
MATTHEW GIORGI, Continuity in Degree Structures, Ph.D. (Leeds), April 2001.
ANDREW E.M. LEWIS, Aspects of Complementing in the Turing Degrees, Ph.D. (Leeds), March 2003.
GEORGE BARMPALIAS, Computability and Applications to Analysis, Ph.D. (Leeds), September 2004.
CHARLES HARRIS, Enumeration Reducibility and Polynomial Time Bounds, Ph.D. (Leeds), March 2006.
BAHAREH AFSHARI, commenced October 2004.
MARIYA SOSKOVA, commenced September 2005.
ANTHONY MORPHETT, commenced April 2006.
Some recent talks:
European Summer Meeting of the Association of Symbolic Logic
(Logic Colloquium '90), Helsinki, Finland, July 1990.
9th International Congress of Logic, Methodology and Philosophy of Science, Uppsala, Sweden, August 1991.
International Centennial Chebotarev Conference, Kazan, Russia, June 1994.
Annual Meeting of the Association of Symbolic Logic, University of California at Irvine, March 1995.
Greater Boston Biennial Logic Meeting, M.I.T., May 1995.
European Summer Meeting of the Association of Symbolic Logic (Logic Colloquium '95), Haifa, Israel, August 1995.
Sixth Asian Logic Conference, Beijing, P. R. of China, May 1996.
49th British Mathematical Colloquium, Royal Holloway, London, April 1997.
European Summer Meeting of the Association of Symbolic Logic (Logic Colloquium '98), Prague, Czeck Republic, August 1998.
Colloquium Logicum 98 (Logic in Mathematics, Philosophy and History), Berlin, August 1998.
AMS-IMS-SIAM Joint Research Conference in Computability Theory and Applications, University of Colorado, Boulder, June 13-17, 1999.
International conference Logic and Applications honouring Yu.L. Ershov on his 60th birthday, Novosibirsk, Russia, May 4-6, 2000.
Turing 2004: A celebration of his life and achievements, University of Manchester, June 5th, 2004.
International Conference Algebra and Analysis 2004 on the occasion of the 200th anniversary of Kazan State University, Kazan, Russia, July 2--9, 2004.
Colloquium Logicum 2004, Biennual Meeting of the German Society for Mathematical Logic (DVMLG), September 17--19, 2004, University of Heidelberg, Germany.
Professional Service:
Co-editor and founder of the Recursive Function Theory Newsletter
(1972-).
Member organising committee for the 1979 European Summer Meeting of the A.S.L. (``Logic Colloquium '79"), Leeds University.
Programme Committee member for the Third Logical Biennial, Varna, Bulgaria, 1990, for the International Conference of Algebra and Analysis, Kazan, Russia, 1994, for the Logic Conference in honour of A. I. Malcev, Novosibirsk, 10-15 August, 1999, for 'Logic Colloquium 2000' held in Paris, and for 'Algebra and Analysis 2004', Kazan, Russia, July 2-9, 2004.
Chairman Programme Committee for the 1997 European Summer Meeting of the Association of Symbolic Logic (``Logic Colloquium '97"), University of Leeds.
Reviewer for Mathematical Reviews, Journal of Symbolic Logic, London Mathematical Society, and the Institute of Mathematics and its Applications.
Referee for various academic journals, including the Journal of Symbolic Logic, Archive for Mathematical Logic, Journal of Logic and Computation, publications of the London Mathematical Society, of the Royal Society, and of the American Mathematical Society, the Notre Dame Journal of Formal Logic, and the European Journal of Combinatorics.
Co-organiser (with Dr. J. K. Truss) of the Leeds Logic Conference, December 10/11, 1993.
Member of the Sacks Prize Committee 1995 - 99.
Grant reviewer for SERC/EPSRC, the U.S. National Science Foundation, NATO and the International Science Foundation.
Member Committee of the British Logic Colloquium, 1996-98.
External examiner (1998-2001), Mathematical Logic MSc, Manchester University.
Programme Committee Co-Chair Computability in Europe 2005: New Computational Paradigms, University of Amsterdam, June 8--12, 2005.
1. Minimal upper bounds for sequences of recursively enumerable degrees, J. London Math. Soc. 5 (1972) 445-450
2. Degrees of unsolvability complementary between recursively enumerable degrees, Part I, Ann. Math. Logic 4 (1972) 31-73.
3. Jump equivalence of the delta-zero-two hyperhyperimune sets, J. Symbolic Logic 37 (1972) 598-600.
4. Minimal degrees and the jump operator, J. Symbolic Logic 38 (1973) 249-271.
5. Minimal pairs and high recursively enumerable degrees, J\. Symbolic Logic 39 (1974) 655-660.
6. An annotated bibliography for the structure of degrees below 0' with special reference to that of the recursively enumerable degrees, Recursive Function Theory Newsletter 5 (1974) 1-15.
7. Partial degrees and the density problem, J. Symbolic Logic 47 (1982) 854-859.
8. Partial degrees and the density problem, Part 2: The enumeration degrees of the sigma-two sets are dense, J. Symbolic Logic 49 (1984) 503-513.
9. (with K. McEvoy) On minimal pairs of enumeration degrees, J. Symbolic Logic 50 (1985) 983-1001.
10. (with R. L. Epstein) Complementing below recursively enumerable degrees, Annals of Pure and Applied Logic 34 (1987) 15-32.
11. Enumeration reducibility using bounded information: counting minimal covers, Zeitschrift fŸr Math. Logik und Grundl. v. Math. 33 (1987) 537-560.
12. (with C. S. Copestake) Properly sigma-two enumeration degrees, Zeitschr. f. Math. Logik 34 (1988) 491-522.
13. The strong anti-cupping property for recursively enumerable degrees, J. Symbolic Logic 54 (1989) 527-539.
14. A jump class of non-cappable recursively enumerable degrees, J. Symbolic Logic 54 (1989) 324-353.
15. (with S. Lempp and P. Watson) Weak density in the d-r.e. degrees, Israel J. Mathematics 67 (1989) 137-152.
16. The jump is definable in the structure of the degrees of unsolvability, Bulletin of the A.M.S. 23 (1990) 151-158.
17. Enumeration reducibility, nondeterministic computations and relative computability of partial functions, in ``Recursion Theory Week, Oberwolfach 1989", (eds. K. Ambos-Spies, G. Muller, G. E. Sacks), Springer-Verlag, Berlin, Heidelberg, New York, 1990, pp. 57-110.
18. The density of the low-two n-r.e. degrees, Archive for Math. Logic 31 (1991) 19-24.
19. (with L. Harrington, A. H. Lachlan, S. Lempp and R. I. Soare) The d-r.e. degrees are not dense, Annals of Pure and Applied Logic 55 (1991) 125-151.
20. A splitting theorem for the n-r.e. degrees, Proceedings of the Amer. Math. Soc. 115 (1992) 461-471.
21. Definability and global degree theory , in ``Logic Colloquium '90" (eds. J. Oikkonen and J. Vaananen), Lecture Notes in Logic vol. 2, Springer-Verlag, Berlin, Heidelberg, New York, 1993, pp. 25-45.
22. Professor Stephen Kleene (obituary), in ``The Independent", Thursday 10 February, 1994.
23. Rigidity and definability in the non-computable universe, in ``Proceedings of the 9th International Congress of Logic, Methodology and Philosophy of Science" (eds. D. Prawitz, B. Skyrms, D. Westerstahl), North-Holland, Amsterdam, 1994, pp. 209-236.
24. (with X. Yi) Discontinuity of splitting in the recursively enumerable degrees, Archive for Math. Logic 34 (1995) 247-256.
25. (editor, with T. A. Slaman and S. S. Wainer) Computability, Enumerability, Unsolvability: Directions in Recursion Theory, London Mathematical Society Lecture Note Series 224, Cambridge University Press, 1996.
26. A characterisation of the jumps of minimal degrees below 0', in `Computability, Enumerability, Unsolvability: Directions in Recursion Theory', London Mathematical Society Lecture Notes, Cambridge University Press, 1996, pp. 81-92.
27. Discontinuous phenomena and Turing definability, in `Algebra and Analysis' (eds. M. M. Arslanov, A. N. Parshin and I. R. Shafarevich), Proceedings of the International Centennial Chebotarev Conference held in Kazan, Russia, June 5-11, 1994, Walter de Gruyter, Berlin, New York, 1996, pp. 41-55.
28. Strong minimal covers for recursively enumerable degrees, Math. Logic Quarterly 42 (1996) 191-196.
29. Beyond Gödel's theorem - the failure to capture information content, in ``Complexity, Logic and Recursion Theory" (ed. A. Sorbi), Lecture Notes in Pure and Applied Mathematics, vol. 187, Marcel Dekker, New York, 1997, pp. 93-122.
30. (with A. Sorbi) Non-cappable enumeration degrees below 0', J. of Symbolic Logic 61 (1996) 1347-1363.
31. Local degree theory, in the `Handbook of Computability Theory' (ed. E. R. Griffor), North-Holland/Elsevier, Amsterdam, Lausanne, New York, Oxford, Shannon, Singapore, Tokyo, 1999, pp. 121-153.
32. (with X. Yi) Isolated D.R.E. degrees, preprint.
33. (with A. Sorbi and X. Yi) Cupping and noncupping in the enumeration degrees of sigma-zero-two sets, Annals of Pure and Applied Logic 82 (1996) 317-342.
34. On a conjecture of Kleene and Post, Math. Logic Quarterly 47 (2001), 3-33.
35. On systems of finite sets with multiple intersections, to appear.
36. On conjectures of Erdos, Ko, Rado and Frankl, to appear.
37. (with K. Ambos-Spies, S. Lempp) Initial segments of recursive linear orders, Order 14, no. 2 (1997-98) 101-105.
38. (with G. Barmpalias and A. Lewis) Minimal pairs and the Slaman-Soare phenomenon, in preparation.
39. (with R. Coles) The strongest non-splitting theorem, in preparation.
40. Families containing no s pairwise disjoint sets, in preparation.
41. The Turing universe is not rigid, in preparation.
42. The limits of local Turing definability, in preparation.
43. (with A. Sorbi and Y. Yang) A capping theorem for the delta-zero-two enumeration degrees, in preparation.
44. Minimal degrees and the arithmetical hierarchy, in preparation.
45. Beyond Gödel's theorem - Turing nonrigidity revisited, in 'Logic Colloquium '95' (eds. J. A. Makowsky and E. V. Ravve), Lecture Notes in Logic, Vol. 11, Springer, Berlin, New York, Tokyo, 1998, pp. 44-50.
46. A non-invariant atomic jump class , in preparation.
47. Computably enumerable singletons and Turing definability, in preparation.
48. Upper cones as automorphism bases, Siberian Advances in Mathematics 9 (1999), 1-61.
49. (editor, with J. K. Truss) Models and Computability , London Mathematical Society Lecture Note Series 259, Cambridge University Press, 1999.
50. (editor, with J. K. Truss) Sets and Proofs , London Mathematical Society Lecture Note Series 258, Cambridge University Press, 1999.
51. Clockwork or Turing U/universe? - remarks on causal determinism and computability, in 'Models and Computability' (S.B. Cooper and J.K.Truss, eds.), London Mathematical Society Lecture Note Series 259, Cambridge University Press, 1999, pp. 63-116.
52. Hartley Rogers' 1965 agenda, in ``Logic Colloquium '98" (S. R. Buss, P. Hajek and P. Pudlak, eds.), Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic, held in Prague, Czech Republic, August 9-15, 1998, Lecture Notes in Logic 13, Association for Symbolic Logic/A K Peters, Natick, Massachusetts, 2000, pp. 154-172
53. (with M. Arslanov and A. Li) There is no low maximal d.c.e. degree, Math. Logic Quarterly 46 (2000), 409-416.
54. (with A. Li and X. Yi) On the distribution of Lachlan nonsplitting bases, Archive for Math. Logic, 41 (2002), 455-482.
55. (with A. Li) Splitting and nonsplitting: A Low3 Harrington nonsplitting base, preprint.
56. (with A. Li) Non-uniformity and generalised Sacks splitting, Acta Mathematica Sinica, English Series 18 (2002), 327-334
57 (with M. M. Arslanov and I. Sh. Kalimullin) Splitting properties of total enumeration degrees, Algebra and Logic 42 (2003), 1-13.
58. (with A. Li) Splitting and nonsplitting, II: A Low2 c.e. degree above which 0' is not splittable, J. of Symbolic Logic 67 (2002), 1391-1430.
59. (with A. Li, A. Sorbi, Y. Yang) A maximal 3-c.e. enumeration degree, Israel J. of Mathematics 137 (2003), 285-320.
60. On the intensionality of Turing definitions, to appear.
61. (with A. Li) Splitting and cone avoidance in the d.c.e. degrees, Science in China (Series A), 45 (2002), 1135-1146.
62. (with A. Li) Turing definability in the Ershov hierarchy, J. of the London Math. Soc. (2) 66 (2002), 513-528.
63. (with P. Odifreddi) Incomputability in Nature, in Computability and Models: Perspectives East and West (S. B. Cooper and S. S. Goncharov, eds.), Kluwer Academic/Plenum Publishers, New York, Boston, Dordrecht, London, Moscow, 2003, pp. 137-160.
64. (with S. S. Goncharov, eds.) Computability and Models: Perspectives East and West, The University Series in Mathematics, Kluwer Academic/Plenum Publishers, New York, Boston, Dordrecht, London, Moscow, 2003.
65. Computability Theory, Chapman & Hall/CRC Press, Boca Raton, FL, New York, London, 2004, 424 pages.
66. (with M. M. Arslanov, C. T. Chong and Y. Yang) The minimal e-degree problem in fragments of Peano arithmetic, to appear in the Annals of Pure and Applied Logic.
67. (with M. Arslanov and A. Li) There Is No Low Maximal d.c.e. Degree - Corrigendum, Math. Logic Quarterly, 50 (2004), 628-636.
68. (with A. Li, A. Sorbi and Y. Yang) Bounding and nonbounding minimal pairs in enumeration degrees, to appear in the J. of Symbolic Logic.
69. (with A. Li) On Lachlan's major subdegree problem, to appear.
70. (with M. M. Arslanov and I. Sh. Kalimullin) Total degrees and nonsplitting properties of Sigma-two enumeration degrees, in preparation.
71. The local jump-join theorem for nondeficient d.c.e. operators, in preparation.
72. Computability and emergence, in preparation for Vol. 4 of the Kluwer/Springer International Mathematical Series, Mathematical Problems from Applied Logic. New Logics for the XXI-st Century (eds. D. Gabbay, S. Goncharov, M. Zakharyaschev).
73. The incomputable Alan Turing, in preparation for the proceedings of Turing 2004: A celebration of his life and achievements, University of Manchester, June 5th, 2004, to be published by the British Computing Society.
74. Incomputability, fifty years after Alan Turing, in preparation for the proceedings of Algebra and Analysis 2004, Kazan, Russia, July 2-9, 2004.
75. An Introduction to Turing Nonrigidity, in preparation.
Personal Interests:
Music - Mahler, Shostakovich,
Schoenberg, Birtwistle, Messiaen,
P.J. Harvey, Captain Beefheart,
Gubaidulina, John Coltrane, Sun Ra, Cecil Taylor,
Anthony Braxton,
Marilyn Crispell, AACM,
Ornette Coleman,
renaissance music, Bach, Beethoven, Paul Robeson, Isabel Parra, Siouxsie and the
Banshees, Tom Waits, Kate Bush, Janacek,
Mark Anthony Turnage, Xenakis, Chicago blues,
Charles Wuorinen,
Steve Lacy,
Allan Pettersson,
Galina
Ustvolskaya,
Bill Dixon,
Michael Moore,
Helmut Lachenmann,
Konk Pack, Andrzej Panufnik,
Glenn Spearman, most of Leo Records,
Humphrey Searle,
Tetsu Saitoh,
Gloria Coates,
Acid Mothers Temple,
Rebecca Saunders, ....
(Founder and committee member
Leeds Jazz.)
Some favourite places for live music (when time allows):
Termite Club, and the
Huddersfield Contemporary Music Festival.
Reading and plays - Tolstoy, Dostoyevsky, E.F. Benson, Eric Hobsbawm, political theory, psychology, Mikhail Bulgakov, James Hanley, Primo Levi, Susan Dunlap, Colette, Ford Madox Ford, Joseph Conrad, D.H. Lawrence, Virginia Woolf, Jane Austen, Jack London, cosmology, philosophy, Strindberg, Dennis Potter, Wordsworth, Stevie Smith, David Mercer, Joe Orton, Ibsen, Chekov, Philip Roth, Don DeLillo, Anthony Burgess, Saul Bellow, Henry Green, Theodore Dreiser, T.F. Powys, Thomas Wolfe, Hermann Broch, Orhan Pamuk, Cynthia Ozick, Cao Xueqin, Haruki Murakami, Kenzaburo Oe ....
Art - Gauguin, Lucian Freud, Turner, Piero della Francesca, Domenico Beccafumi, Botticelli, Francis Bacon, Henri Rousseau, Mark Rothko, Edward Burra (thanks, Carrie), ....
Plants - Palms and Cycads, Asclepiads, Briophytes, Bromeliads, Euphorbias, Eucalypti, Cyatheas, Dicksonias, giant redwoods... .
Politics (days of relentless activism over ... but memories of many interesting and wonderful people, and our efforts to build a better world).
Cinema - Ingmar Bergman, Glauber Rocha, Tarkovsky, Eisenstein, Erich von Stroheim ... but mainly kids' films currently!
Running (bodily wear-and-tear permitting - favourite races - 1985 Chicago Marathon (2hrs. 48mins.), 1989 Oberwolfach 10K). And rugby (England under-fifteen team, 1958) - recent involvement via Evan and Moortown Rugby Club.
Places - the seaside (Robin Hood's Bay, Bognor, Whitby), Berkeley and the Bay Area (Cafe Med, Moe's, Vesuvio's, City Lights, Yoshi's, parks, bridges), Siena, Bressanone, Kazan, Scotland, China, Chicago, New York, Ventnor, Yugoslavia (as was), Greece, Kew Gardens, Munich, Heidelberg, US national parks, Singapore (although a little warm!), Kazakhstan (a photo from the mountains above Almaty), book and record shops, anywhere one can be anonymous, ...
Memberships: British Logic Colloquium,
Association for Symbolic Logic, London Mathematical Society,
American Mathematical Society,
New Politics Network, Labour Party,
Amnesty International,
Society for the Promotion of New Music, European Palm Society,
Luxuriant
Flowing Hair Club for Scientists.