Hartley Rogers Jr passed away on July 17, 2015 (last week Friday as I write this).He was 89 and passed peacefully.
For our community Rogers is probably best known for his textbook on Recursion Theory which I discuss below. He did many other things, for which I refer you to
his Wikipedia page here.
His book was:
The theory of recursive functions and effective computability.
It was first published in 1967 but a paperback version came out in 1987.
It was probably the first textbook in recursion theory. It was fairly broad. Here are the chapter headings and some comments.
Recursive functions
Unsolvable problems (The first edition came out before Hilbert's tenth problem was solved),
Purpose: Summary,
Recursive invariants,
Recursive and recursively enumerable sets,
Reducibilities,
One-One Reducibilities; Many-one Reducibilities, (Maybe its just me but I can't imagine caring if the reduction is 1-1 or m-1.)
Truth-Table Reducibilities;simple sets, (``simple sets are not simple'' was a quote from Herbert Gelernter who taught me my first course in recursion theory.)
Turing Reducibilities; hypersimple sets,
Post's Problem; incomplete sets. (Posts problem was to find an r.e. set that is neither recursive nor Turing-complete. when I tell people there such a set they they often say `Oh, Like Ladner's Theorem.' Thats true but backwards. Its still open to find a NATURAL set that is incomplete, though they prob don't exist and its hard to pin that down.)
The Recursion Theorem,
Recursively enumerable sets as a lattice,
Degrees of unsolvability,
The Arithmetic Hierarchy (Part 1),
The Arithmetic Hierarchy (Part 2),
The Analytic Hierarchy.
Looking over his book I notice the following
1) He thanks Noam Chomsky (a linguist) and Burton Dreben (A philosopher). I think we are more specialized now. Would it be surprising if a text in recursion theory written now thanked people who are not in math?
2) He thanks his typist. I think that people who write math books now type it themselves. I wonder if novelists also now type it themselves.
3) I think that Soare's book replaced it as THE book that young recursion theorists read. (Are there young recursion theorists?) Soare's book is chiefly on r.e. degree theory, Rogers book is broader. When Rogers wrote his book much less was known (no 0'''-arguments, very little on random sets). It was possible to have most of what was known in one book. That would be hard now, though Odilfreddi book comes close. Note that Odilfreddi book is in two volumes with a third one to be finished... probably never.
One personal note- I had a course on Recursion theory taught by Herbert Gelernter at Stonybrook (my ugrad school) in the Fall of 1979. We covered the first six chapters of Rogers text. It was a great course from a great book taught by a great teacher and set me on the path to do work in recursion-theoretic complexity theory.
Bill - It was Herbert Gelernter that taught you Recursion Theory, not Harold Gelernter.
ReplyDeleteThanks, fixed.
ReplyDeleteBecause of your correction I was reminded that Herbert Gelernter was actually in AI yet he taught a year long course in Theory of Comp which was first semester- Logic (Godel's completeness and incompleteness theorems) and second semeter Recursion theory (as noted above, the first six chapters of Rogers). He was a brilliant man.
Again the theme of specialization- I think it would be rare nowadays to have someone in AI teach a course in recursion theory. For one thing we are all now more specialized, but also (I think) AI is not as linked to logic as it once was.
Hartley Rogers was my academic grandfather. I learned from his book, even taught from it once. For complexity theorists, there’s a lot of meat in Rogers that didn’t make it into Soare’s book, which has a very different emphasis and style.
ReplyDeleteJim Royer was particularly relieved when the paperback edition of Rogers came out. He had a copy for his office, and a copy at home, but the paperback finally allowed him to fulfill his dream of having a copy for his car...