FOM: computability & complexity

Martin Davis martind at cs.berkeley.edu
Sun Aug 23 16:56:09 EDT 1998


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




More information about the FOM mailing list