G12FCO -- Formal Computation

Lecture notes and other supporting materials from a module given by me for the Mathematics Department of Nottingham University in 1999 and other years. Supplied as is, with no warranty as to their continued correctness! Use as you see fit, but please achnowledge this site if you publish or publicise this material.

Quick links:

• general
• content
• lectures
• problem classes
• coursework

General Information:

There will be two lectures per week, and a problem class in alternate weeks. Assessment will be by a two-hour written examination. Coursework will be set, but it will not count for assessment. Lecture notes, problem class notes, coursework and solutions will appear on the Web, in pages referenced from this one [see below]. If you do not already know how to use a Web browser, you are strongly encouraged to find out! From the Web, you can get either soft [disc file] or hard [printed] copies of any of these notes, which you may use as you like for purposes related to the module [but note the copyright; you may not publish them elsewhere, or pass them off as your own work]. Note added 2016: these conditions now relaxed -- ANW

Please note: The information on the Web is for your convenience. You will get the usual sorts of handouts, such as problems, in paper form. I neither require nor expect you to print everything out and read along with it as I lecture!

If you do decide to print everything out using the Department's facilities, you will find it quite expensive [though much cheaper than a textbook, and much faster than writing it out yourself!]. Here are some hints for making it cheaper: (a) You don't have to print to a laserwriter -- any old printer will do. Nor do you have to do it in C30 -- you are welcome to copy the files to floppies and print them off anywhere you find cheap printing facilities. (b) You don't have to print out the whole file -- feel free to take a copy and edit out the headers and footers and anything else you don't really want printed. (c) You can use a smaller font -- students with normal eyesight should be able to read at 6-point size, which gets most of the material onto a single page per lecture. (d) Share with your friends -- print one copy and take photocopies [which can be reduced, double-sided, whatever]. (e) There is a Unix facility, psnup, which will take a PostScript file [obtained by careful setting of options in the `print preview' menu item] and print it 2 or 4 pages to one sheet of paper.

Content:

• Algorithms. The idea of a (computational) process, termination, and correctness; and associated ideas such as invariance, limits, iteration and recursion.
• Complexity. The idea that some processes can be carried out in a `reasonable' time, while others cannot.
• Computability. The idea that some `processes' can be carried out, while others cannot (sometimes even in principle).

Reading:

David Harel: Algorithmics: The Spirit of Computing, Addison-Wesley, 1987, 2nd Ed 1992. QA 1157 HAR

An excellent survey of the field. Written mostly for computing scientists, so the detailed contents are largely irrelevant, but the broad sweep corresponds quite well with my point of view.

Edsger W. Dijkstra: A Discipline of Programming, Prentice-Hall, 1976. QA 928 DIJ

Rather old, but a classic. Ignore the impenetrable programming, and read this for the insights into how to analyse problems, and for the uniquely mournful slightly-fractured English. Covers only the first part of the module.

Edsger W. Dijkstra, W.H.J. Feijen. A Method of Programming, Addison-Wesley, 1988. QA 1145 DIJ

Really a tidied-up and modernised version of the above, which has thereby lost all its character.

Marvin L. Minsky: Computation: Finite and Infinite Machines, Prentice-Hall, 1972. QA 1135 MIN

Another classic, extremely well-written and full of insights, but now showing its age. A revised edition is long overdue. Talks only about what computers can or cannot do, so only covers a small part of the module, but still well worth reading.

Michael R. Garey and David S. Johnson: Computers and Intractability: a Guide to the Theory of NP-completeness, Freeman, 1979. QA 1157 GAR

Mentioned here only because it is still, despite its age, the definitive guide to complexity. Absolutely not light bed-time reading, but indispensable to professional mathematicians in this field.

Christos H. Papadimitriou: Computational Complexity, Addison-Wesley, 1994. QA 1160 PAP

An excellent and well-written survey of complexity. A good source for applications of complexity (e.g. to cryptography), but some chapters are rather difficult.

Henry M. Walker: The Limits of Computing, Jones and Bartlett, 1994. QA920 WAL

A more-or-less non-technical survey, which you may find easier to read than the serious texts above.

Aims, objectives, transferable skills:

Lectures:

The last few lecture slots will be occupied by revision classes; these will be of a nature similar to problem classes, but attendance will not be compulsory. During the `revision week', I shall keep `office hours' at the lecture times for otherwise unscheduled consultations with students. You are, of course, welcome to see me at any other time, whether or not by appointment, but at random times you take pot luck as to whether I am available and in my office.

Problem Classes:

Coursework: