Logo IMG
HOME > PAST ISSUE > Article Detail


The Great Principles of Computing

Computing may be the fourth great domain of science along with the physical, life and social sciences

Peter J. Denning

What Are Information Processes?

There is a potential difficulty with defining computation in terms of information. Information seems to have no settled definition. Claude Shannon, the father of information theory, in 1948 defined information as the expected number of yes-or-no questions one must ask to decide what message was sent by a source. He purposely skirted the issue of the meaning of bit patterns, which seems to be important to defining information. In sifting through many published definitions, Paolo Rocchi in 2010 concluded that definitions of information necessarily involve an objective component—signs and their referents, or in other words, symbols and what they stand for—and a subjective component—meanings. How can we base a scientific definition of information on something with such an essential subjective component?

Biologists have a similar problem with “life.” Life scientist Robert Hazen notes that biologists have no precise definition of life, but they do have a list of seven criteria for when an entity is living. The observable affects of life, such as chemistry, energy and reproduction, are sufficient to ground the science of biology. In the same way, we can ground a science of information on the observable affects (signs and referents) without having a precise definition of meaning.

A representation is a pattern of symbols that stands for something. The association between a representation and what it stands for can be recorded as a link in a table or database, or as a memory in people’s brains. There are two important aspects of representations: syntax and stuff. Syntax is the rules for constructing patterns; it allows us to distinguish patterns that stand for something from patterns that do not. Stuff is the measurable physical states of the world that hold representations, usually in media or signals. Put these two together and we can build machines that can detect when a valid pattern is present.

A representation that stands for a method of evaluating a function is called an algorithm. A representation that stands for values is called data. When implemented by a machine, an algorithm controls the transformation of an input data representation to an output data representation. The algorithm representation controls the transformation of data representations. The distinction between the algorithm and the data representations is pretty weak; the executable code generated by a compiler looks like data to the compiler and like an algorithm to the person running the code.

Even this simple notion of representation has deep consequences. For example, as Gregory Chaitin has shown, there is no algorithm for finding the shortest possible representation of something.

Some scientists leave open the question of whether an observed information process is actually controlled by an algorithm. DNA translation can thus be called an information process; if someone discovers a controlling algorithm, it could be also called a computation.

Some mathematicians define computation as separate from implementation. They treat computations as logical orderings of strings in abstract languages, and are able to determine the logical limits of computation. However, to answer questions about the running time of observable computations, they have to introduce costs—the time or energy of storing, retrieving or converting representations. Many real-world problems require exponential-time computations as a consequence of these implementable representations. My colleagues and I still prefer to deal with implementable representations because they are the basis of a scientific approach to computation.

These notions of representations are sufficient to give us the definitions we need for computing. An information process is a sequence of representations. (In the physical world, it is a continuously evolving, changing representation.) A computation is an information process in which the transitions from one element of the sequence to the next are controlled by a representation. (In the physical world, we would say that each infinitesimal time and space step is controlled by a representation.)

comments powered by Disqus


Subscribe to American Scientist