FOM: computability & complexity

Martin Davis martind at
Sun Aug 23 16:56:09 EDT 1998

At 03:53 PM 8/23/98 -0400, simpson at 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".


More information about the FOM mailing list