Theory of Computation - COMP4141


	Faculty: Faculty of Engineering
	School: School of Computer Science and Engineering
	Course Outline: www.cse.unsw.edu.au/~cs4141
	Campus: Kensington Campus
	Career: Undergraduate
	Units of Credit: 6
	EFTSL: 0.12500 (more info)
	Indicative Contact Hours per Week: 4
	Enrolment Requirements:
	Prerequisite: COMP2911 or MATH2301.
	Fee Band: 2 (more info)
	Further Information: See Class Timetable

Description

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)