Why Your Humble iPod May Be Holding the Biggest Mystery in All of Science
In
1965, Intel co-founder Gordon Moore predicted that the number of
transistors placed on an integrated circuit would double approximately
every two years. That prediction, notes Bernard Chazelle, Computer
Science Professor at Princeton, if anything underestimated the results
during the past half century and should continue for at least another
decade. Moore’s Law, he posits, is responsible for most of the desktop
and hip-pocket wonders of the computer age, notably remarkable
improvements in processing speed, memory capacity, and network
bandwidth.
Moore’s Law correctly predicted revolutionary technological and social change in the late 20th century. But by 2020 if not before, as transistor features approach just atoms in width, Moore’s Law will have run its course. New technologies may replace integrated circuit technologies to extend Moore’s Law for decades; Chazelle argues that the years ahead will usher in the era of the “Algorithm,” a notion which, he contends, will prove to be the most disruptive and revolutionary scientific paradigm since quantum mechanics.
At the December 12 Lunch ‘n Learn, Chazelle began by confronting the four big ideas in computing: universality, duality, self-reference, and tractability. Universality owes its origin to Alan Turing, who explained first that it would be possible to create a computer that could load separate simple or complex programs and data. The result today is that we have iPods, Blackberries, desktop boxes and supercomputers that are essentially all the same in their architectural approach. Some are heavier, or more expensive, or more colorful or faster, but they are, thanks to Turing, the same. Turing took the idea of duality, the separating of the program from its data, from linguistics. Self-reference involves situations when the program and the data are equivalent, permitting replication of the program as in the replication of DNA from equivalent base pairs.
The modern era, suggests Chazelle, added to the concept of tractability, whether tasks are difficult because they are hard, or because we simply don’t understand them. Intractable problems include map coloring, airline scheduling, protein folding, and calculating optimal tours for continuously traveling salesmen. Even with continuing advances in Moore’s Law, there appears to be insufficient processing available to solve such problems. Says Chazelle, the remarkable discovery is that all tractable problems are equivalent, variants of the same, in that if you can solve any one of them, though they look very different, you also solve all the others.
The most ingenious and powerful algorithms probably include Fast Fourier Transform (FFT) (useful in digital signal processing and solving partial differential equations), RSA (a key algorithm for cryptography, encryption, and e-commerce), and even Google’s PageRank (used to determine the relevance of web pages to specific search requests). Chazelle gave examples of algorithms that are vastly more amazing. Zero-Knowledge is an interactive dialogue in which one party can prove mathematically that a statement is true without revealing any knowledge. Zero-Knowledge is used in authentication systems in which one party wants to prove its identity to a second party without revealing anything about how it actually proves its identity.
An even more mind-boggling algorithm is PCP (Probabilistically checkable proof) that would permit us to determine the veracity of a proof simply by entering it into a specific format and then by checking a random number of its elements. If bugs exist, the formatting method will spread the error throughout the proof making it easier to detect.
In the future, algorithms will assist us with the deluge of many different kinds of data. Natural algorithms, essentially algorithms that come to us from nature, is an area of research that is most humbling, says Chazelle, because that is where we are most behind and because nature seems to adopt these algorithms so effortlessly. Nature folds proteins quickly and accurately, despite the fact that the algorithms governing such behavior appears to be intractable. Similarly, crowds move effortlessly through complex social situations, fish defend themselves from predators by shaping their bodies collectively to reflect light, and birds flock, swarm, and hunt in intricate and complex patterns. Chazelle notes that we want to build tools to understand these mechanisms, but classical mathematics won’t do and computer science, he insists, is not yet up to the challenge.