The University of Aberdeen
The Computing Science Department

CS3518:Formal Languages and Computability

This course, which is being revised drastically for the academic year 2014-15, provides a basic-level introduction to computability via the notion of a formal language. The revised course presupposes some familiarity with formal logic and set theory, and with the theory of formal languages and automata, for example as these topics are taught in our CS2013 course on Mathematics for Computing Science. The functional programming language HASKELL is introduced as a device for exploring the notion of an infinite set. If time allows, we shall use PROLOG to illustrate computability in logic. The plan of the course is as follows.

  1. Introductory material
    1. Recap of the theory of relations and functions (e.g., bijections)
    2. Infinite sets and Russell's paradox
    3. Recap of Finite State Automata (with extensions)
  2. The functional model of programming
    1. Introduction to the lambda calculus
    2. Programming in HASKELL
    3. Defining and handling infinite sets in HASKELL
  3. Computability
    1. The notion of an algorithm
    2. Turing Machines
    3. An abstract (non-constructive) proof that noncomputable problems exist
    4. The Halting Problem is undecidable
    5. Logical consequence in dyadic Predicate Logic is decidable
    6. Logical consequence in full Predicate Logic is undecidable

Course Database Entry

Lecturer

Kees van Deemter