[Colloquium] Theory Seminars at Computer Science
Donna Brooms
donna at cs.uchicago.edu
Mon Oct 7 07:44:41 CDT 2013
*REMINDER*
THEORY SEMINAR
Monday, October 7, 2013
2:30 p.m.
Ryerson 251
Yuri Gurevich
Microsoft Research (Washington)
Research.microsoft.com/~gurevich
Title: Semantics-to-syntax analyses of algorithms
Abstract: Alan Turing pioneered semantics-to-syntax analysis of algorithms. You start with a large species of algorithms, and you finish up with a syntactic artifact that characterizes the species, typically a kind of machines that compute all and only the algorithms of the species.
The task of analyzing a large species of algorithms seems daunting if not impossible. As in quicksand, one needs a rescue point, a fulcrum. In computation analysis, a fulcrum is a particular viewpoint on computation that clarifies and simplifies things to the point that analysis become possible.
We review from that point of view Turing's analysis of human-executable computation, Kolmogorov's analysis of sequential bit-level computation, Gandy's analysis of a species of machine computation, and our own analysis of sequential computation.
We also discuss limitations of semantics-to-syntax analyses.
Hosts: Prof. Soare and Prof. Razborov
*Refreshments will be served after the talk at 3:30 in Ryerson 255*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20131007/bcfe2365/attachment.htm
More information about the Colloquium
mailing list