Formal Languages and Calculability

• Mathematical Formalism and Proof Techniques
• Infinite Sets and Computable Numbers
• Boolean Logic Circuits as basic computational model, Shannon's Counting Argument
• Languages and Chomsky's Hierarchy
• Finite State Automata and Regular Languages
• Push-Down Automata and Context-Free Languages
• Recursively Enumerable Languages and Turing Machines
• The Halting Problem and Decidability
• Computability, the (Extended) Church-Turing thesis, Rice's Theorem.
• From Computability to Complexity
• Physics and Computability
• Quantum Computability

• Lecture Notes v.2.8 (28May26)

• Introductory Slides

• Infinite Sets and Computable Numbers

• The CYK Algorithm