Well, Aaron, can you be more specific? It is something of a dodge, to say, "read these books." I can think of computationally intractable problems. You mention Gödel. A Gödelized encryption goes like this:
seed prime postion exp'n
N 01 14 1^14 = 1
U 02 21 2^21 = 2097152
C 03 03 3^3 = 27
L 05 12 5^12 = 1953125
E 07 05 7^5 = 16807
A 11 01 11^ 1 = 11
R 13 18 13 ^ 18 = (etc)
Then you multiply together as one product all of the exponentiations. Because the factors are powers of primes, the resulting number is theoretically factorable. You can broadcast a long text message as a single (large) number. Getting the plaintext out of the cipher is computationally intractable. (from The Code Book: all about unbreakable codes and how to use them (3rd ed.), Marotta. Loompanics. 1987)
Another example is the n-body problem. Croatia honors native son Ruger Boscovic on their money.

( http://www2.physics.umd.edu/~redish/Money/)
An 18th century polymath, he solved one of the restricted three-body problems. (You can read books on this.) As far as I know, these restricted three body problems have no synthetic solutions -- and no solutions at all exist for systems more complicated. When sending a satellite into farther space, scientists track it and make course corrections, closer in their methods to (empirical) Chaldean astrologers than to (rational) Enlightment mathematicians. So, there, again, the solutions might be indicated, but they are computationally intractable.
On the other hand, the Federal government still uses its DES/DEA (Data Encryption Standard/Data Encryption Algorithm), for federal reserve bank money transfers because it has never been cracked because it is computationally intractable -- but remains unused in military application because it might not be. Similarly, the RSA algorithm preferred by private enterprise has been seeded with longer and longer primes to keep ahead of factoring theory and factoring machinery. The longest known prime number -- several in recent years, as always -- was discovered by a homebrew internet-driven network of desktop personal computers. (Published December 04, 2003 MSU student's prime number largest one yet http://www.lsj.com/news/local/031204_numbers_1a-10a.html)
There was a time when just getting a system of wheels to point to the second derivative was a challenge worthy of a worldclass mathematician and the equally brilliant daughter of a brilliant poet: Babbage and Ada. Would that they were alive now to see what we can do!
So, what is computationally intractable changes over time -- and is not metaphysically determined. (But I could be wrong.)
|