- 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.
Course Description: Link to Official Course Descriptor.
Pre-requisite course(s): F17SC Discrete Mathematics .
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?
Learning Outcomes: Subject Mastery
Understanding, Knowledge and Cognitive Skills Scholarship, Enquiry and Research (Research-Informed Learning)
- Understanding functions and gaining competence with recognizing, specifying, and using them.
- Understanding how computation and its limits are mathematically modeled and reasoned about.
Learning Outcomes: Personal Abilities
Industrial, Commercial & Professional Practice Autonomy, Accountability & Working with Others Communication, Numeracy & ICT
- Awareness of the limits of computing and how to assess whether a problem is solvable at all.
- Increased fluency in reading theoretical research in the field.
Assessment: Examination: (weighting – 70%) Coursework: (weighting – 30%)
Re-assessment: Examination: (weighting – 100%)
SCQF Level: 9.