## CS103 Machines, Languages and Computation, 2015

Here are the lecture slides and other materials for CS103 Machines, Languages and Computation.

### Class Notices

• The second Class Test will be held on Friday 4th December.

### Semester 1: Assignments

• Workbook 1: Exercises for Weeks 2-4 of the class.
• Workbook 2: Exercises for Weeks 5 & 6 of the class.
• Workbook 3: Exercises for Weeks 7-11 of the class.

### Semester 1: Practicals

• Practical 1: Calculating Collatz sequences.
• Figure 1: Algorithm for calculating Collatz sequences..

### Semester 1: Lecture Slides

• Lecture 1: Introduction: computers are programmable devices that solve problems; all computers are mathematically equivalent.
• Lecture 2: Proof and formal systems: the idea of proof; direct proof; introducing the MIU system from Gödel, Escher, Bach.
• Lecture 3: More on proof: dealing with infinite sets in proofs; a simple direct proof; a proof by contradiction that the set of prime numbers is infinite.
• Lecture 4: MI MU?: a recap of the prime number proof; the MIU system; searching for proofs by computer; what happens when we search for MU?
• Lecture 5: Proof and infinite sets: definition of sets, both finite and infinite; proving theorems for all members of the natural numbers using Proof by Induction.
• Lecture 6: Recap of proof by induction; making progress with our decision procedure for MIU using arguments based on the I-count of a string.
• Lecture 7: Functions and Algorithms: what is a problem in Computer Science, what is an algorithm and why are algorithms so important?
• Lecture 8: Functions and Mappings: the mathematical view of functions; an introduction to "potato diagrams".
• Lecture 9: Dogs and Collars: mapping from dogs to collars and back again; why there are more real numbers than integers.
• Lecture 10: Non-Computable Functions: A proof that there are more functions in the world than there are computer programs.
• Lecture 11: Languages and Recursion: What are languages and what structure do they have? We take a first look at grammars and I pose a challenge problem: can you generate sentences with more than one adjective?
• Lecture 12 Strings and Recursion: In this lecture we characterise languages as abstract strings of characters which conform to a given pattern. We also introduce regular expressions and ask: is it possible to generate L = anbn using only context-free rules?
• Lecture 13: Knowledge and Inference: Using MIU-like rules to represent facts and rules about the world; how to use symbolic rules to make inferences; a simple approach to knowledge engineering.
• Lecture 14: More Rules and Recursion: representing the ancestor relation to find out who Bart's ancestors are; working backwards from the goal using a proof tree.
• Lecture 15: The Lambda Calculus: The Lambda Calculus: how to specify functions using symbols; functions as first class objects; what is the type of λf.f 3?
• Lecture 16: Functions and Demons: how to get an infinite line of demons to calculate the factorial function for you; recursive functions in Python.
• Python functions developed in Lecture 16. If you want to try these out, right click on the link and select "Save link as...", then right click on the file and select "Edit with IDLE".

John Levine, 26th November 2015.