Higher Type Computability: Platek-Scott-Ershov Computability
- Date: Wednesday 18 January 2017, 14:00 – 15:30
- Location: Mathematics Level 8, MALL 1 & 2, School of Mathematics
- Type: Pure Mathematics seminars, Proofs, constructions and computations seminars, Seminar series
- Cost: Free
Stan Wainer, University of Leeds. Part of the proofs, constructions and computations seminar series.
Two contrasting notions of computability on higher types will be briefly surveyed, both tracing back to the 1960s, and neither receiving as much attention nowadays as they deserve. The recent book by John Longley and Dag Normann "Higher-Order Computability" (Springer 2015) is an excellent source of up-to-date material.
Lecture 1: Kleene Recursion in Higher Types See least week.
Lecture 2: Platek-Scott-Ershov Computability
Information systems and the Scott topology. Function spaces as information systems. Computability here means the object is given by a c.e. set of finite approximations. Plotkin\'s theorem: a partial continuous functional is computable iff it is recursively definable from fixed schemes pcond, valmax and \exists.
Stan Wainer, University of Leeds