Announcements


There are no announcements

Forum

General


This course is part of the MAGIC core.

Description

Turing Computability and Beyond ...
  • Mathematics can bring clarity to questions arising across many disciplines. Any mathematician in the modern information age needs some basic familiarity with the basic concepts and results concerning the relationship between what we can describe and what we can compute.
  • This course aims to introduce students to the seminal ideas of the early pioneers such as Alan Turing, Kurt Gödel and Emil Post, and to trace their legacy through today's research. Their work provides a conceptual and technical basis for constructive mathematics and theoretical computer science; and throws light on research challenges in physics, biology, artificial intelligence, philosophy and the humanities.
  • This will involve a fascinating intellectual adventure, bringing together both technical and philosophical aspects of computability theory. We will start with some history, and proceed via the basics of Turing machines and other models of computation, to more challenging work relating language and computation.
  • We will take time to introduce students to some of today's open questions and controversies regarding the role of incomputability in the contemporary setting.
  • Most of the background and technical side of the course is covered in Parts I and II of my book on Computability Theory - see the bibliography for details. There is a 2nd edition of Computability Theory due out next year, and a draft version has been made available to those registering for this year's course - see the Files. The other books in the bibliography provide background, and pointers to more advanced topics.
  • The course assessment will be via a take-home exam after the end of the course.

Semester

Autumn 2014 (Monday, October 6 to Friday, December 12)

Timetable

  • Mon 11:05 - 11:55
  • Fri 09:05 - 09:55

Prerequisites

There are no specific prerequisites. However, a previous encounter with basic logic, or even a model of computation such as recursive functions or register machines, would ease the way into what is a conceptually challenging area. 'Mathematical sophistication' will be invaluable, and will certainly be enhanced via this course.

Syllabus

  1. Historical background: Hilbert, algorithms and formalism; Gödel, Church, Turing and models computability.
    (1 lecture; see Computability Theory, Chapter 1.)
  2. Classical models of computation: Recursive functions; Turing machines and computable functions; Church-Turing thesis.
    (4 lectures; see Computability Theory, Chapter 2, omitting 2.3.)
  3. Information and universality: Programs as data; the Universal Turing Machine, and the history of the stored program computer; contextual remarks on higher type computation, functionalism, and artificial intelligence.
    (3 lectures; parts of Computability Theory, Chapter 4, plus background and history related to the universal computer and its wider significance.)
  4. Unsolvability and enumerability: Incomputability and unsolvable problems; the Halting Problem and statement of Church's Theorem; undecidable theories; the arithmetical hierarchy; the Normal Form Theorem for computably enumerable sets; Kleene's fixed point theorem. Undecidable theories and Hilbert's 10th Problem (brief account).
    (3 lectures; parts of Computability Theory, Chapters 5-6, omitting 5.4 and 6.2.)
  5. Interactive and relative computation: Oracle Turing machines; the Jump Operator and creative sets; definability, computability, and Post's Theorem. Remarks on natural language, computability and artificial intelligence.
    (4 lectures; selected material from Computability Theory, Chapter 10, omitting 10.6 - with discussion of the relevance of incompatibility to definability over natural contexts.)
  6. Higher order computation and new paradigms: Morphogenesis; higher type computation revisited; introduction to new computational paradigms (neural nets, cellular automata, games, standard model of quantum computation); remarks on embodied computation and the brain.
    (3 lectures; a less technical conclusion to the course, ranging over a number of areas where the mathematics of computability - and in particular higher order computation - can clarify the character and role of causal structure.)
  7. Complexity of computations: Polynomial bounds; non-deterministic Turing machines, guessing, the P =? NP problem.
    (2 lectures; see Computability Theory, Section 11.6.)

Lecturer


Barry Cooper
Email pmt6sbc@maths.leeds.ac.uk
Phone (0113) 3435165
Photo of Barry Cooper


Students


