This is a presentation I did about Post's Correspondence Problem for the "Models of Computation" course in 2011.
The presentation starts by giving an introduction to the problem itself and then showing its Turing completeness using M.Sipser’s proof from“Introduction to Theory of Computation”. I spent a lot of time on understanding and visualizing it so I think it's worth it. Later in the presentation slides I present some methods for proving the insolvability of some PCP instances, using knowledge from L. Zhao's. “Tackling Post’s Correspondence Problem”.
Post's Correspondence Problem
In retrospect there might be some things I would have changed in it; however I believe it has a nice smooth flow from simple notions to formalizations.
1.Michael Sipser, "Introduction to the Theory of Computation" (2nd edition), Thomson Course Technology, (2005).
2.Ling Zhao, “Tackling Post’s Correspondence Problem”, (2003).
