The University of Aberdeen
The Computing Science Department

CS3518: Formal Languages and Computability

This course provides a basic-level introduction to computability via the notion of a formal language. It does not presuppose familiarity with formal languages and automata. Some familiarity with imperative programming (e.g. in JAVA) and with the basics of set theory is assumed. The functional programming language Haskell is introduced, and this language is used to explore the notion of an infinite set.

  1. Introduction to formal languages
    1. Finite State automata
    2. Regular languages
  2. The functional model of programming
    1. Theory: The lambda calculus
    2. Practice: Programming in HASKELL
  3. The imperative model of programming
    1. Theory: Turing machines
    2. Practice: Programming in Turing machines
  4. Computability
    1. Preliminary material (bijections, cardinality, the Russell paradox)
    2. Abstract (non-constructive) proof that noncomputable problems must exist
    3. Examples of noncomputable problems

Course Database Entry

Lecturer

Kees van Deemter