Week 11: Unsolvable Problems: A No-recursive Language and an Unsolvable Problem, The Halting Problem, Unsolvable Problems Involving TMs, Rice’s Theorem, Post’s Correspondence Problem
Course Material
- Week 1: Mathematical Tools and Techniques: Logic and Proofs, Sets, Functions and Equivalence Relations, Languages.
- Week 2: Proofs, Principle of Mathematical Induction, Recursive Definitions, Structural Induction.
- Week 3: Regular Languages and Regular Expression
- Week 4: Nondeterministic Finite Automata with A-Transitions, Kleene’s Theorem.
- Week 5: Regular, Non-regular Languages, Criteria for Regularity, Minimal Finite Automata
- Week 6: Context-Free Grammars, Regular Grammars, Derivation Tree and Ambiguity
- Week 7: Pushdown Automata: Definitions and Examples, Deterministic Pushdown Automata
- Week 8: Context-Free, Non-Context-Free Languages.
- Week 9: Turing Machines: Definitions and Examples, Non-deterministic TM, Universal TM
- Week 10: Recursively Enumerable and Languages: Recursively Enumerable and Recursive, Enumerating a Language, More General Grammars, Context-Sensitive Languages and the Chomsky Hierarchy
- Week 11: Unsolvable Problems: A No-recursive Language and an Unsolvable Problem, The Halting Problem, Unsolvable Problems Involving TMs, Rice’s Theorem, Post’s Correspondence Problem
- Week 12: Computable Functions: Primitive Recursive Functions, PRF and Bounded Operations, Unbounded. Minimalization and ų-Recursive Functions, Godel Numbering
- Chapters 12
- Department CS & IT
- Teacher
Samreen Razzaq
