F29FB - Foundations 2
Course leader(s):
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
1. computable and non computable functions and the size of their sets
2. Enumerability, cardinality, and the size of sets
3. Uncountability
4. Encoding and Goedel Numbering
5. Turing Machines, Effective Computability, Non-Computability of the Halting problem
6. Reducibility and Solvability and Their USe in deducing Computability/non-Computability
7. Costly problems and complexity
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
