Example sheets for the course are available at http://www.dpmms.cam.ac.uk/study.

Thursday, 10 October 2024. No lecture due to Covid infection.

Saturday, 12 October 2024. No lecture due to Covid infection.

First Lecture. Tuesday, 15 October 2024. Decision problems. Examples. Hilbert's Tenth Problem and the negative Davis-Matiyasevich-Putnam-Robinson solution. Asymmetry of positive and negative solutions of decision problems. Notation and definitions. Strings. Countability and uncountability. The set of strings and the set of finite subsets is countable. Lecture Notes.

Second Lecture. Thursday, 17 October 2024. Chomsky: the defining feature of language is recursion. Example of recursion in sentence formation. Rewrite systems. There are countably many rewrite systems over \(\Omega\). Grammars. Examples. Equivalent grammars. Isomorphisms of grammars. Isomorphic grammars are equivalent. There are countably many grammars for fixed sets of symbols. The generated language only depends on the size of the set of variables. There are countably many languages generated by a grammar. Lecture Notes.

Third Lecture. Saturday, 19 October 2024. Noncontracting, context-free, and regular rules, grammars, and languages. The Chomsky hierarchy: are the classes strictly included in each other? Equivalent grammars need not belong to the same Chomsky class. Decision problems: the word problem, the emptiness problem, and the equivalence problem. The word problem for noncontracting grammars is solvable. Closure properties: concatenation, union, complement. The concatenation grammar and when it produces the concatenation of two languages. Lecture Notes.

Fourth Lecture. Tuesday, 22 October 2024. Equivalent variable-based grammars. Type 0, 1, and 2 languages are closed under concatenation. The union grammar. Type 0, 1, and 2 languages are closed under union. Question about regular grammars. The empty word cannot be produced by noncontracting grammars. The basic \(\varepsilon\)-rule. Equivalent \(\varepsilon\)-adequate grammars. Adding the empty word to a language. Essentially regular, context-free, and noncontracting grammars. Regular grammars: terminal and non-terminal rules; number of letters and variables. Analysis of what regular derivations look like. Lecture Notes.

Fifth Lecture. Thursday, 24 October 2024. Regular concatenation and union grammars. Closure of Type 3 languages under concatenation and union. Deterministic automata and their accepted language. Homomorphisms and isomorphisms of automata. Accessible and indistinguishable states and their relation to surjectivity and injectivity of homomorphisms. Homomorphic automata accept the same language. Application: without loss of generality, an automaton never returns to the start state. Lecture Notes.

Sixth Lecture. Saturday, 26 October 2024. Closure of the class of languages accepted by an automaton: complements, product automata, unions and intersections. Translating an automaton into a grammar: every language accepted by an automaton is regular. Non-deterministic automata. Characterisation theorem for regular languages: a language is regular if and only if it is accepted by an automaton (either deterministic or non-deterministic). Subset construction. Lecture Notes.

Seventh Lecture. Tuesday, 29 October 2024. Constructivity of the transformations in the characterisation theorem. The regular pumping lemma. Proof. Examples: \(\{\mathbf{0}^n\mathbf{1}^n\,;\,n>0\}\) is context-free, but not regular. \(\{\mathbf{0}^nw\,;\,w\in\mathbb{W}\}\) is regular, but has no automaton with \(n\) or fewer states. The regular pumping lemma does not characterise regular languages: there are irregular languages that satisfy the regular pumping lemma. The emptiness problem for automata and regular grammars is solvable. Lecture Notes.

Eighth Lecture. Thursday, 31 October 2024. Accessible and distinguishable states. Indistinguishability as an equivalence relation. The quotient automaton. The quotient automaton accepts the same language. Irreducible automata. Injectivity and surjectivity for irreducible automata. Irreducible automata that accept the same language are isomorphic. Construction of a minimal automaton for a language. Algorithm to check whether a state is inaccessible. Algorithm to check whether two states are indistinguishable (proof not complete yet): table filling algorithm. Lecture Notes.

Ninth Lecture. Saturday, 2 November 2024. Proof that the table filling algorithm works. Solvability of the equivalence problem for deterministic automata. Lack of context-freeness in natural language. Intuitive consequences of context-freeness. Parse trees and their parsed word. Characterisation of context-free derivations via parse trees. Lecture Notes.

Tenth Lecture. Tuesday, 5 November 2024. Levels of trees, height of trees. Subtrees of labelled trees. Grafting of labelled trees. Chomsky normal form (CNF). Length of derivations in CNF. CNF-parse trees. Relationship of height of a CNF-parse tree and the parsed word. Unit productions, bad productions, and very bad productions. Removing very bad productions. Unit closed grammars. Every context-free grammar is equivalent to a unit closed grammar. Removing unit productions from a unit closed grammar preserves the language. Lecture Notes.

Eleventh Lecture. Thursday, 7 November 2024. Removing bad productions. Proof of Chomsky's theorem. The context-free pumping lemma or Bar-Hillel lemma. Differences between the regular and the context-free pumping lemma. Proof of the context-free pumping lemma for context-free languages. Lecture Notes.

