Lambda Calculus

9 units · Undergraduate

Intermittent: 9 units An introductory course in classical lambda calculus, with an emphasis on syntax. The course will describe many research problems which are suitable topics for senior theses or master's theses. Topics will include: Basic properties of reduction and conversion; Reduction and conversion strategies; Calculability and representation of data types; Elementary theory of Ershov numberings; Bohm's theorem, easy terms, and other exotic combinations; Solvability of functional equations (unification); Combinatorics and bases; Simple and algebraic types; Labelled reduction and intersection types; Extensionality and the omega rule. Prerequisites: 80-310 or 15-150 or 21-300