Computer technology has advanced at a pace unprecedented by other technologies. Although such achievements have transformed the human experience, they have also fueled misconceptions about the limits of computation itself. From a popular perspective, the scope of problems that can be solved by computers may seem unlimited. In reality, computers are limited by several factors—some contingent and others more fundamental.
Contingent limitations apply to the current state of computer technology. Actual computers are artifacts of engineering; as such, they are subject to certain physical limitations and may lack sufficient resources (e.g., speed, memory) to solve certain problems. For example, to list all possible partitions of 100 countries into two even halves (the city partition problem) would require at least 2100 steps, which would take more than 30 trillion years on a computer at the speed of 1 billion steps per second. Note that this is a problem that is solvable by computers in principle but that we just cannot afford the waiting time given the speed of the current computers. Moreover, further improvement in computer power does not seem to help much. For example, even with the computer speed improved by 1,000 times, the city partition problem still would require more than 30 billion years of computer time.
Other contingent limitations apply to our current knowledge of computer algorithms. Computer algorithms have been a very active research area in computer science. Many powerful algorithmic techniques have been developed during the past four decades. For example, now it is a trivial task using computers to schedule a minimum cost trip from a given city to another given city (the shortest path problem). The problem on a map of 100 cities takes a computer only miniseconds. This algorithm has been used very popularly by travel agents. On the other hand, if we add the condition that the tour must pass through all cities on the map (the traveling salesman problem), a seemingly moderate condition, the problem becomes much more difficult. The problem is solvable in principle; we can simply enumerate all possible such tours and pick the one with the minimum cost. However, such an enumerating algorithm would take more than 2100 steps on a computer, and this, as already calculated for the city partition problem, would require an unaffordable waiting time.
On the other hand, in spite of much effort by computer scientists and mathematicians over the past four decades, no one has been able to develop an algorithm for the traveling salesman problem that is essentially better than the trivial enumerating algorithm. Therefore, currently no known computer program is able to solve the problem in a practical manner. Note that the traveling salesman problem is different from the city partition problem; the 2100 computer steps are necessary for solving the city partition problem, whereas much faster computer algorithms might exist for the traveling salesman problem but simply have not been discovered yet.
During the past 40 years of research in a variety of areas in computer science, a class of more than 1,000 problems, all similar to the traveling salesman problem, has been identified. It is known that if any of these problems can be solved efficiently, all problems in the class can be solved efficiently using a technique of problem reductions. On the other hand, many of these problems have been studied for decades, and no efficient algorithms have been found for any of them. Thus, it is natural to conjecture that no efficient algorithms exist for these problems and that all of the problems in the class are computationally intractable. These problems have been named NP-complete problems.
Many important computational problems in a large variety of areas are known to be NP-complete. Studying NP-completeness has been central in the research in theoretical computer science. But this is only half of the story. Beyond the physical limitations on what can be computed in practice, there are deeper and more fundamental limitations on what can even be computed in principle. These limitations apply to the nature of computation itself. In fact, classic results in computational unsolvability were studied by mathematicians and philosophers prior to the construction of the first computers.
After all, computers are built based on Boolean logic, and the execution of a computer program can be regarded as a process of mathematical logic reasoning. According to Gödel’s incompleteness theorem, no formal mathematical system can verify the validity of all mathematical statements. Translated into the language of computer science, this says that no computer program can test the correctness of all other programs. In fact, it has been proven using formal mathematics that there are a large number of very simple computer programs whose correctness cannot be verified by any computer program. For example, suppose that a computer programming teacher has taught his first class and assigned his students to write their first computer program that simply prints “Hello, World.” It would be quite natural for the teacher to expect to write a “testing program” that can test the correctness of the programs submitted by the students. However, fundamental research in computational unsolvability has shown that no such testing programs exist even for such a simple task. Note that the impossibility results here are outright and have nothing to do with the computational resource. These fundamental impossibility results have also found wide applications in science and engineering.
In summary, limitations of computation have been studied thoroughly from both practical and theoretical points of view. These studies may play important roles in the research in geographic information science (GIScience). In particular, research directions in GIScience, such as computable city, electropolis, Digital Earth, and virtual field trip, all are closely related to computer and information technology. A clear understanding of what is possible and what is impossible using computer technologies seems to be necessary for the research in these areas.
No comments:
Post a Comment