Line 18: Line 18:
  
 
[http://www.cs.cornell.edu/Courses/cs4820/2013sp/Handouts/481TM.pdf Turing Machine Handout]
 
[http://www.cs.cornell.edu/Courses/cs4820/2013sp/Handouts/481TM.pdf Turing Machine Handout]
 +
 +
[http://www.cs.toronto.edu/~sacook/csc463h/notes/comp.pdf Reduction examples for decidablility]
  
 
[http://theory.stanford.edu/~trevisan/cs154-12/rice.pdf Rice's theorem, Undecidable and unrecognizable problems on TM]
 
[http://theory.stanford.edu/~trevisan/cs154-12/rice.pdf Rice's theorem, Undecidable and unrecognizable problems on TM]

Revision as of 09:48, 20 August 2014

Video Lectures by Shai Simonson

NP Complete

Recursively Enumerable Sets

Recursively Enumerable Sets

Notes from CMU

Definitions

Push Down Automata

Linear Bounded Automata

Turing Machine Problems

Turing Machine Handout

Reduction examples for decidablility

Rice's theorem, Undecidable and unrecognizable problems on TM

Undecidable problems about L(CFG)

Trivial and Non-trivial properties of L(M)

Undecidable Problems

Closure property of CFL

NP Complete

A good lecture going deep into Abstract Machines

P, NP, NPC and NP-Hard in SImple terms

Identify the class of the language