Mathematical Foundations of Computer Science
- Professor Cristian S. Calude,
room 303S-571, Science Building, course coordinator.
- Professor Fred Kroon,
18 Symonds St.,
Marcus Triplett. Office hours:
By appointment. Any problem
related to marking should be addressed to the tutor.
Kiran Anthony Foster.
Course Facebook group.
- Taught: First semester 2015, three hours of lectures and a tutorial a week (see 2015 Academic Dates).
Timetable: Lectures: Tuesday 15-16, Wednesday 16-17, Thursday 15-16. Tutorial: Friday 13-14, , starting the second
Check updates at UoA Timetables 2015 .
- 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
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
- Automata and regular languages
- Computability and decidability
- Algorithmic complexity
- Church-Turing Thesis
- Quantum computing
- 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 quantum
- prove the undecidability or complexity of a variety of problems
- understand the issue of whether there are limits of computability
Introduction to the Theory of
PWS Publishing Company, Boston, 2013, third edition.
- Software: Register machine simulation
- Tutorials: Materials will be available on the Tutorial page.
- Assessment: Three assignments worth 20% in total, Test: 30%, Exam: 50%
- Assignments (the assignment dropbox will be outside the room 303S-571): Assignment 1:
due Monday 30 March, before 4.00pm,
due Friday 15 May, before 4.00pm,
due Friday 5 June, before 4.00pm, worth 6%.
Sample solutions: Assignment 1.
Thursday, 2 April 2015, 3.00pm-4.00pm, during the lecture.Test preparation.
- Handouts (subject to changes):
Part 1, Automata. Part 3, Complexity and Quantum Computing.
- Policy on
- Other relevant sites: