ECM3404 Logic and Computation
Study Resources for 2008-09
Level 3 module taught by Dr
Antony Galton
General information
Lecture notes
Overheads
Tutorials
Continuous assessment
Exercises
Examinations
Software
Web links
Recommended reading
Except where otherwise indicated, material available below is in the
form of PDF files.
STOP PRESS
Revision session at 12 noon on Tuesday 26th May in Room 215.
Summary information sheet
Lectures take place in Semester 2
on Mondays at 9 a.m. in Harrison 106 and
on Fridays at 9 a.m. in Harrison 209.
Tutorials
take place in Harrison 254 on Tuesdays at 4 p.m. in weeks 28, 30, 33, 40, and 42.
Continuous Assessment. There will be one piece of continuous assessment, counting for 20% of the module mark.
Examinations. There will be a two-hour, unseen closed-book written
examination in May/June.
TOP OF PAGE
These will be posted here nearer the time of the lectures.
Natural Deduction: All the rules
Logic as a Formal System (Lectures 5-7)
Turing Machines (Lectures 8-12)
NP-completeness and Cook's Theorem (Lectures 13-15)
Gödel's Incompleteness Theorems
TOP OF PAGE
These will be posted here nearer the time of the lectures. Some details will be omitted from the slides until after the lecture in which they have been shown.
Exercise sheets for the group meetings will be posted here shortly
before the tutorials are scheduled to take place.
Sample solutions will be posted after the meetings have taken place.
10th February: Natural Deduction
with solutions
24th February: Peano Arithmetic
with solutions
3rd March: More examples on Peano Arithmetic
with solutions.
20th March: Turing machines
with solutions.
5th May: NP-completeness and Cook's Theorem with solutions
12th May: Gödel numbering
Due 19th March 2009: Exercise on Natural Deduction and Peano Arithmetic with solutions
TOP OF PAGE
These are unassessed exercises to be done in your own time.
TOP OF PAGE
Past examination papers
(please note that there have been changes in the module content
since the module began in 1998-99):
There are no papers for 2003 and 2005 since the module was not delivered in those years.
June 2008 with
specimen answers.
June 2007 with
specimen answers.
June 2006 with
specimen answers.
June 2004
September 2002 (referred paper)
with specimen answers
June 2002
2001
with specimen answers
2000
with specimen answers
1999 (hard copy of solutions available
from AG on request)
TOP OF PAGE
Here is the source code for a simple Turing Machine simulator in java.
(Instructions for how to run it are given in the comments at the beginning of the code.)
Here are quintuple listings for some Turing Machines that can be run on this simulator:
TOP OF PAGE
Useful starting-points for finding out about
Gödel
and
Turing.
The Alan Turing Home
Page (Andrew Hodges)
The Church-Turing Thesis
A short and readable article on Gödel and the limits of logic (with some nice pictures).
TOP OF PAGE
University library classification in square brackets.
-
Keith Devlin, Goodbye, Descartes: The End of Logic and the Search
for a New Cosmology of the Mind, John Wiley and Sons, Inc., 1997.
Highly readable and informative, he is good on logic and computation
and stresses the limitations of logic as well as its power. [153 DEV]
-
David Harel, Computers Ltd: What they really can't
do. Oxford University Press, 2000. Highly readable survey of
computability and complexity and their implications. Intended for the
lay reader, but it makes a good introduction to this
module. [001.64 HAR]
-
Martin Davis, The Universal Computer: The Road from Leibniz to Turing.
W. W. Norton and Co., 2000. Readable account covering the contributions of
Leibniz, Boole, Frege, Cantor, Hilbert, Gödel, and Turing.
[001.6409 DAV]
-
Rolf Herken, The Universal Turing Machine: A Half-Century
Survey. Oxford Science Publications, 1988. A very useful collection
of articles on logic, Turing Machines, computation, etc. [511.3 UNI]
-
Jean van Heijenoort, From Frege to Gödel: A Source Book in
Mathematical Logic, 1879--1931. Contains Gödel's completeness and
incompleteness papers. [164 HEI/X]
-
Martin Davis, The Undecidable: Basic Papers on Undecidable
Propositions, Unsolvable Problems, and Computable Functions. Raven
Press, New York, 1965. Contains Gödel's incompleteness
paper and Turing's Entscheidungsproblem paper. [510.1 UND]
-
Richard Jeffrey, Formal Logic: Its Scope and Limits,
McGraw-Hill, 1981. Explains the Truth Tree method, and discusses
completeness and incompleteness. [160 JEF]
-
Ernest Nagel and James Newman, Gödel's Proof, Routledge and
Kegan Paul Ltd, 1958. A gentle introduction for the general reader.
[510.1 NAG]
-
Christof Teuscher (ed.),
Alan Turing: Life and Legacy of a Great Thinker,
Springer, 2004. A very interesting collection of essays covering all aspects of Turing's life and work. (See in particular the chapter by Michael Beeson on `The Mechanization of Mathematics'.) [510.92 TUR]
-
Antony Galton, 'The Church-Turing Thesis: Its Nature and Status', in P. Millican and A. Clark (eds.), Machines and Thought, Oxford: Clarendon Press, 1996. [001.535 MIL]
- Antony Galton, 'The Church-Turing Thesis: Still valid after all these years?', Applied Mathematics and Computation, 178 (2006), 93-102. [Copies available from APG]
TOP OF PAGE
Antony Galton