Course co-ordinator(s): Prof Fairouz Kamareddine (Edinburgh), Dr Joe Wells (Edinburgh), Dr Hind Zantout (Dubai), Dr Thomas Basuki (Malaysia).
Aims:
- To ensure students correctly understand the needed mathematics, in particular: functions and how to logically specify them.
- To understand computability.
- To understand a specific model of computability: Turing machines.
- To understand the limits of computability and how we know these limits.
Detailed Information
Course Description: Link to Official Course Descriptor.
Pre-requisite course(s): F17SC Discrete Mathematics .
Location: Dubai, Edinburgh, Malaysia.
Semester: 2.
Syllabus:
Mathematical background; enumerability; countable and uncountable sets; diagonalization; Gödel numbering; Turing machines (TMs); computable and uncomputable functions; Turing computability; the Halting Problem; solvability and reduction of decision problems; Church's thesis and effective computability; nondeterministic TMs; P = NP?
SCQF Level: 9.
Credits: 15.