My Mathematical Encounters with Anil Nerode Rod Downey Victoria University Wellington New Zealand LFCS, San Diego, January 2013 Plan (cid:73) When I was asked to give a talk for Anil’s 80-th, I was not only honoured, but also had occasion to reflect on how many times his work has influenced mine. (cid:73) It seemed to me that this would be a nice basis for a talk. The beginning (cid:73) I think I met Anil in 1979 (certainly 79 or 80) in Monash University in Australia. I was beginning my PhD. (cid:73) My supervisor, Crossley, said I should talk to Anil Nerode, to which I said “who?” My thesis (cid:73) Was in Effective Alegebra. (cid:73) This considers algebraic structures and endows them with some kind of computational structure and seeks to see what kind of algorithms come with this. (cid:73) For example. A computable group is one where the group operations are computable and the universe is too. (cid:73) Nerode was there way before me. Background (cid:73) Begins implicitly with work of Kronecker, etc in the late 19th century. (cid:73) Explicitly with the work of Max Dehn in 1911 asking about the word, conjugacy and isomorphism problems in finitely presented groups. (That is, groups of the form F(x ,...,x )/G(y ,...,y ) with y 1 n 1 m i words in x , F and G free and G normal.) i (cid:73) Before the language of computability theory. (cid:73) Arguably going back to Kronecker. (cid:73) Van ver Waerden (based on Emmy Noether’s lectures), Grete Hermann (1926) for ideal theory, Post and Turing in the 1930’s for semigroups. (cid:73) Discussion: Metakides (a student of Anil) and Nerode: The introduction of nonrecursive methods into mathematics. The L. E. J. Brouwer Centenary Symposium (Noordwijkerhout, 1981), 319-335. (cid:73) Modern incarnation: Fr¨ohlich and Shepherdson 1956, Effective procedures in field theory, (cid:73) Rabin, Computable algebra, general theory and theory of computable fields, 1960 (cid:73) Malt’sev, Constructive algebra I, 1961. (cid:73) Rabin showed that a computable field had a computable algebraic closure. (cid:73) Fro¨lich and Shepherdson showed that there are computale fields without computably unique algebraic closures (meaning no computable isomorphism between the algebraic closures). (cid:73) When does a computable field have a computably unique computably algebraic closure. (cid:73) What about the rest of classical field theory? (cid:73) For example, does a computable algebraically closed field have a computable transcendence base? Classic papers (cid:73) Metakides and Nerode : (cid:73) Recursion theory and algebra, in Algebra and Logic (ed. J. N. Crossley), Lecture notes in Math., vol. 450, New York (1975), 209–219. (cid:73) Recursively enumerable vector spaces, Ann. Math. Logic, Vol. 11 (1977), 141-171. (cid:73) Effective content of field theory, Ann. Math. Logic, vol. 17 (1979), 289–320.