Revision

The modules COS2601 and COS3701 are about computer theory. We are concerned with the capabilities of different types of machines. In COS2601 you were introduced to the finite automaton. An FA is a very weak type of computer: it is a language acceptor, but has no memory for storing characters. This means that FAs are not able to accept languages such as anbn because they have no way of "remembering" how many characters have been read. These machines also have no way of comparing letters so that a language like PALINDROME cannot be accepted by any FA.

 

In COS3701 we investigate increasingly powerful machines until we reach the ultimate computing machine. This investigation is done in stages. We proceed, via pushdown automata (PDAs) which use a stack as memory, to Turing machines (TMs) which are the most powerful language acceptors that exist. A TM can accept input and produce output. If there is an algorithm for solving a problem we are able to build a TM that gives the answer to the

problem. Turing machines are computationally equivalent to the computers we use today. We finally learn that even these machines cannot accept all languages.

 

We suggest the following programme:

 

  • First you should read through the relevant chapter in Cohen. Do it carefully, but do not waste too much time in trying to understand concepts you find difficult.

  • The next step is then to read the notes for corresponding chapter in these learning units.

  • After having worked carefully through a section in the learning units, you should go through the corresponding section in the textbook again, making sure that you understand everything.

  • Before proceeding to the next chapter, you should tackle the self assessment activities for all the chapters and do assignment question(s) based on the chapter that you have just completed. If you find a question very difficult or impossible to do, you should work through the entire chapter again. 

  • Chapter 20 of the 1997 edition of Cohen on Post Machines is not prescribed study material and may be left out completely