![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Yuri Gurevich, Microsoft Research Redmond, USA 
Tuesday 09 February 2016, 16:00-17:00
What is an Algorithm?
- đ¤ Speaker: Yuri Gurevich, Microsoft Research Redmond, USA đ Website
- đ Date & Time: Tuesday 09 February 2016, 16:00 - 17:00
- đ Venue: SW01
Abstract
The title problem is of obvious interest to theorists. We will explain its importance to software engineering, in particular to specification, testing and verification of software and hardware.
Wasn’t the problem solved by Turing? No. Of course Turing’s contribution was pivotal, but the problem remained open, even for sequential algorithms. We argue that problem cannot be solved in full generality because the notion of algorithm is still evolving. But certain species of algorithms have matured sufficiently to become amenable to foundational analysis. This applies first of all to sequential algorithm.
In the main part of the lecture we formalize the notion of sequential algorithms in full generality. Then we will mention the other species of algorithms that have been formalized in full generality. Finally, we will describe some applications of this research, in particular at Microsoft.
Series This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.
Included in Lists
- All Talks (aka the CURE list)
- bld31
- Cambridge talks
- Computing and Mathematics
- Department of Computer Science and Technology talks and seminars
- Interested Talks
- Logic and Semantics Seminar (Computer Laboratory)
- Martin's interesting talks
- School of Technology
- SW01
- tcw57âs list
- Trust & Technology Initiative - interesting events
- yk373's list
- yk449
Note: Ex-directory lists are not shown.