[Colloquium] Theory Seminar at Computer Science

[Donna Brooms]

*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/7153c225/attachment.htm