Computability Lecture Notes

Lecture Download
Introduction and Overview
Generalized Computers, Strings, Languages. Finite Automata (FA's)
Regular Languages and Regular Operations; emacs regular expressions
Closure of Regular Languages Under Boolean Operations.
Nondeterminstics FA's (NFA's). Regular Expressions (REG); FA = NFA = REG
Minimization. Pumping Lemma
Context Free Languages: Derivations, Parse-Trees, Ambiguity
Pushdown Stack Automata (PDA's)
Grammar and Machine Transformations
Context Free Pumping Lemma
Turing Machines: Motivation, Definitions, Recognizers vs. Deciders
Turing Machine Variants: 3 levels of TM abstraction, Non-deterministic recognizers and deciders, K├Ânig's infinity lemma, Multitape TM's
Universal Models of Computation: TM = k-track TM = k-tape TM = NTM, FIFO Queue Machines
Viewing algorithms as languages, Algorithmic Decision Problems: ATM, ACFG , A REX,ETM, etc.
Incomputable Languages: Existence of Incomputable Languages; Cantor's Diagonalization Argument; Undecidability of ATM, E TM, EQTM; ALLTM
More Undecidable Problems: Reducibility: Turing reducible, Mapping reducible, Co-mapping reducible; Beyond undecidable; General grammars; Semi-Thue systems (STP); Post's correspondence problem (PCP); Problems involving CFG's
Complexity: Running time, Big-O review, the class PP and CYK algorithm
The Class NP: Nondeterministic complexity: poly-time NTM's, poly-time Verifiers, poly-size proofs; Punch-Card Puzzle, SAT and variants, The class Co-NP; Polynomial time reductions
NP-complete problems; P vs. NP Open Problem: Known and unknown hierarchies; Nondeterministic complexity
The Cook-Levin Theorem: Showing that CSAT is NP-hard, Reducing CSAT to 3SAT

No comments: