Handbook - Theory of Computation

There is a more recent version of this academic item available.

Overview

Computability: formal languages and problems, Turing Machines (TMs), computability, (semi-)decidability, universal TMs, Church-Turing thesis, halting problem, reduction and undecidability proofs, examples; Complexity: run time, space, complexity classes, non-determinism and NP, polynomial reductions and NP completeness, optimisation problems and approximation, randomisation; Languages and Automata: regular expressions and languages, finite automata, determinisation, context-free grammars and languages (CFLs), Chomsky normal form, word problems, pumping lemma, push-down automata, decidability problems for CFLs; Semantics and Correctness: while programs, assertions and program correctness, Hoare logic, loops and loop invariants, relative completeness of Hoare logic (and its role in a proof of Gödel's incompleteness result)

Conditions for Enrolment

Prerequisite: MATH1081, and COMP1927 or COMP2521

Delivery

In-person - Standard (usually weekly or fortnightly)

Please note that the above delivery information is an indication on how this course may be delivered within the year. Delivery mode(s) for each term can be viewed on other sources such as myUNSW and class timetable site.

This Handbook is a comprehensive catalogue of our offerings and includes courses that can be taken to satisfy program requirements irrespective as to their availability for a particular year. Availability of courses is best checked using filters on this site or on the class timetable site.

Course Outline

To access course outline please visit below link (Please note that access to UNSW Canberra course outlines requires VPN):

COMP4141 Course Outline

Fees

Type	Amount
Commonwealth Supported Students (if applicable)	$994
Domestic Students	$5970
International Students	$5970

Disclaimer

Where a fee is displayed as “Not Applicable”, including some Work Experience and UNSW Canberra courses, please contact the relevant Faculty for any enquiry.

Note that the University reserves the right to vary student fees in line with relevant legislation. The fee information is provided as a guide and more specific information about fees, including policy, can be found here.

Commonwealth Supported Students:

Please refer to the information about new Student Contribution band classifications. Note that grandfathering arrangements are applicable for some cohorts of students, and other special arrangements apply for a limited number of programs. The Field of Education displayed on the right-hand side of this page may be applicable in understanding which fee rate will apply to you.

Where a Commonwealth Supported fee is displayed it does not guarantee that such places are available.

Pre-2019 Handbook Editions

Access past handbook editions (2018 and prior)

Pre-2019 Handbook Editions