Edmund Robinson

Teaching

I am currently teaching DCS301/AMCM060 Computability.

Please see also Course Summary.

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.