FOM: computability & complexity
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
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