# Edmund Robinson

## Teaching

I am currently teaching DCS301/AMCM060 Computability.

See here for course materials (available to QM account holders only): https://intranet.dcs.qmul.ac.uk/courses/coursenotes/DCS301/

### Encoding of datatypes and countability

• 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

### Turing’s Account of Computability

• 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

### Universal 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.

### Other accounts of computability

• 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.

### Coverage of the notion of computability

• 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

### Partial Recursive Functions

• 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.).

### Primitive Recursion

• 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.