Mathematical Foundations of Computer Science
 Lecturers:
 Professor Cristian S. Calude,
room 303427, Science Building, course coordinator.
 Professor Fred Kroon,
room 443 Arts 1.

Tutor and marker:
Yan Kolezhitskiy. Office hours:
By appointment.
 Marker:
Stefano Stollenwerk Cavallaro.

Class representative:
Catherine Williams.
 Taught: First semester 2018, three hours of lectures and a tutorial repeated twice) a week
(see 2018 Academic Dates).

Timetable: Lectures: Monday, Wednesday, Thursday 15.0016.00, OGHLLecTh/102G36. Tutorials: Thursday 10.0011.00, OCH2/104G54 and Friday 12.0013.00, MLT3/303101, starting the second
week. Check updates at UoA Timetables 2018.
 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:
 Mathematical backgrgound refresh
 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 quantum
 prove the undecidability or complexity of a variety of problems
 understand the issue of whether there are limits of computability
 understand the basic principles of quantum computing
 Textbook:
M. Sipser.
Introduction to the Theory of
Computation,
PWS Publishing Company, Boston, 2013, third edition.
 Software: Register machine simulation
 Assessment: Tutorial work: 5%. Three assignments: 15%, Test: 30%, Exam: 50%.
 Assignments (sumitted via Canvas):
Assignment 1:
due on 23 March 2018,
worth 5%;
assignment 2:
due on 4 May 2018,
worth 5%; assignment 3:
due on 1 June 2018,
worth 5%. All assignments must be prepared using an appropriate wordprocessing application [diagrams may be handdrawn], converted to PDF format, and uploaded in Canvas before 23.55 of the due date.
 Any problem
related to marking should be addressed to the tutor and/or marker.

Test:
26 March 2018, in class, time: 15:0016:00 in OGHLLecTh/102G36 and Conf. Centre Lecture Theater/423342.
Test preparation.
 Canvas: COMPSCI350.
 Handouts: Part 1,
Part 3.
 Regulations:
 Other relevant sites: