Should that not be A and BC ? (and AB and C for black) ]]>

From the notes: “Note when the rules are applied arbitrarily many times, we actually understand pretty well by now what is and isn’t possible: that’s a subject called computability theory”

This is an extremely deficient description of the subject. The study of what’s is and isn’t recursive, and (more generally) what is an isn’t recursively approximable (Delta_2), is only a small part of computability theory/recursion theory. Delta_2 sets are only the beginning of a hierarchy of sets (the arithmetical and hyperarithmetical sets) which are extensively studied by recursion theorists. And of course, recursion theorists study many other things, for instance, randomness.

A better description might be “the study of definability in mathematics”, though this is a bit too general (for instance, it includes descriptive set theory, while recursion theorists (usually) only study effective descriptive set theory).

I think part of the problem is that the name computability theory is misleading. The subject was historically called recursion theory, sets were recursive, not computable, etc. This changed around 1996, when Soare published his paper “Computability and Recursion”, suggesting a terminology change from recursive to computable. Many in the field have now adopted this change in terminology. Some even engage in the bizarre practice of changing the word recursive to computable when citing old papers. Soare’s rationale for the change in terminology is twofold: first, the founders of the subject preferred the term computable to recursive (who cares after 60 years of using recursive terminology). And secondly, people unfamiliar with the field don’t understand recursive to mean computable (how much of a problem is this?). To me, the name computability theory suggests only the study of Delta_2 sets (as you’ve written above). It also seems to suggest that complexity theory is a part of computability theory (as Soare has suggested it should be). Frankly, I don’t know of much relation between the two subjects.

]]>Sorry, I was so outraged by the elitism that I didn’t see the egalitarianism.

]]>thanks for all the knowledge Scott!

]]>