F29FB Foundations 2

Prof Fairouz KamareddineDr Joe WellsDr Hind Zantout

Course co-ordinator(s): Prof Fairouz Kamareddine (Edinburgh), Dr Joe Wells (Edinburgh), Dr Hind Zantout (Dubai).


  • 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.


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 Methods: Due to covid, assessment methods for Academic Year 2021/22 may vary from those noted on the official course descriptor. Please see:
- Maths (F1) Course Weightings 2021/22
- Computer Science (F2) Course Weightings 2021/22
- AMS (F7) Course Weightings 2021/22

SCQF Level: 9.

Credits: 15.