Slashdot Mirror
What Computers Really Can't Do
What can't computers do? Why don't we hear more about their limitations, along with the mushroom clouds of hype about their limitless capabilities? By now, the public might well expect computing to restore the environment, cure cancer, prolong life and reason through the world's most complex and intractable problems.
Not so fast.
The good news, writes author David Harel in his new book, "Computers LTD: What They Really Can't Do," from Oxford University Press, is that computers are indeed incredible, capable of amazing feats.
The bad news is that they also face major problems, serious limitations on what they can ever be expected to accomplish, and that few people, even with advance computer science degrees, really grasp that there are fundamental barries no amount of hardware, software, brainpower or money can ever overcome.
Harel explores the boundaries of computable and noncomputable problems, and find's a lot to be pessimistic about. "..our hopes for computer omnipotence are shattered. We now know that not all algorithmic problems are solvable by computers, even with unlimited access to resources like time and memory space." In fact, he adds, problems relating to computer programs, particularly running time and memory space -- he calls these difficulties computational complexity -- severely limit just how much computers will ever be able to do.
Harel, who's a mathematics and computer science dean at Israel's Weizmann Institute of Science, may have written one of the first books in recent memory that focuses on the limits of computers. For a community grown understandably arrogant by years of hubris and hype, this is probably a much needed dose of reality. Why focus on the negative?, the author asks. His answer:
l. To satisfy intellectual curiousity. Computer scientists need to know what can be computed and what can't.
2. To discourage futility. Computer experts who tackle problems that are simply insoluble need to stop wasting their time.
3. To encourage the development of new paradigms. Many of the most exciting areas of computer science research -- including parallelism, randomization and quantum and molecular computing would not be advancing at their current speeds if it weren't for increased understanding about what computers can't accomplish.
4. To make possible the otherwise impossible. (The author saves much of the answer to what might be possible a surprise in the book, so I can't give it away here).
Harel acknowledges that our society could barely function without them. But he warns against the widespread mythology that computers will be able to do almost anything we can think up.
Typically, Harel writes, when people have problems making computers do what they want them to do, their excuses that fall into three categories: more money would buy larger, more sophisticated computers; being younger would permit us to wait longer for time-consuming programs to be terminated; being smarter could lead us to solutions we don't currently seem able to find.
But the truth is that computers are simply not equal to solve many complex problems. Harel raises, then mostly sidesteps, the debate over whether computers can be endowed with human-like intelligence. "In its wake," he writes, "a host of questions arise concerning the limits of computation, such as whether computers can run companies, carry out medical diagnoses, compose music or fall in love."
For non-techs, this book is on a pretty high plane. Even with Harel's impeccable credentials and engaging writing style, plenty of concepts are rough for someone who's not a programmer or computer scientist to grasp, especially when he gets to tiling and algorithms.
But the question is significant. The limitless potential power of computing has all kinds of implications for technology, education, culture and politics. We do need to know more about what's realistic. This splash of cold water is welcome, and more than a little shocking.
Purchase this at ThinkGeek.
Flip open any biology or medical publication and see how many details of biology are still being discovered, thus couldn't be simulated even if you had a computer powerful enough for the job.
Apparently it's only shocking to Katz and to other true believers of the one faith of computers©. Anybody involved with computers that has any semblance of sanity realizes that computers are not capable of solving every problem/question humanity has ever formulated. And the chances are that they never will. Even people that are into far-future sci-fi style writing usually keep a realistic stance about such things. Dan Simmons, a great author of many styles, wrote of a future with AI (autonomous intelligences, not artificial) computer units that were so intellectually superior to humans that most humans could not even fathom the depths of their 'minds', yet even these great beings couldn't answer some of the most fundamental of questions. Who are we? Why are we here? Who else is out there? How do we do
The whole premise of pure (and completely unfounded) belief in the abilities of machines is just as laughable as any religiously clung to belief. If you believe without question, then you lose your ability to see reality. If Katz sees this as a splash of cold water, then perhaps he needs to regain some perspective.
BTW, has anyone else noticed that Katz has shifted gears over the past few weeks from the "computer people are the smartest, bestest, wonderfullest, most misunderstood" to "computers suck, and they are damaging our society beyond repair"? I wonder if he just had a major system crash a few weeks ago?
------------
Well, some would argue that people are also just automata who respond in a predictable manner, if you know everything about their life from conception till the moment of the action in question. The issue is that humans are so complex, and have such a complex web of influences and forces, that the human mind cannot reliably predict what another human may do. In some sense humans, it could be argued, are psuedo-random, we are predictable, just not to any intellect we have yet spwaned or encountered.
-={(Astynax)}=-
-={(Astynax)}=-
"Darkness beyond Twilight"
Computers are just simple turing machines. This means that everything they do is utterly predictable. The very essence of being conscious is an ability to behave in a random fashion, also known as free will.
:).
Devil's advocate time:
Prove this.
As far as I can see, a human mind is indistinguishable in practice from a very large deterministic system in a chaotic environment. Apparently nondeterministic actions are adequately explained by strong sensitivity to input and the chaotic, effectively unpredictable nature of this input.
So, rather than making a blanket statement that the human mind can't be emulated by a deterministic machine, you're going to have to prove that it isn't already one
I'm using "human mind" instead of "conscious mind" above because you're going to have one hell of a time defining "consciousness".
Harel, [...], may have written one of the first books in recent memory that focuses on the limits of computers.
...
Search on Amazon.com (or others) for books on "Complexity Theory" or "Theory of Computation". I get 277 hits.
We now know that not all algorithmic problems are solvable by computers,
Now? This has been known for 50 years (The halting problem, etc). The book might be very good, but please don't make it sound like this is news.
-- Slef
Computers are just simple turing machines. This means that everything they do is utterly predictable.
Unless you have a Real Random Number Generator (RRNG) card plugged in.
The very essence of being conscious is an ability to behave in a random fashion, also known as free will.
Oh no! my RRNG has consciousness. What's more, it has free will! Even more disturbing is that this means dice are sentient while being rolled. To not roll the dice is cruelty. I heard that there are dice in Las Vegas not being used now. I urge all of you to go to Vegas and shoot craps all day and all night. I urge that we form a society for the prevention of cruelty to dice.
Computers will never have free will and will never be conscious, not in their present Turing Machine form, anyway.
The really scary thing is that nobody can prove that the brain isn't just a sophisticated neural network. Maybe consciousness is an illusion. To believe otherwise is, at this point, a matter of faith.
It is for the best, anyway. I don't want to be superceded mentally and made redundant, like the industrial revolution made my muscles redundant.
So, you don't want to be promoted to mid-level management?
So I am very glad conscious computers are impossible. It would be dangerous for us if they were.
Can you prove either of these statements? The current state of computers is not proof; neither are any Hollywood movies where intelligent computers take over the world.
For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
There are large classes of interesting problems which are incomputable. And that's not just because some PhD said "I tried for four years to solve this problem, and I couldn't figure out how to do it, so it must be incomputable."
Incomputable is a technical term in computer science. Problems can be proved incomputable. These proofs are not trivial. They usually are based on a formal, mathematical model of a computer. If some problem P is proved incomputable, and if the proof is correct, then no real computer that has the same limitations as the "model" computer will ever be able to solve the problem either. It has nothing to do with speed or memory, either. These problems are simply not solvable with our current models of computatation.
Now, IIRC, the "Church-Turing-Tarski Thesis" states that all reasonable (realistic) models of computation will have the same limitations, so if that theorem is true, then no computer will ever solve these problems.
So, any research effort to try to solve the problem with current computers is totally futile. It would be like trying to find a solution to the equation "n * 0 = 100".
You are correct that sometimes, trying to solve a problem yields other results. The way to try to solve these problems is to try to find an alternative model of computation, and prove that it is not resticted to the same class of problems as existing computers.
For example, there is some interesting research being done on the limits of quantum computation. Perhaps quantum computers will be able to solve a larger class of problems. That might disprove the Church-Turing-Tarski thesis.
The reason people should read this book is that many, many programmers out there do not have a theoretical computer science background. People who are self taught, or took a two year course from a technical school may be highly skilled programmers - I don't want to diss them. But they probably don't understand the limits of computation, and that might get them into trouble someday.
And I haven't even mentioned intractability - the gigantic class of problems that we don't know how to solve quickly when the problem gets large. For example, many optimization problems seem easy on paper when you have a set of 2 or 3 objects. You code up a little demo program that can handle 10 to 20 objects. It seems a little slow, but you figure you can optimize it and find a better algorithm, and use a faster computer. Meanwhile Marketing is promising people that you will be able to solve the problem with 1000 objects.
Maybe you work on the problem for months and never solve it and get fired. Or maybe you discover that the problem is intractable - NP-complete, for example - and that there is no known algorithm to solve the problem, and probably isn't one, and even the fastest imaginable computer using the best known algorithm could only handle 50 objects.
This is why everyone should read a little about intractability and incomputability. Ok enough ranting, back to work.
Torrey Hoffman (Azog)
Torrey Hoffman (Azog)
"HTML needs a rant tag" - Alan Cox