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 core material: An interpreter for NSPs in (a mild variant of) PCF. Other non-trivial programs in PCF. NSP equality as a robust notion of observational equivalence for PCF terms. Additional potential material: Properties of PCF-computable functionals. These lectures follow a special format. We will have a formal 50 minute seminar covering all or most of the core material that the later lecture will build in. John kindly agreed to continue with an informal session following the talk including an extended Q&A and covering additional material that later lectures do not require. We are recording both parts of the talk. Subject to unforeseen technical problems and subject to my available time for editing the videos, I plan to upload them to our YouTube channel: https://www.youtube.com/@lfcsseminar9233/playlists<https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.youtube.com%2F%40lfcsseminar9233%2Fplaylists&data=05%7C02%7C%7Ccebb650e1c2f42a8aef308ddb7b14e34%7C2e9f06b016694589878910a06934dc61%7C0%7C0%7C638868694320085446%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=rPhvyA2j0pic%2Fu0c533e0YIMrLMVSCr1lrlo5T6k0e8%3D&reserved=0> Jul 08 2025 16.10 - 17.00 LFCS Seminar Tuesday 8th July: John Longley John Longley, Lecture 4, University of Edinburgh https://homepages.inf.ed.ac.uk/jrl/ Tue, 08 Jul, 4.10pm Venue: IF G.03 Informatics Forum G.03
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 core material: An interpreter for NSPs in (a mild variant of) PCF. Other non-trivial programs in PCF. NSP equality as a robust notion of observational equivalence for PCF terms. Additional potential material: Properties of PCF-computable functionals. These lectures follow a special format. We will have a formal 50 minute seminar covering all or most of the core material that the later lecture will build in. John kindly agreed to continue with an informal session following the talk including an extended Q&A and covering additional material that later lectures do not require. We are recording both parts of the talk. Subject to unforeseen technical problems and subject to my available time for editing the videos, I plan to upload them to our YouTube channel: https://www.youtube.com/@lfcsseminar9233/playlists<https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.youtube.com%2F%40lfcsseminar9233%2Fplaylists&data=05%7C02%7C%7Ccebb650e1c2f42a8aef308ddb7b14e34%7C2e9f06b016694589878910a06934dc61%7C0%7C0%7C638868694320085446%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=rPhvyA2j0pic%2Fu0c533e0YIMrLMVSCr1lrlo5T6k0e8%3D&reserved=0> Jul 08 2025 16.10 - 17.00 LFCS Seminar Tuesday 8th July: John Longley John Longley, Lecture 4, University of Edinburgh https://homepages.inf.ed.ac.uk/jrl/ Tue, 08 Jul, 4.10pm Venue: IF G.03 Informatics Forum G.03
Jul 08 2025 16.10 - 17.00 LFCS Seminar Tuesday 8th July: John Longley John Longley, Lecture 4, University of Edinburgh https://homepages.inf.ed.ac.uk/jrl/ Tue, 08 Jul, 4.10pm Venue: IF G.03
