[FOM] Recursive invariance
pratt at cs.stanford.edu
Wed Jul 14 03:01:30 EDT 2010
On 7/11/2010 10:41 PM, Michael Carroll wrote:
> Hartley Rogers gives a key role to recursive invariance in his 1967 text
> "Theory of Recursive Functions and Effective Computability." He devotes
> Chapter 4 to it, after his introductory chapters and before plunging into
> details. He also remarks intriguingly that "Our fixed choice of Gödel
> numbering ... appears to be a rather noninvariant feature of our theory" (p.
> 22 in my copy).
You're getting the chronology out of order. The word "appears" is
crucial here. The immediately following sentence on p. 22 promises "We
shall see however (Chapter 4 and Exercise 2-10), that our results
possess an invariant significance independent of this choice." The word
"however" is crucial here: you need to pattern match on
"appears...however". But you probably intuited that anyway.
> Some later texts such as Soare's 1987 "Recursively Enumerable Sets and
> Degrees" follow Rogers in his definition of recursive invariance. But it
> does not seem to be mentioned in either of Smullyan's books, neither his
> 1992 "Gödel's Incompleteness Theorems" nor his 1993 "Recursion Theory for
> I'm having trouble fixing whether Rogers' recursive invariance is generally
> regarded as an important and well-accepted concept in recursive function
> theory, and was hoping FOM subscribers might enlighten me.
I took two courses in recursion theory from Manuel Blum in 1969/70 when
I was a Ph.D. student at Berkeley. The very first thing he talked about
in his first course was acceptable Goedel numberings, which is at the
heart of recursive invariance. (But then you'll notice Manuel's name in
connection with Corollary III(b) of Chapter 4 of Rogers.)
I have no idea why Smullyan did not draw attention to it. I will admit
however that when I taught recursion theory at Stanford I never paid
attention to recursive invariance. It's a valid concern, but I have to
say that I was relieved when Manuel moved on from acceptable Goedel
numberings to what seemed to me at the time more important matters. I
was quite willing back then to forgive every unacceptable Goedel
numbering, being very open-minded in my naivete about every kind of
mathematical object. I later saw the wisdom of keeping the unacceptable
ones on a shorter leash, but I'm not sure I would want to trouble my
students with that distinction early on.
So I think my answer to your question about the importance of recursive
invariance is about the same as for that of vector spaces. Linear
algebra is all about the category of vector spaces over an arbitrary
field and their linear transformations, one of the world's most
important families of categories, but I'd prefer to start the students
off with matrices over the reals.
More information about the FOM