This course covers the theoretical computer science areas of formal languages and automata, computability and complexity. Topics covered include the following: regular and context-free languages; finite automata and pushdown automata; Turing machines; computability - halting problem, solvable, and unsolvable problems; space and time complexity; classes P, NP and PSPACE; NP-Completeness.
Additional source review: awaiting review. Published wording is shown below.
Saved requirements encoded for automatic checks. These are prototype interpretations, not ANU decisions or degree-completion checks.
Requisite and Incompatibility
To enrol in this course you must be studying Master of Computing OR Master of Computing (Advanced). Incompatible with COMP3630.
Referenced entries (1)
Links and code mentions retain their original context above. They may describe options, prerequisites or exclusions.
- COMP3630 · 2027 · saved source not linked
Learning Outcomes
Upon successful completion, students will have the knowledge and skills to:
Demonstrate advanced knowledge of formal computation and its relationship to languages
Distinguish different computing languages and classify their respective types
Recognise and comprehend formal reasoning about languages
Demonstrate a competent understanding of the concepts of complexity theory
Published offerings
Future offerings are indicative. Only recognised 2027 sessions with a published class number are offered in the enrolment demo.
| Year | Session | Class number | Class start date | Last day to enrol | Census date | Class end date | Mode Of Delivery | Class Summary |
|---|---|---|---|---|---|---|---|---|
| 2027 | First Semester | 5421 | 22 Feb 2027 | 01 Mar 2027 | 31 Mar 2027 | 28 May 2027 | In Person | N/A |
| 2028 | First Semester | 6693 | 21 Feb 2028 | 28 Feb 2028 | 31 Mar 2028 | 26 May 2028 | In Person | N/A |
Complete offering text
ANU utilises MyTimetable to enable students to view the timetable for their enrolled courses, browse, then self-allocate to small teaching activities / tutorials so they can better plan their time. Find out more on the Timetable webpage. The list of offerings for future years is indicative only. Class summaries, if available, can be accessed by clicking on the View link for the relevant class number. 2027 2028 First Semester Class number Class start date Last day to enrol Census date Class end date Mode Of Delivery Class Summary 5421 22 Feb 2027 01 Mar 2027 31 Mar 2027 28 May 2027 In Person N/A First Semester Class number Class start date Last day to enrol Census date Class end date Mode Of Delivery Class Summary 6693 21 Feb 2028 28 Feb 2028 31 Mar 2028 26 May 2028 In Person N/A
Source evidence (1 saved copy)
Matching copies share this record. Their original file locations and checksums are retained.
assets/Courses/Computational Foundations/6000/Theory of Computation/Theory of Computation - ANU.html
Published ANU page · saved page URL
SHA-256: 296c06e70c820cae83912010f6301cc25f9ff47b9e3bdf904394406a8cdb0639