Twelfth Lecture. Saturday, 9 November 2024. Application of the context-free pumping lemma: \(\{\mathbf{0}^k\mathbf{1}^k\mathbf{2}^k\,;\,k>0\}\) is not context-free. Remarks on memory and storage of possible models of computation: automata only have (bounded) finite memory; a model of computation for context-free languages would need to be able to store on unit of unbounded information, but not to use it without destroying it. Context-free languages are not closed under intersection (and thus not under complementation). The emptiness problem for context-free grammars is solvable. The equivalence problem for context-free grammars is not solvable (without proof). Alan Turing and the general notion of computation: Turing machines and register machines. Basic ideas for the definition of register machines. Lecture Notes.

Thirteenth Lecture. Tuesday, 12 November 2024. States and instructions. Definition of register machines. Configurations/snapshots. Register machines transforming configurations. The computation sequence of a register machine. Halting/converging and diverging. Strong equivalence. There are only countably many register machines up to strong equivalence. Padding Lemma. Partial functions. Performing an operation: first examples. Lecture Notes.

Fourteenth Lecture. Thursday, 14 November 2024. Further examples of operations performed by register machines. Subroutine lemma. An example of the use of the subroutine lemma. Questions and answering questions by a register machine. Basic examples; answering two questions in a row. Case distinction lemma. Repeats of operations. Repeat lemma. Examples: moving and copying information between registers. Lecture Notes.

Fifteenth Lecture. Saturday, 16 November 2024. More examples of operations performed by register machines. Scratch space. Computable functions; examples. Characteristic and pseudocharacteristic functions. Computable and computably enumerable sets. The class of computable sets is closed under complements. Every computably enumerable set is computable. Every regular language is computable. Coding numbers as binary sequences: the shortlex order and the hash function \(\#\). Lecture Notes.

Tuesday, 19 November 2024. No lecture due to Influenza A infection.

Sixteenth Lecture. Thursday, 21 November 2024. Encoded numerical functions. Computability for numerical functions. Computability and computable enumerability for numerical sets. Examples, in particular, the successor function (with proof). Applications of the use of codes for numbers in computations: reference to digits and truncated computations. Primitive recursive functions: composition and recursion. Facts about primitive recursive functions can be proved by induction. Primitive recursiveness for functions on \(\mathbb{B}\). Examples: addition, multiplication, exponentiation. Lecture Notes.

Seventeenth Lecture. Saturday, 23 November 2024. More examples of primitive recursive functions: predecessor, truncated subtraction, absolute difference, and remainder. Applications: Merging and splitting words; remarks on bounded search with arithmetical bounds. Minimisation and Church's recursive functions: recursive functions can be partial, all primitive recursive functions are total. Coding languages by blocks of binary strings. Coding register machines in a concrete coding language. Lecture Notes.

Eighteenth Lecture. Tuesday, 26 November 2024. Coding instructions and register machines. Coding configurations. The sets of codes are regular languages. The transformation function and the computation sequence are computable. The software principle. Remarks on the history of computing machines. Proof of the software principle. The \(s\)-\(m\)-\(n\) Theorem. Lecture Notes.

Nineteenth Lecture. Thursday, 28 November 2024. The halting problem and its two-parameter version. The halting problem is c.e., but not computable (diagonalisation argument). \(\Sigma_1\), \(\Pi_1\), and \(\Delta_1\) sets. Every computable set is \(\Delta_1\). Characterisation of c.e. sets as \(\Sigma_1\). The zigzag method: folding two quantifiers into one; parallelising searches. Characterisation of c.e. sets as ranges of computable functions. Lecture Notes.

Twentieth Lecture. Saturday, 30 November 2024. Characterisation of computable sets as \(\Delta_1\). The c.e. sets are not closed under complementation. All Type 0 languages are c.e. Characterisation of Type 0 languages as c.e. sets (without proof). Closure properties: computable and c.e. sets are closed under union and intersection. The Church-Turing Thesis: equivalence of various conceptually different notions of computability. Identification of algorithmic solvability with the notion of computability. The word problem, emptiness problem, and equivalence problem in coded form. The word problem for Type 0 languages is not solvable. Lecture Notes.

Twenty-first Lecture. Tuesday, 3 December 2024. Partial preorders. Quotients by equivalence relation gives the partial order of degrees. Reduction functions; many-one reducibility and many-one equivalence. Connections between many-one reducibility, computability, and computable enumerability. Proof techniques to prove that a problem is not solvable. Hardness and completeness. Every nontrivial computable set is \(\Delta_1\)-complete. The halting problem is \(\Sigma_1\)-complete. Picture of the many-one degrees. Turing join: example of a set that is neither c.e. nor co-c.e. Index sets. Nontriviality. Examples. Lecture Notes.

Twenty-second Lecture. Thursday, 5 December 2024. Rice's Theorem. Unsolvability of the emptiness problem for Type 0 grammars. Additional information from the proof of Rice's Theorem. Solvability of the equivalence problem implies the solvability of the emptiness problem. Unsolvability of the equivalence problem for Type 0 grammars. Lecture Notes.