Is there a complexity theory for analyzing our real-world
computing systems as there is for the algorithms we invent?
Internet? Consider a molecular computer, a DNA
computer, a nano-scale computer, or even a quantum
computer [ 1]. What problems can and cannot be
solved through them? If contemplating these emerging substrates is not mind-bending enough, consider
a human and a machine working together as a single
computer to solve problems that neither would be
able to solve alone [ 2]. Given that humans and
machines have complementary computing capability,
now ask: What is computable?
In the 1950s, the founders of artificial intelligence
challenged computing researcherswith the third
question. As our understanding of human speech,
vision, language, and motor skills has improved since
then, and as we have achieved scientific and technological advances in computer science, neuroscience,
cognitive science, and the behavioral sciences, the
landscape has changed dramatically. Computer scientists can now probe both deeply and broadly in our
quest to understand intelligence, from the neuron to
the brain, from a person to a population.
“Information” in the field of computing has seemingly disparate meanings depending on scientific context: information theory, information processing,
information retrieval, or information science. Distinguishing signal from noise is relevant in all these contexts, whether we mean transmitting bits over a wire,
searching for an answer through the Web, or extracting knowledge from an ocean of sensor data. In
essence, there is a chain of representations, from bits
to data to information to knowledge. Beyond computing, nature has its own way of encoding information that is not as simplistic as using 0s and 1s. The
genetic code is an obvious example. More sweepingly,
by interpreting a DNA strand, a cell, or an organism
as a reactive system (processing inputs from its environment and producing outputs that affect that environment), it is no longer metaphorical to say biology
is an information science. Ditto geosciences. Meanwhile, with quantum computing, it’s not bits but
qubits.
Our engineering prowess creates computer, communication, and information systems that enhance
everyone’s daily lives and enable us to do astonishing
things: instantaneous access to and sharing of information through palm-size devices with friends in
social networks of tens of millions of users; dance
with remote partners through 3D tele-immersion [ 4];
and lead alternative lives through avatars that can
even defy the laws of physics in virtual worlds. The
complexity of these systems delivers the richness of
functionality we enjoy today, with time and space
performance that spoil us. Their complexity, however,
also makes it difficult for even the original system
developersto analyze, model, or predict system
behavior, let alone anticipate the emergent behavior
of multiple interacting systems.
Can we build systems with simple and elegant
designs that are easy to understand, modify, and
evolve yet still provide the functionality we might
take for granted today and dream of for tomorrow? Is
there a complexity theory for analyzing our real-world computing systems as there is for the algorithms we invent? Such a theory would need to
consider measures of not just time and space but of
energy and cost, as well as dependability, security,
and usability, most of which elude quantification
today. More ambitiously (or crazily), is there a complexity theory that spans both the theory and practice of computing?
I pose these questions to stimulate deep thinking
and further discussion. What deep questions about
computing would you want answered? In 50 years,
how different will they and their answers be from
what we ask and are able to answer today? c
REFERENCES
1. Reiffel, E. and Polak, W. An introduction to quantum computing for
non-physicists. ACM Computing Surveys 32, 3 (Sept. 2000), 300–335.
2. von Ahn, L. Games with a purpose. IEEE Computer (June 2006), 96– 98.
3. Wing, J. Thinking about computing. Computing Research News 19, 5
(Nov. 2007).
4. Yang, Z., Yu, B., Wu, W., Diankov, R., and Bajscy, R. Collaborative
dancing in tele-immersive environment. In Proceedings of ACM Multimedia (Santa Barbara, CA, Oct. 23– 27). ACM Press, New York, 2006,
723–726.
JEANNETTE M. WING ( jwing@nsf.gov) is Assistant Director of the
Computer and Information Science and Engineering Directorate at the
National Science Foundation, Arlington, VA, and the President’s Professor of Computer Science in the Computer Science Department at
Carnegie Mellon University, Pittsburgh, PA.