Turing Machines and the Birth of Computability in Logic



Overview

Nowadays, we are taking computers almost for granted, but how was the 'idea' of a computer even conceived at first, and by whom? This course will provide a detailed introduction to the groundbreaking work of one of the most brilliant individuals in our history, Alan Turing, and how his idea of a machine that can perform a large number of operations relies on simple basic mathematical concepts and procedures.

All the mathematical knowledge required will be covered and practised during the course, which will also provide an overview of the historical development of the idea of 'computers' and 'computability'. We will then discover the idea of computational 'complexity' and how this has a positive effect on our lives (e.g. cryptography). Therefore, we will introduce the language and formalism of Logic to appreciate its incompleteness and draw connections with computability. 

Programme details

Courses starts: 21 Apr 2023

Week 0: Course Orientation

Week 1: Turing Machines

Week 2: Functions and Proof by Induction

Week 3: Computability

Week 4: The Universal Turing Machine

Week 5: Alan Turing, the 'Entscheidungsproblem', and WWII

Week 6: Introduction to Logic

Week 7: Logic and CNF-formulae

Week 8: Complexity and NP-problems

Week 9: Cryptography and P vs. NP 

Week 10: Incompleteness of Logic and Gödel

Certification

Students who register for CATS points will receive a Record of CATS points on successful completion of their course assessment.

To earn credit (CATS points) you will need to register and pay an additional £10 fee per course. You can do this by ticking the relevant box at the bottom of the enrolment form or when enrolling online.

Coursework is an integral part of all weekly classes and everyone enrolled will be expected to do coursework in order to benefit fully from the course. Only those who have registered for credit will be awarded CATS points for completing work at the required standard.

Students who do not register for CATS points during the enrolment process can either register for CATS points prior to the start of their course or retrospectively from the January 1st after the current full academic year has been completed. If you are enrolled on the Certificate of Higher Education you need to indicate this on the enrolment form but there is no additional registration fee.

Fees

Description Costs
Course Fee £238.00
Take this course for CATS points £10.00

Tutor

Dr Niccolò Salvatori

Dr Niccolo Salvatori is a Guest Teacher at the London School of Economics and a former Honorary Research Associate of King's College London. In the past, he has lectured Calculus for the University of California, Berkeley for study abroad programmes and has recently joined the Department of Continuing Education, Oxford. Niccolo also teaches at Secondary School and Sixth Form level, including Further Mathematics, and has been creating and delivering projects and enrichment courses for A-Level students since 2017. His interests are in Analysis and Geometry, but he is passionate about Logic and has great admiration for the work of Alan Turing and its far-reaching consequences.

Course aims

To introduce the rigorous definition of computability and complexity, and provide historical and theoretical foundations to concepts and methods in Computer Science.

Course objectives

1. To learn how to describe instructions for basic operations in the language of Turing Machines and how the Entscheidungsproblem was solved.

2. To understand the historical and conceptual aspects of the birth of computers.

3. To learn and use formal logic while appreciating its limitations.

4. To understand and describe how limitations of our ability to compute/solve have positive repercussions on our daily life.

Teaching methods

Students will have access to a pre-recorded lecture to be watched in advance of the weekly online session.

Learning outcomes

By the end of the course students will be expected to be able to:

1. describe what a Turing Machine is;

2. create instructions for a Turing Machine to compute basic operations;

3. translate sentences in CNF-formulae and calculate their satisfiability;

4. describe the concepts of computability, complexity, and incompleteness;

5. articulate clearly and in detail what consequences computational complexity has on daily life and why.

Assessment methods

Short exercises and a short report:

A set of short exercises and a short report (between 1,000 and 1,500 words) will be set in Week 6 and will constitute the assessment for the award of the 10 CATS points. Some of the exercises will be presented before Week 6 when the relevant topic will be discussed and can be submitted once before the deadline to receive feedback and improve.

Students must submit a completed Declaration of Authorship form at the end of term when submitting your final piece of work. CATS points cannot be awarded without the aforementioned form - Declaration of Authorship form

Application

We will close for enrolments 7 days prior to the start date to allow us to complete the course set up. We will email you at that time (7 days before the course begins) with further information and joining instructions. As always, students will want to check spam and junk folders during this period to ensure that these emails are received.

To earn credit (CATS points) for your course you will need to register and pay an additional £10 fee per course. You can do this by ticking the relevant box at the bottom of the enrolment form or when enrolling online.

Please use the 'Book' or 'Apply' button on this page. Alternatively, please complete an application form.

Level and demands

GCSE Mathematics 

Essential knowledge:

• GCSE level algebra.

• GCSE level number facts and procedures (e.g.: basic operations, factorization, sequences of numbers, etc.).

Desirable knowledge

• Definition of a function and composition of functions.

Most of the Department's weekly classes have 10 or 20 CATS points assigned to them. 10 CATS points at FHEQ Level 4 usually consist of ten 2-hour sessions. 20 CATS points at FHEQ Level 4 usually consist of twenty 2-hour sessions. It is expected that, for every 2 hours of tuition you are given, you will engage in eight hours of private study.

Credit Accumulation and Transfer Scheme (CATS)

10 CATS points

Terms & conditions for applicants and students

Information on financial support