Re:GetACoder.com: Solve P Vs NP
by eru on Monday August 16, 2010 @08:37AM
(#1607574)
Post's Correspondence Problem is nice. As an exercise you may try to figure out how to simulate a Turing machine in the Correspondence System. If you've done so, you basically have a prove of the undecidablility of this problem.
I worked on this, when I was bored in theoretical computer science classes.
I worked on this, when I was bored in theoretical computer science classes.