LFCS Seminar Tuesday 8th July: John Longley

Title: Computability theory of PCF

Abstract: This talk is the 4th in a short series of 4 tutorial lectures covering
some classic material from higher-order computability theory. The
lectures cover classic material rather than very recent research.
They contain fundamental ideas that have proved to be of enduring
interest, but are perhaps not so easy to learn from books and papers.
These lectures reflect some of my recent ideas for presenting this
material as I work on the second edition of my book with Dag Normann on the
subject.


Lecture 4 will cover the following material:


An interpreter for NSPs in (a mild variant of) PCF.

NSP equality as a robust notion of observational equivalence for PCF
terms.

Other non-trivial programs in PCF. Properties of PCF-computable
functionals.