Course co-ordinator(s): Dr Joe Wells (Edinburgh).
Aims:
- To introduce basic notions of computability.
- To understand two models of computability: the lambda-calculus and Turing machines.
- To understand which functions can be computed.
Detailed Information
Pre-requisite course(s): F17SC Discrete Mathematics .
Location: Edinburgh.
Semester: 2.
Syllabus:
Enumerability; countability and non-countability; Goedel numbering; Turing machines; review of the lambda-calculus; computable and non computable functions; Turing computability; Solvability and reduction of decision problems; Church’s thesis and effective computability
Learning Outcomes: Subject Mastery
Understanding, Knowledge and Cognitive Skills Scholarship, Enquiry and Research (Research-Informed Learning)
Become competent with enumerability, Turing machines, encoding functions with the lambda-calculus, Goedel numbering, & computability
Learning Outcomes: Personal Abilities
Industrial, Commercial & Professional Practice Autonomy, Accountability & Working with Others Communication, Numeracy & ICT
- Understand basic mathematical thinking as it applies to computability.
- Become aware of limits of computing.
Assessment Methods:
Assessment: Examination: (weighting – 70%) Coursework: (weighting – 30%)
Re-assessment: Examination: (weighting – 100%)
SCQF Level: 9.
Credits: 15.