Photo of Ingram BONDIN
Ingram BONDIN
(Leeds)
Photo of Sky  BREWER
Sky BREWER
(York)
Photo of Matthew Burfitt
Matthew Burfitt
(Southampton)
Photo of Long Chen
Long Chen
(York)
Photo of Thomas Coleman
Thomas Coleman
(East Anglia)
Photo of Paolo Comaron
Paolo Comaron
(Newcastle)
Photo of Charles Cox
Charles Cox
(Southampton)
Photo of Cesare Gallozzi
Cesare Gallozzi
(Leeds)
Photo of Chrissy Gavin
Chrissy Gavin
(Surrey)
Photo of James Gay
James Gay
(Leeds)
Photo of Tom Harris
Tom Harris
(Southampton)
Photo of Ewan Johnstone
Ewan Johnstone
(Liverpool)
Photo of John Lawson
John Lawson
(Durham)
Photo of Edd Lewis
Edd Lewis
(Cardiff)
Photo of David Matthews
David Matthews
(Southampton)
Photo of Konstantinos Palapanidis
Konstantinos Palapanidis
(Southampton)
Photo of Edward Prior
Edward Prior
(Sheffield)
Photo of James RILEY
James RILEY
(Leeds)
Photo of George Stagg
George Stagg
(Newcastle)
Photo of Petra Staynova
Petra Staynova
(Leicester)
Photo of ANON STUDENT
ANON STUDENT
(*External)
Photo of Dionysios Syrigos
Dionysios Syrigos
(Southampton)
Photo of Amelia Taylor
Amelia Taylor
(Birmingham)
Photo of David TOTH
David TOTH
(Leeds)
Photo of Jakob VIDMAR
Jakob VIDMAR
(Leeds)
Photo of Andrew Wheadon
Andrew Wheadon
(Exeter)
Photo of Richard WHYMAN
Richard WHYMAN
(Leeds)
Photo of Stephen Worsley
Stephen Worsley
(Liverpool)


Bibliography


Computability TheoryS Barry Cooper
Alan Turing - His Work and ImpactS Barry Cooper and Jan van Leeuwen
The Universal Computer: The Road from Leibniz to TuringMartin Davis
The Emperorʼs New Mind: Concerning Computers, Minds, and the Laws of PhysicsSir Roger Penrose
Alan Turing: The EnigmaAndrew Hodges
Incomputability after Alan TuringS. Barry Cooper
Turing’s Titanic Machine?S. BARRY COOPER


Note:

Clicking on the link for a book will take you to the relevant Google Book Search page. You may be able to preview the book there. On the right hand side you will see links to places where you can buy the book. There is also link marked 'Find this book in a library'. This sometimes works well, but not always. (You will need to enter your location, but it will be saved after you do that for the first time.)

Assessment



There will be a take home examination in January with 2 weeks to complete and submit online. There will be one basic compulsory technical question, and a choice between either (a) two further technical questions (chosen from the relevant parts of the book), or (b) a more conceptual/foundational question relating to the role of computation/computability in mathematics and beyond.
The take home exam will be posted online on January 5, 2015, and your solutions will need to be uploaded by 00:01 GMT on January 19, 2015.

TURING COMPUTABILITY AND BEYOND - Take Home

Files:Exam paper
Released: Monday 5 January 2015 (992.6 days ago)
Deadline: Sunday 18 January 2015 (978.6 days ago)


Files


Files marked L are intended to be displayed on the main screen during lectures.

Week(s)File
0-20cellularForms-HD.mp4L
0-20comp_book_2edn_draft.pdf
0-20Cooper_AMSNotices.pdf
0-20LECTURE1.pdfL
0-20LECTURE10.pdfL
0-20LECTURE11.pdfL
0-20LECTURE12.pdfL
0-20LECTURE13.pdfL
0-20LECTURE14.pdfL
0-20LECTURE15.pdfL
0-20LECTURE16.pdfL
0-20LECTURE17.pdfL
0-20LECTURE2.pdfL
0-20LECTURE3.pdfL
0-20LECTURE4.pdfL
0-20LECTURE5.pdfL
0-20LECTURE6.pdfL
0-20LECTURE7.pdfL
0-20LECTURE8.pdfL
0-20LECTURE9.pdfL
0-20Seething-SD.mp4L
0-20titanic_CACM.pdf


Recorded Lectures


Please log in to view lecture recordings.