production
Skip to Content

CS3518: LANGUAGES AND COMPUTABILITY (2020-2021)

Last modified: 21 Oct 2020 10:35


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
Session Second Sub Session 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?

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?

No

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

  • 1 Practical during University weeks 26 - 34, 38

More Information about Week Numbers


In light of Covid-19 and the move to blended learning delivery the assessment information advertised for courses may be subject to change. All updates for first-half session courses will be actioned no later than 1700 (GMT) on 18 September 2020. All updates for second half-session courses will be actioned in advance of second half-session teaching starting. Please check back regularly for updates.

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
Knowledge LevelThinking SkillOutcome
Sorry, we don't have this information available just now. Please check the course guide on MyAberdeen or with the Course Coordinator

Exam

Assessment Type Summative Weighting 75
Assessment Weeks Feedback Weeks

Look up Week Numbers

Feedback
Learning Outcomes
Knowledge LevelThinking SkillOutcome
Sorry, we don't have this information available just now. Please check the course guide on MyAberdeen or with the Course Coordinator

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
Knowledge LevelThinking SkillOutcome
Sorry, we don't have this information available just now. Please check the course guide on MyAberdeen or with the Course Coordinator

Exam

Assessment Type Summative Weighting 75
Assessment Weeks Feedback Weeks

Look up Week Numbers

Feedback
Learning Outcomes
Knowledge LevelThinking SkillOutcome
Sorry, we don't have this information available just now. Please check the course guide on MyAberdeen or with the Course Coordinator

Course Learning Outcomes

Knowledge LevelThinking SkillOutcome

Compatibility Mode

We have detected that you are have compatibility mode enabled or are using an old version of Internet Explorer. You either need to switch off compatibility mode for this site or upgrade your browser.