Complexity_ A Guided Tour - Melanie Mitchell [79]
When we say a system is processing information or computing (terms which, for now, I will use synonymously), we need to answer the following:
What plays the role of “information” in this system?
How is it communicated and processed?
How does this information acquire meaning? And to whom? (Some will disagree with me that computation requires meaning of some sort, but I will go out on a limb and claim it does.)
INFORMATION PROCESSING IN TRADITIONAL COMPUTERS
As we saw in chapter 4, the notion of computation was formalized in the 1930s by Alan Turing as the steps carried out by a Turing machine on a particular input. Ever since then, Turing’s formulation has been the basis for designing traditional von-Neumann-style programmable computers. For these computers, questions about information have straightforward answers. We can say that the role of information is played by the tape symbols and possible states of the tape head. Information is communicated and processed by the tape head’s actions of reading from and writing to the tape, and changing state. This is all done by following the rules, which constitute the program.
We can view all programs written for traditional computers at (at least) two levels of description: a machine-code level and a programming level. The machine-code level is the set of specific, step-by-step low-level instructions for the machine (e.g., “move the contents of memory location n to CPU register j,” “perform an or logic operation on the contents of CPU registers j and i and store the result in memory location m,” and so on. The programming level is the set of instructions in a high-level language, such as BASIC or Java, that is more understandable to humans (e.g., “multiply the value of the variable half_of_total by 2 and store the result in the variable total,” etc.). Typically a single high-level instruction corresponds to several low-level instructions, which may be different on different computers. Thus a given high-level program can be implemented in different ways in machine code; it is a more abstract description of information processing.
The meaning of the input and output information in a Turing machine comes from its interpretation by humans (programmers and users). The meaning of the information created in intermediate steps in the computation also comes from its interpretation (or design) by humans, who understand the steps in terms of commands in a high-level programming language. This higher level of description allows us to understand computations in a human-friendly way that is abstracted from particular details of machine code and hardware.
INFORMATION PROCESSING IN CELLULAR AUTOMATA
For non-von-Neumann-style computers such as cellular automata, the answers are not as straightforward. Consider, for example, the cellular automaton described in the previous chapter that was evolved by a genetic algorithm to perform majority classification. Drawing an analogy with traditional computers, we could say that information in this cellular automaton is located in the configurations of states in the lattice at each time step. The input is the initial configuration, the output is the final configuration, and at each intermediate time step information is communicated and processed within each neighborhood of cells via the actions of the cellular automaton rule. Meaning comes from the human knowledge of the task being performed and interpretation of the mapping from the input to the output (e.g., “the final lattice is all white; that means that the initial configuration had a majority of white cells”).
Describing information processing at this level, analogous to “machine