Starting with Euler's solution to the Seven Bridges of Königsberg problem, we discussed the main definitions and concepts used in graph theory. Exercises included Tournament graphs and Kings, and the handshake problem (couples variant).
Topics covered in this lecture included DFAs and NFAs, (including the extended transition function), and regular expressions and the relationship between FAs and REs. We also covered the Pigeonhole principle, and how to show a language isn't regular using the Pumping lemma. We also looked at palindromes. All exercises are included in the updated slides.
In this lecture we covered the formal definition of Turing Machines, their transition function, and Instantaneous Descriptions (IDs). The notions of acceptance and decidability for TM were briefly presented. We also looked at Non-Deterministic Turing Machines (NTMs), and equivalence. Variations such as multi-tape and multi-track machines were also discussed and shown to be equivalent to the standard TM. We finally discussed the Busy Beaver function and its implications, using a TM simulator. There was also a short discussion of quantum computing.
In this session we looked at total and partial functions, and recursion. Using Haskell notation we defined the factorial and Fibonacci functions using recursion and pattern matching. We then analysed the properties the McCarthy 91 function, and developed inductive proofs of its behaviour. We then discussed and proved the undecidability of the Halting problem, and the relation to the Busy Beaver 'S' function. Lastly, we discussed and sketched a proof of Rice's theorem, and the need to be careful in forming statements.
In this lecture we covered quantum computation, specifically the quantum circuit model. We started with a historical overview,
discussing Shor's factorisation algorithm and Grover's Quantum Database Search. (Notes 1)
We then developed a circuit model of classical, finite, reversible computation - using Tofolli and Fredkin gates, and a discussion of Maxwell's demon. (Notes 2) The basic linear algebra needed for quantum computation was then presented, followed by a development of the quantum circuit model. Lastly, the Deutsch algorithm was presented and analysed. (Notes 3)
Further reading: A full development and description of Shor's algorithm can be found here,
and a continuation of the above notes, including a full formalisation of