[FOM] Recursive invariance
Michael Carroll
mcarroll at pobox.com
Mon Jul 12 01:41:13 EDT 2010
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).
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
Metamathematics."
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.
Michael Carroll
More information about the FOM
mailing list