There are no announcements
This course is part of the MAGIC core.
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.
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
- 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
- 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
- The course assessment will be via a take-home exam after the end of the course.
Autumn 2014 (Monday, October 6 to Friday, December 12)
- Mon 11:05 - 11:55
- Fri 09:05 - 09:55
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.
- Historical background: Hilbert, algorithms and formalism; Gödel,
Church, Turing and models computability.
(1 lecture; see Computability Theory, Chapter 1.)
- Classical models of computation: Recursive functions; Turing machines and computable functions;
(4 lectures; see Computability Theory, Chapter 2, omitting 2.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.)
- 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.)
- 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.
lectures; selected material from Computability Theory, Chapter 10, omitting 10.6 - with discussion of the relevance of incompatibility to definability over natural contexts.)
- 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
(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.)
- Complexity of computations: Polynomial bounds; non-deterministic Turing
machines, guessing, the P =? NP problem.
(2 lectures; see Computability Theory, Section 11.6.)
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.)
TURING COMPUTABILITY AND BEYOND - Take Home
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.
|Released:|| Monday 5 January 2015 (992.6 days ago)|
|Deadline:|| Sunday 18 January 2015 (978.6 days ago)|
Files marked L are intended to be displayed on the main screen
Please log in to view lecture recordings.