• Lecturers:
  • Professor Cristian S. Calude, room 303-575, Science Building, course coordinator.
  • Professor Fred Kroon, Arts 2, 18 Symonds St., Level 2, Room 202.
  • Tutor: Alastair Abbott and Damien Desfontaines. Office hours: By appointment, room 576. Any problem related to marking should be addressed to the tutor.
  • Class representative: Nick Stones-Havas
  • Taught: First semester 2013, three hours of lectures and a tutorial a week (see 2013 Academic Dates).
  • Timetable: Lectures: Monday 12-13, Geo/301-1060, Wednesday 10-11, Geo/301-1060, Thursday 14-15, Geo/301-1060. Tutorials: Tuesday 11-12, LawSmall/803-210, starting the second week. Check updates at COMPSCI Timetable.
  • Short Description: The aim of this paper is to present mathematical models for computers and computation, and derive results about what can and cannot be computed. It deals with idealised computers (automata) which operate on idealised input and output (formal languages). For example, we prove that it is impossible to write a computer program that takes as input any computer program and tells us whether or not that program will end up in an endless loop (the halting problem). Quantum computing will also be briefly described and the Church-Turing Thesis will be critically discussed. In addition we will discuss some problems in algorithmic complexity. We assume you are comfortable with formal mathematical proofs and can write them properly.
  • Content:
    • Automata and regular languages
    • Computability and decidability
    • Algorithmic complexity
    • Church-Turing Thesis
    • Beyond Turing
  • Expected learning outcomes: On completion, students will be able to
    • explain the theoretical limits on computational solutions of undecidable and inherently complex problems
    • describe concrete examples of computationally undecidable or inherently infeasible problems from different fields
    • understand formal definitions of machine models, classical and unconventional
    • prove the undecidability or complexity of a variety of problems
    • understand the issue of whether there are limits of computability
  • Textbook: M. Sipser. Introduction to the Theory of Computation, PWS Publishing Company, Boston, 2013, third edition.
  • Software: Register machine simulation
  • Recommended Reading:
    • J. E. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, Addison Wesley, Boston, 2001, second edition.
    • John C. Martin. Introduction to Languages and the Theory of Computation Mc Graw-Hill, Boston, 2003, third edition.
  • Tutorials: Materials will be available on Cecil.
  • Assessment: Three assignments worth 20% in total, Test: 30%, Exam: 50%
  • Assignments (the assignment dropbox will be outside the room 303-576): Assignment 1: due Friday 5 April, before 4.00pm, worth 7%; assignment 2: due Friday 17 May, before 4.00pm, worth 6%; assignment 3: due Friday 7 June, before 4.00pm, worth 7%. Sample solutions: Assignment 1.
  • Test: 1 May, in class.Test preparation. Sample Solutions.
  • Congratulations to: Tim Von Ahsen for solving a bonus question!
  • Handouts (subject to changes): Part 1, Prof. Calude's lectures. Part 3, Prof. Calude's lectures.
  • Policy on Cheating
  • Other relevant sites:
    • Church-Turing thesis in Wikipedia, Stanford Encyclopedia of Philosophy, Wolfram MathWorld
    • Grail: A Symbolic Computation Environment for Finite-State Machines
    • A Toolbox to Manipulate Finite-state Automata
    • Gödel
    • Gödel's incompleteness theorem
    • Introductions and Tutorials in Quantum Computing
    • Gödel Machine