The Limits of Computing

Computers can solve complex problems but they are far from omnipotent. Prof. Ran Raz of the Weizmann Institute's Computer Science and Applied Mathematics Department is trying to portray the limits of a computer's abilities and to estimate the resources required to solve certain problems.

For example, one problem a computer will never be able to solve is this: Will a computer running a given program stop at the end of the process? Surprisingly enough, it has been shown that this problem, which scientists call the "halting problem," cannot be solved by any machine.

In addition, there are problems that in principle can be solved by computers, but arriving at the solution would take centuries. Raz is trying to analyze the resources (such as time or memory space) needed to perform certain computational tasks. In most cases, such analyses are extremely difficult. To make progress, scientists utilize simpler, more basic, and sometimes weaker models of computation.

"Boolean circuits" are an example of a basic model in which the computation is performed by applying the logical operations AND, OR, and NOT to Boolean variables (bits). A weaker model allows only the operations AND and OR. Investigating the computational limitations of such basic models is imperative if the limits of a real computer's ability are to be determined. Understanding the basic limitations of man's electronic best friend could also prove critical in devising future computerized systems.
 

Prof. Ran Raz holds the Elaine Blond Career Development Chair.Born - Jerusalem, Israel Ph.D. - Hebrew University of Jerusalem Postdoctoral research - Princeton University, New Jersey Weizmann Institute of Science - Since 1994