Computers are not omnipotent

Summary form only given as follows. In a cover article in April, 1984, TIME magazine quoted the editor of a software magazine as saying: “Put the right kind of software into a computer and it will do whatever you want it to. There may be limits on what you can do with the machines themselves, but there are no limits on what you can do with the software.” The paper is of expository nature, and disproves this contention outright. We survey a wide array of results obtained by logicians and computer scientists over the last 65 years that establish inherent limitations of any kind of computing device, even with unlimited resources. This work thus has interesting philosophical implications concerning our own limitations as entities with finite mass and a finite life-span. Technically, we discuss problems that are noncomputable as well as problems that are computable in principle but are provably intractable in terms of their use of resources. We discuss the famous class of NP-complete problems, jigsaw puzzles, the travelling salesman problem, and timetables and scheduling. We also show how some kinds of “bad news” can be exploited in remarkable ways in cryptography, e.g., in the so-called zero-knowledge protocols. We also relate the “hard” results to the “softer” ideas of heuristics and artificial intelligence