CS3518: Languages And Computability

CS3518: LANGUAGES AND COMPUTABILITY (2020-2021)

Last modified: 05 Aug 2021 13:04

Course Overview

This course provides a basic-level introduction to computability via the notion of a Turing Machine. Some familiarity with imperative programming (e.g., in JAVA) and with the basics of set theory (e.g., the notion of a bijection) is assumed. The Functional language Haskell (familiar from earlier courses, including CS2013) is used to explore the concepts of infinity, recognisability and decidability, which are crucial to computability.

Course Details

Study Type	Undergraduate	Level	3
Term	Second Term	Credit Points	15 credits (7.5 ECTS credits)
Campus	Aberdeen	Sustained Study	No
Co-ordinators	Dr Matthew. Collinson Dr Bruno Yun

Qualification Prerequisites

Either Programme Level 3 or Programme Level 4

What courses & programmes must have been taken before this course?

CS2013 Mathematics for Computing Science (Passed)
Any Undergraduate Programme (Studied)

What other courses must be taken with this course?

None.

What courses cannot be taken with this course?

None.

Are there a limited number of places available?

Course Description

Imperative languages and their associated automata: Regular languages and Finite state automata (FSA), Context-free languages and Pushdown Automata (PDA), Non-context-free languages and linear-bounded automata (LBA), Turing Machines (TM), nondeterministic Turing Machines.
Functional languages: Haskell idioms, Haskell polymorphic types, recursion, Haskell higher-order functions, lazy evaluation, infinite sets.
Chomsky hierarchy and computability: Turing decidability, Turing recognisability, injections, surjections and bijections, Cantor's diagonal argument, the halting problem, the Church-Turing Thesis.

Contact Teaching Time

Information on contact teaching time is available from the course guide.

Teaching Breakdown

More Information about Week Numbers

Details, including assessments, may be subject to change until 21st September 2026 for Term 1 and Full Year courses and 8th January 2027 for Term 2 courses.

Summative Assessments

Assessment Type	Summative	Weighting	25
Assessment Weeks		Feedback Weeks		Look up Week Numbers
Feedback	Formative feedback for in-course assessments will be provided in written form. Additionally, formative feedback on performance will be provided informally during practical sessions.

Learning Outcomes

Sorry, we don't have this information available just now. Please check the course guide on or with the Course Coordinator
Knowledge Level	Thinking Skill	Outcome

Exam

Assessment Type	Summative	Weighting	75
Assessment Weeks		Feedback Weeks		Look up Week Numbers
Feedback

Learning Outcomes

Sorry, we don't have this information available just now. Please check the course guide on or with the Course Coordinator
Knowledge Level	Thinking Skill	Outcome

Formative Assessment

There are no assessments for this course.

Resit Assessments

Resubmission of failed elements

Assessment Type	Summative	Weighting	25
Assessment Weeks		Feedback Weeks		Look up Week Numbers
Feedback

Learning Outcomes

Sorry, we don't have this information available just now. Please check the course guide on or with the Course Coordinator
Knowledge Level	Thinking Skill	Outcome

Exam

Assessment Type	Summative	Weighting	75
Assessment Weeks		Feedback Weeks		Look up Week Numbers
Feedback

Learning Outcomes

Sorry, we don't have this information available just now. Please check the course guide on or with the Course Coordinator
Knowledge Level	Thinking Skill	Outcome

Course Learning Outcomes

Knowledge Level	Thinking Skill	Outcome

Factual	Remember	ILO’s for this course are available in the course guide.

51cg