production
Skip to Content

Log In

  1. University Home
  2. Catalogue of Courses
  3. Undergraduate
  4. 2016-2017
  5. Computing Science
  6. CS3518: LANGUAGES AND COMPUTABILITY

CS3518: LANGUAGES AND COMPUTABILITY (2016-2017)

Last modified: 28 Jun 2018 10:27


Course Overview

This course provides a basic-level introduction to computability - what can and cannot be computed in principle - via the notion of a Turing Machine. The course explores concepts of infinity, recognisability, and decidability, which are crucial to computability. The course assumes some initial familiarity with a programming language along with the basics of set theory, predicate logic, and finite state machines. A functional programming language is used as a way to get 'hands on' with some of the concepts.





Course Details

Study Type Undergraduate Level 3
Session Second Sub Session Credit Points 15 credits (7.5 ECTS credits)
Campus None. Sustained Study No
Co-ordinators
  • Dr Adam Wyner

Qualification Prerequisites

None.

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?

No

Course Description

  • Set theory, functions, and enumerability: Bijections, infinite sets, Cantor's diagonal argument.
  • Languages and their associated automata.
  • Lambda Calculus and Functional programming: Lambda conversion and abstraction, programming language idioms, types, recursion, higher-order functions, list comprehension, lazy evaluation, infinite sets.
  • Turing machines: Turing machines, Turing decidability, Turing recognisability, the Halting Problem, the Church-Turing Thesis.
  • Implications of the Halting Problem.

Further Information & Notes

Assistive technologies may be required for any student who is unable to use a standard keyboard/mouse/computer monitor. Any students wishing to discuss this further should contact the School Disability Co-ordinator.


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 31 August 2023 for 1st half-session courses and 22 December 2023 for 2nd half-session courses.

Summative Assessments

1st Attempt: 1 two-hour written examination (75%); continuous assessment (25%).

Resit: 1 two-hour written examination (75%); continuous assessment mark carried forwards (25%).

Only the marks obtained on first sitting can be used for Honours classification.

Formative Assessment

During lectures, the Personal Response System and/or other ways of student interaction will be used for formative assessment.

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.

Course Learning Outcomes

None.
 

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.