Higher Type Computability: Platek-Scott-Ershov Computability

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