Yuri Gurevich: Selected recorded talks

Axiomatic definition of sequential algorithms
2011-03-30 Microsoft Channel 9 Lecture 3 on Algorithms
* What are sequential algorithms?
* Postulate 1 (Sequential Time)
* Postulate 2 (Abstract State)
* Postulate 3 (Bounded Exploration)
* Axiomatic definition
* Representation Theorem
What's an algorithm?
2011-02-07 Microsoft Channel 9 Lecture 2 on Algorithms
* Is it possible to define algorithms?
* What kind of entities are algorithms?
* Why bother to define algorithms?
* Algorithms = Turing machines ?
Algorithms and computablitlity
2010-06-02 Microsoft Channel 9 Lecture 1 on Algorithms
* Euclid's algorithms and his time
* One classification of algorithms
* Turing's analysis of symbolic algorithms
* Computability and decidability
* Limitations of the Turing machine model
* On the verge of computational complexity
2010-02-02 Microsoft Channel 9 interview

The interview, conducted by Charles Torre of Channel 9, touched upon a number of topics.
* Logic in Soviet Union.
* A critique of functional programming and declarative specifications.
* The analysis of algorithms that motivated the introduction of abstract state machines. The is by far the longest piece of the conversation.
* A recent article When two algorithms are the same?
* A quick motivation of a new Distributed Knowledge Authorization Language (DKAL).
* The sequential character of human thought.
2009-06-02 lecture on Church-Turing thesis at Google

It is the same lecture as the #1 but to a different audience with different questions.
2009-01-20 lecture on Church-Turing thesis at Microsoft

The lecture was organized by the Association for the Advancement of Artificial Intelligence of Greater Seattle

ABSTRACT:    The Church-Turing thesis is one of the foundations of computer science. The thesis heralded the dawn of the computer revolution by enabling the construct of the universal Turing machine which led the way, at least conceptually, to the von Neumann architecture and first electronic computers. One way to state the Church-Turing thesis is as follows: A Turing Machine computes every numerical function that is computable by means of a purely mechanical procedure.
       It is that remarkable and a priori implausible characterization that underlies the ubiquitous applicability of digital computers. But why do we believe the thesis? Careful analysis shows that the existing arguments are insufficient. Kurt Gödel surmised that it might be possible to state axioms which embody the generally accepted properties of computability, and to prove the thesis on that basis. That is exactly what we did in a recent paper with Nachum Dershowitz of Tel Aviv University.
       Beyond our proof, the story of the Church-Turing thesis is fascinating and scattered in specialized and often obscure publications. We try to do justice to that intellectual drama.