Mathematical Foundations of Computer Science
 Lecturers:
 Professor Cristian S. Calude,
room 303575, Science Building, course coordinator.
 Professor Fred Kroon,
Arts 2,
18 Symonds St.,
Level 2,
Room 202.

Tutor:
Rong Wang. Office hours:
By appointment, room 303576. Any problem
related to marking should be addressed to the tutor.

Class representative:
David MillacDuccant.
 Taught: First semester 2014, three hours of lectures and a tutorial a week (see 2014 Academic Dates).

Timetable: Lectures: Tuesday 1617, Science Center, 303101, Thursday 1516, Arts 1/209, Friday 1516, Arts 1/209. Tutorial: Tuesday 1718, Biology Building/100, 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 ChurchTuring 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
 ChurchTuring 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 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
 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 303575): Assignment 1:
due Monday 7 April, before 4.00pm,
worth 7%;
assignment 2:
due Monday 19 May, before 4.00pm,
worth 7%;
assignment 3:
due Friday 6 June, before 4.00pm, worth 6%.
Sample solutions: Assignment 1.

Test:
Tuesday 29 April, in class.Test preparation.
Sample Solutions.
 Handouts (subject to changes):
Part 1, Prof. Calude's lectures. Part 3, Prof. Calude's lectures.
 Policy on
Cheating
 Other relevant sites: