Formal Languages and Calculability

• Mathematical Formalism and Proof Techniques
• Boolean Logic Circuits as basic computational model
• 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
• The (Extended) Church-Turing thesis
• From Calculability to Complexity
• Quantum Mechanics and Calculability

• Lecture Notes v.2.4 (12Apr26)

• Introductory Slides