UNSW Handbook Course - Logic and Computability

Logic and Computability - MATH3421


	Faculty: Faculty of Science
	School: School of Mathematics
	Campus: Kensington Campus
	Career: Undergraduate
	Units of Credit: 6
	Contact Hours per Week: 4
	Enrolment Requirements:
	Prerequisite: MATH1081 or MATH1090.
	Offered: Semester 1 2005
	Fee Band: 2

Description

Software is written in the language of logic, and logic is the science on which computing is based. This course develops the classical mathematics of propositional and predicate logic and automata, which inspired the founders of computing such as Turing and von Neumann. Topics include Propositional calculus: formal proofs and the Deduction theorem; consistency, completeness, compactness, independence of axioms. Predicate calculus: interpretations; axiomatisations; soundness, completeness and compactness theorems; nonstandard analysis; Peano arithmetic and Godel's incompleteness theorems. Automata: deterministic and non-deterministic finite automata, regular languages. Computability: algorithms; Turing machines, computable and uncomputable functions; Church's thesis, different formalisations of computation; unsolvable problems; recursive functions:

URL for this page:

© The University of New South Wales (CRICOS Provider No.: 00098G), 2004-2011. The information contained in this Handbook is indicative only. While every effort is made to keep this information up-to-date, the University reserves the right to discontinue or vary arrangements, programs and courses at any time without notice and at its discretion. While the University will try to avoid or minimise any inconvenience, changes may also be made to programs, courses and staff after enrolment. The University may also set limits on the number of students in a course.