• Lecturers:
• Professor Cristian S. Calude, room 810-839, course coordinator.
• Dr. Andrew Withy, room 206-449, Arts 1.
• Tutor and marker: Yan Kolezhitskiy. Office hours: By appointment.
• Marker: Manuel Aguero.
• Taught: First semester 2021, three hours of lectures and a tutorial repeated four times) a week
• Short Description: The aim of this course is to present mathematical models for computers and computation, classical and quantum, and to prove results about what can and cannot be computed. It deals with idealised computers which operate on idealised input and output. For example, one proves that it is impossible to write a computer program that takes as input any computer program and tells whether or not that program will finish running or continue forever (the halting problem). Various methods to evaluate algorithmic complexity and prove undecidability, as well as efficient strategies, classical and quantum, for problem solving will be presented. The Church‐Turing Thesis will be critically discussed. This course requires that students have a good knowledge of mathematical proofs and can write them properly.
• Content:
  • Mathematical backgrgound refresh
  • 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
  • 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
• Any problem related to marking should be addressed to the tutor and/or marker.
• Canvas: COMPSCI350.
• Other relevant sites:
  • Church-Turing thesis in Wikipedia, Stanford Encyclopedia of Philosophy, Wolfram MathWorld
  • A Toolbox to manipulate finite-state automata
  • Gödel
  • Gödel's incompleteness theorem
  • Gödel machine
  • A movie about Gödel
  • On The Turing Completeness of PowerPoint
  • Turing Test