I am currently teaching **DCS301/AMCM060 Computability**.

Please see also Course Summary.

- Understand definitions of injective, surjective and bijective functions
- Understand what it means for a set to be countable
- Demonstrate equivalence between definitions given by injective function into N and surjective function from N.
- Exhibit standard encodings of data structures: pairs, tuples, lists, trees.
- Understand and reproduce Cantor’s diagonal argument for uncountability as instanced for: real numbers, infinite sequences, functions from N

- Understand Turing’s abstract definition of a computing machine
- Understand and explain Turing’s tabular definition of machine.
- Be familiar with the conventions used by Turing in his formal account (eg notions of m-function, and F-squares).
- Design simple Turing machines

- Understand Turing’s construction of a universal machine
- Be able to explain the encoding of machines, and how the universal machine simulates any given machine.
- Show undecidability results using the universal machine.

- Understand and be able to explain the correspondence between Turing Machines and while programs.
- Understand the definition of recursive functions, and how they can simulate Turing Machines, understand the broad basis of the argument for the reverse simulation.
- Be familiar with a number of generalisations of Turing machines (eg variations in alphabet and number of tapes), and understand the basic principles of their equivalence with standard Turing machines.

- Understand Turing’s arguments for the generality of his notion of computation.
- Understand the potential limits of this notion of computation in the context of:
- Modern networked computers
- Human cognition

- Understand the definitions of partial recursive functions and general recursive functions, and their link with Turing computability.
- Understand the notions of recursive set and recursively enumerable set.
- Be familiar with the φn notation for partial recursive functions, and be able to use it to, eg show the undecidability of the halting problem.
- State Kleene’s smn theorem and explain its proof in broad outline (though not in detail).
- State and prove Rice’s Theorem.
- State the Rice-Shapiro theorem and explain its proof in broad outline (though not in detail).
- Understand the use of Rice’s theorem and the Rice-Shapiro theorem in showing that the sets of indices for various classes of functions are not recursive (or not r.e.).

- Understand the definition of the class of primitive recursive functions
- Be able to produce definitions of functions that demonstrate they are primitive recursive
- Be familiar with Ackermann’s function and understand the structure of the argument that shows it is not primitive recursive.
- Be familiar with the statement of Kleene’s Normal Form Theorem, and the strategy used in proving it (though not the detail).
- Understand the link between bounded search and primitive recursion and unbounded search and general recursion through the Kleene Normal Form theorem.