G13CS3 -- Mathematical Aspects of Computing

Quick links:

• general
• aims, objectives and transferable skills
• content
• reading
• lectures
• supplementary material
• bottom of page

General Information:

Module aims, objectives and transferable skills

Objectives: By the end of the module, you should understand the inherent limitations of computing and be able to construct simple proofs of uncomputability or infeasibility, and should be able to relate a range of automata to equivalent computers or mathematical constructs.

Transferable skills: The analysis of problems for feasibility and complexity; an appreciation of the computational ability of a wide range of mechanisms; and the use of the Web as a teaching and learning resource.

Outline of the Module

Reading

• A good compromise is Computational Complexity, by C. H. Papadimitriou (Addison-Wesley, 1994). Bits of this are very readable, but it's dense in places, and you have to have read earlier chapters to understand the notation in later ones.
• Computation -- Finite and Infinite Machines, by M. Minsky (Prentice-Hall, 1967) is old, indeed ancient, but very good. It's out of print, but the library has several copies. It covers a large fraction of the module.
• Most of the rest is covered by another classic, Computers and Intractability by M. R. Garey and D. S. Johnson, (Freeman, 1979); this book is not, however, light bed-time reading.
• Algorithmics: the Spirit of Computing, by D. Harel (Addison-Wesley, 1987) is a more modern text that gives an overview of most topics in the module.

Lectures

There is another source of information [besides the textbooks mentioned above, and any other private reading which you may (and are encouraged to!) do] which you should use in conjunction with lecture notes; this is the Web, and the relevant material comes in two parts. This document is at URL

http://cuboid.me.uk/anw/G13CS3

The second part of this resource is the set of pages for the Formal Computation module, G12FCO [obtainable by clicking from my home page, or on the `anchor' in this sentence, or by the obvious change from the above URL]. This is the last year in which G13CS3 will be given, as a result of the new 3/4-year degree structure working its way through the system, and G12FCO is a partial replacement. In fact, the last twelve lectures of that module are concerned with material that is also covered here [and indeed were written from my notes for this module], but in a quite different order. The pages for those lectures comprise quite detailed lecture notes. However, there is quite a lot of material in this module which is not in G12FCO [as you would expect, comparing 20+ 3rd-yr lectures with 12 2nd-yr lectures], and even where there is substantial overlap the focus and the sophistication will not be the same. Nevertheless, you may find this other material useful.

You should not feel that consulting the Web pages is an instant imperative without which you are irretrievably sunk. They are intended to supplement lectures, and, for example, to give extended explanations in detail that would be tedious in lectures. Nor should you feel that you have to rush to C30 and print them off on the LaserWriter. You can read Web pages from any computer in the world as long as it is suitably connected, and any cheap printer should be perfectly adequate, and you are welcome to copy the source of the page and edit it down to just the bits you need and/or to copy it to a file which you can use as you like, or indeed just to browse it on the screen and take your own written notes.

Supplementary Material

[This is where cross-references will appear as the module progresses. Numbers refer to lectures.]

1. [Nothing to add.]
2. For a modest discussion of FSMs, see G12FCO, lecture 15.
3. There is a page of examples of McCulloch-Pitts cells. See Minsky for much, much more.
4. The relation between FSMs, their powers, the bracket-matching problem, and Turing machines is covered in G12FCO, lecture 16. New: For some working Turing machines see Andrew Hodges' Turing Scrapbook and pages referenced therefrom (your browser needs to be Java-aware). [Andrew Hodges wrote an excellent biography of Turing.]
5. See G12FCO, lecture 17 for a somewhat stripped down version of this lecture. Minsky, chapters 5, 6, 7 and 8, is a good source for this material; most other books get bogged down in the formal logic.
6. The end of G12FCO, lecture 17 gives the `Halting Problem' proof; the version in this lecture has better diagrams! See G12FCO, lecture 18 and, as always, Minsky for some other relevant stuff.
7. G12FCO, lecture 19 is about computability of numbers and functions; largely `borrowed' from Minsky.
8. G12FCO, lecture 20 is about minimalist computers, and has some diagrams. We go just a little further in this module.
9. I have no good reference for the cellular automata stuff. I'll write a web page about it `soon'; do not hold your breath!
10. Likewise!
11. Here we more-or-less rejoin G12FCO, at about lecture 9. Some of the earlier G12FCO lectures may also prove slightly helpful, but in this module we are not doing algorithms in any systematic way. Of the mentioned texts, Papadimitriou and Garey and Johnson do some of this stuff but much more formally; Harel would be a better bet for an overview.
12. Non-deterministic TMs and oracles are in G12FCO, lecture 10.
13. For transformations, see G12FCO, lecture 11. There are different possible transformation rules, which I'm skating over rather quickly here. Papadimitriou covers this in great detail. At the moment, we don't know whether these different regimes are `really' different, so it's largely a matter of convenience.
14. Cook's Theorem is sketched in G12FCO, lecture 11. This is a bit of an `Ouch!' topic. Papadimitriou has a fairly elegant proof, but it's a house of cards, and it's hard to understand his proof without going through the whole of his first eight chapters in some detail. Garey and Johnson give a rather brutal proof; if you first accept that languages and programs are essentially the same thing, and then don't mind their notation, then their proof is messy but straightforward. In this module, we take a somewhat intermediate position; fleshed out from the one in G12FCO, but sketched from G&J. The idea is much more important than the detail.
15. A few simple NP-complete problems are shown [with pretty pictures!] in G12FCO, lecture 12. We'll do a few more in this module, based mainly on Garey and Johnson but with occasional nods to Papadimitriou [which has some more modern and neater proofs]. [Well, I was going to, but it was getting boring! -- ANW]
16. This material is sketched in G12FCO, lecture 13. Extra waffle in this module!
17. Also partly based on material somewhat covered in G12FCO, lecture 13. Garey and Johnson is fairly opaque on this material, but it is covered in Harel and in Papadimitriou.
18. Pass.
19. Cryptography is well covered in Papadimitriou; G12FCO, lecture 14 is based on my lecture notes.
20. Last lecture; continuation of the previous one!

Solutions to Exercises 1, Exercises 2, and Exercises 3 are now available.

ANW

top of page