FOM: computability & complexity

[Martin Davis]

At 03:53 PM 8/23/98 -0400, simpson at math.psu.edu wrote:
>  Soare introduces himself as a computability
>theorist.  Wouldn't it be natural for his colleagues to assume that
>his focus is computation, computer science, algorithms, or something
>like that?  

No! Unless they are woefully uninformed.

CS departments have been giving courses in computability theory and in
algorithmic analysis for years; nobody confuses one with the other.

On the other hand, in Russia it is precisely what we call computability or
recursion theory that is called "Theory of Algorithms".

Martin