On Christmas, Jim and I were discussing the difficulties of programming a computer to play Go in comparison to Chess. I said Go might ultimately be beyond the power of a computer because it relied on pattern recognition rather than number-crunching. Jim said he doubted that, because eventually computers would be able to handle complex pattern recognition. Well, it looks like I was wrong, about the nature of the task--it's number-crunching AND pattern recognition--and the outcome. At least one expert concurs that it's not a matter of whether but when. Here's a no-sign-in-required link to the NYTimes article I remembered from several years ago. In relevant part it states: "'It may be a hundred years before a computer beats humans at Go -- maybe even longer,' said Dr. Piet Hut, an astrophysicist at the Institute for Advanced Study in Princeton, N.J., and a fan of the game. 'If a reasonably intelligent person learned to play Go, in a few months he could beat all existing computer programs. You don't have to be a Kasparov.' When or if a computer defeats a human Go champion, it will be a sign that artificial intelligence is truly beginning to become as good as the real thing."
It's my assumption that pattern recognition is number crunching. The permutations in a game of Go are so high that some people assume that you can't reduce it to number crunching - but that's only given our present serial computers. A quantum computer - assuming they can build them, and it looks like they will be able to - will completely change everything. This problem (ditto for cryptography) will go from being physically impossible to being not so hard. When I say physically impossible I mean that it could be done in a certain amount of time, but given the most powerful traditional computer (one made out of all the matter in the universe) that could work on the problem for the maximum amount of time (the entire life of the universe) it still wouldn't be enough to solve the problem. So it's solvable in theory (in that we can say what it would take to solve it in a brute force manner) but it's impossible, because what it would take is beyond what is physically possible in this universe.
But that's only given traditional (serial) computer design.
A quantum computer takes advantage of parallel universes. Depending on how big your quantum computer is, it splits a problem into that many discreet units, and then replicates itself into that many different parallel universes. In each parallel universe each replicated copy of the quantum computer works on its part of the problem at the same time. At the end they all pop back into one quantum computer in this universe which now holds the answer to the problem.
No, seriously. IBM and others have already build small ones. I think IBMs sucessfully factored 15 into 5 and 3. That may not seem like much, and strictly speaking it's not, but it's a good proof of concept. I say Go, and more importantly cryptography as we know it, have less than 50 years.
|
- tom moody 1-01-2002 8:13 pm
It's my assumption that pattern recognition is number crunching. The permutations in a game of Go are so high that some people assume that you can't reduce it to number crunching - but that's only given our present serial computers. A quantum computer - assuming they can build them, and it looks like they will be able to - will completely change everything. This problem (ditto for cryptography) will go from being physically impossible to being not so hard. When I say physically impossible I mean that it could be done in a certain amount of time, but given the most powerful traditional computer (one made out of all the matter in the universe) that could work on the problem for the maximum amount of time (the entire life of the universe) it still wouldn't be enough to solve the problem. So it's solvable in theory (in that we can say what it would take to solve it in a brute force manner) but it's impossible, because what it would take is beyond what is physically possible in this universe.
But that's only given traditional (serial) computer design.
A quantum computer takes advantage of parallel universes. Depending on how big your quantum computer is, it splits a problem into that many discreet units, and then replicates itself into that many different parallel universes. In each parallel universe each replicated copy of the quantum computer works on its part of the problem at the same time. At the end they all pop back into one quantum computer in this universe which now holds the answer to the problem.
No, seriously. IBM and others have already build small ones. I think IBMs sucessfully factored 15 into 5 and 3. That may not seem like much, and strictly speaking it's not, but it's a good proof of concept. I say Go, and more importantly cryptography as we know it, have less than 50 years.
- jim 1-07-2002 9:27 pm [add a comment]