That's a useful article. The easy parts include<p>- The halting problem is decidable for systems with finite memory. That's simple enough; a deterministic program with finite memory must either halt or repeat a previous state. Now the question is, is there a faster way to determine the outcome than running the program? That's a complexity problem. One of those where the average case is much easier than the worse case. Many NP-hard problems are like that.<p>- The same scaling issue applies to the "Chinese room", which is an extremely inefficient solution to the problem. The question is how much can you improve on exhaustive enumeration.<p>Then it gets hard. I thought it was established that quantum computing is not going to allow brute-force search (using multiple universes?) on problems like factoring. Is that wrong?
The <i>method</i> of proof of P!=NP will undoubtedly tell us something deeply fundamental about computation and therefore logic and therefore philosophy. That complexity theory is so difficult thus far is in itself philosophically interesting.