F29FB - Foundations 2

Course leader(s):

Fairouz Dib Kamareddine (Edinburgh, January)
Joe Wells (Edinburgh, January)
Hind Zantout (Dubai, January)
Thomas Anung Basuki (Malaysia, January)

Aims

Mathematical background; enumerability; countable and uncountable sets; diagonalisation; Gödel numbering; 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?

Syllabus

Learning outcomes

By the end of the course, students should be able to do the following:

differentiate between computable and non-computable functions in terms of effective procedures and Turing machines.
calculate the size of countable sets using enumerability techniques.
differentiate between finite/infinite sets; and between infinitely countable and uncountable sets.
determine that a set (e.g., the set of reals, or the set of all functions on the natural numbers) is uncountable using relevant techniques (e.g. diagonalisation).
determine the countability of a set using Goedel numbering (e.g., the set of computable functions is countable by virtue of Goedel numbering the set of all the Turing machines).
use reducibility between problems to deduce their (un)solvability.
show unsolvability of problems using Turing machines (e.g., the unsolvability of the halting problem).
analyse the complexity of problems.

Further details

Curriculum explorer: Click here

SCQF Level: 9

Credits: 15