I081 Lambda calculus

Faculty of Informatics
Spring 2001
Extent and Intensity
2/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium).
Teacher(s)
prof. RNDr. Jiří Zlatuška, CSc. (lecturer)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Jiří Zlatuška, CSc.
Timetable
Mon 9:00–10:50 B410
Prerequisites (in Czech)
( I007 Computability || I008 Computational Logic )&& M009 Algebra II
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
Course objectives
Pure lambda-calculus: lambda-terms, structure of terms, equational theories.
Reductions: one-way transformations, general reductions, beta-reduction.
Lambda-calculus and computations: coding, recursive definitions, lambda-computability, fixed-point combinators, undecidable properties.
Modification of the theory: combinatory logic, extensionality, eta-reduction.
Typed lambda-calculus: types and terms, normal forms, set models, strong normalization, types as formulae.
Domain models: complete partial orders, domains, least fixed points, partiality.
Domain construction: compound domains, recursive domain construction, limit domains.
Syllabus
  • Pure lambda-calculus: lambda-terms, structure of terms, equational theories.
  • Reductions: one-way transformations, general reductions, beta-reduction.
  • Lambda-calculus and computations: coding, recursive definitions, lambda-computability, fixed-point combinators, undecidable properties.
  • Modification of the theory: combinatory logic, extensionality, eta-reduction.
  • Typed lambda-calculus: types and terms, normal forms, set models, strong normalization, types as formulae.
  • Domain models: complete partial orders, domains, least fixed points, partiality.
  • Domain construction: compound domains, recursive domain construction, limit domains.
Literature
  • ZLATUŠKA, Jiří. Lambda-kalkul. 1. vyd. Brno: Masarykova univerzita, 1993, 264 s. ISBN 8021008261. info
  • BARENDREGT, H. P. Lambda calculus : its syntax and semantics. Rev. ed. Amsterdam: Elsevier, 1998, xv, 621 s. ISBN 0-444-86748-1. info
  • HINDLEY, J. Roger and J. P. SELDIN. An Introduction to Combinators and the (lambda)-calculus. Cambridge: Cambridge University Press, 1986, 360 s. ISBN 0521318394. info
  • AMADIO, Roberto M. and Pierre-Louis CURIEN. Domains and Lambda calculi. Cambridge: Cambridge University Press, 1998, xvi, 484. ISBN 0521622778. info
Assessment methods (in Czech)
přednášky a samostané studium dle literatury zadané přednášejícím
Language of instruction
Czech
Further comments (probably available only in Czech)
The course is taught once in two years.
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/fi/spring2001/I081