1What Is Information Processing?

1.1 Formal Games

Cognitive psychologists believe that human thinking is information processing. What does “information processing” mean? To provide an answer, let’s explore the parallels between information processing and chess. We play chess on a board divided into an 8x8 pattern of alternating light and dark squares. Figure 1-1 illustrates a chess board labelled with a coordinate system.

Playing chess involves moving chess pieces, or tokens, on the chess board. One player, White, uses light-coloured tokens. The other player, Black, uses dark-coloured tokens. Chess uses six different token types. Each type has a different name and a distinctive shape. Figure 1-2 shows the token types available to both players.

Different rules govern different token types in chess; rules define a token’s possible moves. To know how to move a particular token, a player must identify the token as belonging to a particular type (Queen, Rook, etc.). Chess is a formal game because a player identifies a token’s type by examining the token’s shape or form. For example, Figure 1-3 shows the eight squares to which White’s King on square d5 could move. Importantly, the eight possible moves presume that a King, and not some other type, is on d5.

If the token on d5 belongs to a different type, then different rules apply. Figure 1-4 shows the squares to which a Knight could move from d5.

After the chess pieces are placed on their starting squares (Figure 1-5), a game begins when White moves one token to a different square. Black replies by moving one of her pieces.

Figure 1-6 presents the chess board’s state after both players make three moves in a game. White has moved a Pawn, a Knight, and a Bishop. Black has moved a Knight and two Pawns. The only differences between Figure 1-6 and Figure 1-5 are chess token positions.

In chess, a player can remove a token from the board. If a player moves a token to a square already occupied by the opponent’s token, then the opponent’s token is captured. A captured piece disappears from the board. Capturing a piece is illustrated in Figure 1-7. With her fourth move, White moves the Bishop from b5 to c6 to capture Black’s Knight already on c6; that Knight vanishes from Figure 1-7.

Black responds by using her Pawn at d7 in Figure 1-7 to capture the Bishop at c6, producing the chess board shown in Figure 1-8. Note that the chess board in Figure 1-8 has two fewer pieces than the one in Figure 1-5.

How does chess relate to information processing? Information processing involves manipulating symbols stored in memory. A chess board is an example of memory. The chess board illustrated in Figure 1-1 is an empty memory, holding no tokens.

An information processing system also uses a finite set of tokens, or a finite alphabet of symbols, for storing in memory. In chess, the tokens for storage—for placing on the board—are illustrated in Figure 1-2.

An information processor uses operations to manipulate symbols in memory. One operation adds a new symbol to memory. In our chess example, this operation is illustrated in Figure 1-5; to create the chess game’s starting positions, 32 different chess tokens appear in Figure 1-1’s empty memory. The “add a token” operation executes 32 different times.

A second operation rearranges symbols by moving a token from one memory location to another. Figure 1-6 demonstrates how chess piece positions change after each player makes three different moves. Each move causes a token to change its location from one square to another; each move rearranges symbols on the chess board memory. Restrictions apply to token rearrangement in memory. Different rules apply to different token types (Figures 1-3 and 1-4). An information processing system must distinguish one token type from another to determine which rules can be applied.

A third operation deletes a symbol from memory. Figures 1-7 and 1-8 illustrate a token’s removal from the board after being captured.

A fourth operation changes a token from one type to another. We could use this operation to describe capturing a piece. For example, when Black’s Pawn captures White’s Bishop at c6 in Figure 1-7 to produce Figure 1-8, two different operations occur. First, we delete Black’s Pawn at d7. Second, we change White’s Bishop at c6 into a different token, Black’s Pawn.

The chess example illustrates two properties of any information processor: a data structure, which is a memory for storing different types of symbols, and a set of rules or operations used to manipulate the symbols in the data structure. Another basic property is control. Control determines “what to do next.” At any given moment, an information processor must choose which rule to apply and which symbol to manipulate. Control permits an information processor to apply its rules in a particular order to accomplish a task.

Chess also involves control. In chess, we try to defeat an opponent by capturing her King. Chess players range in ability from mere amateurs to grandmasters and world champions. What makes a grandmaster better than an amateur? The grandmaster has superior control—she makes better decisions about what move to make next.

How does a grandmaster make better decisions about the moves to make in a chess game? She has more knowledge about playing chess and uses it to make better decisions about which move to make next by predicting her opponent’s next moves, by identifying weaknesses in her opponent’s position, and so on.

However, we are not immediately concerned with such details. For now, we need only understand that an information processor has three basic components: a data structure, rules for manipulating the symbols stored in the data structure, and a control procedure for deciding which rule to apply to the data structure. Chess illustrates the three components. Information processing is rule-governed symbol manipulation; it is like playing a formal game.

1.2 Form and Function

The Figure 1-2 chess pieces represent the Staunton design. In a Staunton chess set, Rooks look like castle towers, Knights look like horses, and Bishops, Queens, and Kings all have distinctive hats or crowns. However, many alternatives to the Staunton design exist. Some designs use cartoon or Sesame Street characters or American Civil War figures. Chess pieces can also be made from wood, plastic, stone, or other materials.

The many chess piece designs illustrate a many-to-one relationship. In a many-to-one relationship, many (seemingly) different things all belong to the same type. For instance, one type of chess token—the King—could resemble a Staunton piece with a crown, Abraham Lincoln, or Homer Simpson. We could also construct the King from many different materials. Yet the King’s different shapes, built from different materials, belong to one type: the King.

How, then, do we define the chess King? We cannot define the King as a specific form in a particular chess set or the material from which it is built. To do so would rule out possible Kings. For example, defining a King as a wooden Staunton piece ignores the possibility that the King could take another shape or be built from another material. In short, we cannot define a King using physical properties; such definitions restrict us too much. Instead, we must define a King by its function in a chess game. A functional definition focuses on what something does, not on its physical properties. In chess, a King is the token to which the King’s rules apply (Figure 1-3). Functional definitions permit assigning chess pieces of different shapes or materials to the same type, having the same function in a game.

We almost always explain information processors functionally, not physically. Cognitive psychologists liken human thinking to a computer running a program. What makes such an analogy possible given physical differences between brains and computers? The analogy works by being functional, not physical. Like different designs for chess pieces, brains and computers can perform identical functions even while being built from different materials.

1.3 The Formalist’s Motto

Processing information is playing a formal game. A chess game’s characteristics illustrate information processing’s core properties. However, playing chess and processing information differ on one key property. Useful information processors manipulate representations—symbols with meanings, symbols referring to things in the world. Information processing conveys new meanings by creating new symbol combinations. Formal games do not.

Chess tokens do not represent meanings. A chess move has no content because chess pieces do not represent anything; formal chess moves depend only on token shapes. Chess piece positions do not communicate meanings.

To distinguish an information processor’s formal properties from its meanings, we borrow two words from linguistics. Linguists use the word syntax to describe a sentence’s grammatical structure. Syntax is a set of rules for distinguishing grammatical sentences from ungrammatical sentences. The rules governing token movements in a formal game are analogous to a syntax.

In contrast, linguists use the word semantics to describe a sentence’s meaning. Claiming that a symbol has meaning is claiming that a symbol stands for something else; a symbol refers to something in the world. For instance, the string of letters dog is meaningful because it represents or stands for a particular animal in the world. When a symbol represents meaning by referring to something in the world, we call the symbol intentional.

Philosopher Franz Brentano (1874/1995) used intentionality to distinguish the physical from the mental. For Brentano, mental states could be intentional, but physical states could not, separating syntax from semantics. Consider linguist Noam Chomsky’s famous example “Colorless green ideas sleep furiously,” a meaningless sentence with proper syntax. Meaningless sentences can still be grammatical.

Separating syntax from semantics makes mechanical information processing possible. Information processors manipulate symbols using formal operations; information processors do not understand what symbols mean. However, formal operations can be meaningful.

Although chess tokens do not have meanings, symbols used in other formal systems do. For example, mathematics uses formal rules to manipulate symbols. But mathematical symbols represent meanings. Engineers manipulate symbols to determine whether a bridge will stand, or whether an airplane will fly, using symbols to represent real-world properties such as force, gravity, or mass. Logic also manipulates meaningful symbols. In logic, a symbol represents a real-world property’s truth or falsehood.

Mathematical or logical operations, though meaningful, do not themselves understand what symbols mean, for they are as formal as the rules governing chess. For example, one rule in mathematics permits replacing the string x + x + x with the string 3x but does not know x’s value or what x represents. The rule only requires recognizing symbol shapes (e.g., x, +) to permit symbols to be manipulated in a particular way.

Amazingly, mathematical operations preserve meanings. For instance, the preceding example of replacing one set of symbols with another (x + x + x = 3x) operates without knowing what x means. However, in the real world, whatever x is, when added to itself three times, the result will be three times its value. The formal operation preserves meanings, even though it does not understand them.

Philosopher John Haugeland (1985) notes that a symbol in an information processing system possesses dual properties. One property is the symbol’s shape or form, which permits the symbol to be manipulated by formal operations. The other property is the symbol’s meaning. Haugeland points out that information processing systems are powerful because their formal operations on symbols—operations not sensitive to meaning—still preserve meaning and therefore can produce new meanings. Haugeland summarizes this notion in the formalist’s motto: take care of the syntax, and the semantics will take care of itself.

The formalist’s motto makes modern information processors, such as computers, possible. Basic information processing operations provide a formal syntax for manipulating symbols. The syntax works independently of what the symbols represent. However, the syntax preserves the meanings of symbols, making modern computers useful information processing devices.

1.4 Demonstrating the Formalist’s Motto

The formalist’s motto claims that information processors formally manipulate symbols, but still preserve meanings, even without understanding what symbols represent. We will now consider one example to illustrate the formalist’s motto.

In the 1930s, mathematician Alan Turing (1936) proposed an idea now known as a Turing machine. A Turing machine is a very basic information processing device with two different components (Figure 1-9). The first is an infinitely long ticker tape memory. The tape is divided into a series of individual cells. Each cell can only contain a single symbol. The ticker tape cells in Figure 1-9 contain a 0, a 1, or a B (for blank).

A Turing machine’s second component is a machine head for manipulating the symbols on the ticker tape. The machine head includes methods for moving along the tape (one cell at a time), for reading the symbol in the current cell, and for writing a symbol into the current cell. The machine head also includes a register to indicate its current physical condition or machine state. Finally, the machine head contains operations, the machine table, for manipulating the ticker tape’s contents.

To use a Turing machine, we ask a question by writing some symbols on the ticker tape. The symbols on the Figure 1-9 tape provide an example question. Next, we place the machine head at a starting cell on the ticker tape, and we assign a starting machine state. The starting cell for the Figure 1-9 machine head is the lowest cell containing a 1, and the starting machine state is 1. Finally, we activate the machine, which starts to read and write symbols on the tape, moving along the tape one cell at a time. Eventually, the machine halts. When halted, the symbols written by the machine on the tape give the machine’s answer to the original question.

How does the machine head manipulate the symbols on the ticker tape? The machine head contains formal operations. The machine reads the symbol from the current cell on the tape, noting the current machine state. Combined, the symbol and the machine state tell the machine which operation to perform. At each processing step, the Figure 1-9 machine writes a symbol (0, 1, or B) to the tape or moves one cell up or down.

Table 1-1 contains one special instruction. If the machine head reads a 0 while in State 6, then the Turing machine executes an operation called HALT. When HALT occurs, the tape holds the Turing machine’s answer to the original question. Figure 1-10 shows the Turing machine’s answer to the question shown on the tape in Figure 1-9.

A Turing machine’s information processing behaviour does not require understanding what the ticker tape’s symbols represent. The interested reader can confirm this by starting with the Turing machine as laid out in Figure 1-9 and then following the machine table’s steps. The reader—like the Turing machine itself—can produce the Figure 1-10 ticker tape without knowing what the tape’s symbols mean. What question does the tape hold in Figure 1-9? What answer does the tape hold in Figure 1-10? If the reader can pretend to be the machine, but cannot answer such questions, then she has acted as a formal system.

Importantly, the ticker tape contents in Figures 1-9 and 1-10 are meaningful. In both figures, the tapes represent integer values by placing a certain number of 1s between two 0s. The integer 2 is coded “0110,” the integer 3 is coded “01110,” and so on. A tape can hold more than one integer, separating different integers with a blank cell.

Knowing the tape’s encoding, we see that the ticker tape in Figure 1-9 represents two different integers (2 and 3) and that the ticker tape in Figure 1-10 represents a single integer (5). The Table 1-1 machine table provides instructions for adding two integers together. Thus, the question in Figure 1-9 is “What is the sum of 2 and 3?,” and the machine’s answer in Figure 1-10 is “The sum is 5.”

Our example Turing machine operates without understanding ticker tape meanings. But the Table 1-1 operations preserve meaning and will correctly add any two integers written on the tape. The Turing machine takes care of the syntax only, while the ticker tape’s semantics takes care of itself.

1.5 A Universal Machine

The Turing machine in Section 1.4 performs only one task: summing up two integers. It does not solve any other information processing problems. A specialist, the Turing machine accomplishes only one thing.

Many other specialist Turing machines can exist. For example, one machine might (only) subtract one integer from another. Another machine might (only) multiply two integers together. To create a different Turing machine, we must create a different machine table to take the place of Table 1-1. Every specialist Turing machine has its own distinct machine table.

Note: B represents a blank cell.

However, we can create a general information processor. Consider a reader pretending to be the Turing machine in Section 1.4. If that section provided a different machine table, then the reader could pretend to be the different machine as well, by following any instructions like those in Table 1-1. Therefore, she could pretend to be any Turing machine. She would be a generalist, not a specialist.

In the 1930s, Turing designed a Turing machine pretending to be any other Turing machine, called the universal Turing machine, which operates like the reader who uses Table 1-1 to simulate the Figure 1-9 machine. A universal machine’s ticker tape holds different information (Figure 1-11). One part of the tape holds data—where one writes the to-be-answered question. Another part describes the Turing machine that the universal machine pretends to be. A third part serves as a temporary memory or scratchpad.

When observing a universal Turing machine behave, we might recognize that it operates like a reader who simulates Table 1-1. The universal machine’s machine head moves back and forth between the data on the ticker tape and the machine description on the ticker tape. The universal machine reads a data symbol, goes to the machine description to find out what to do to the symbol, and then goes back to the data to perform the operation. The scratchpad remembers important information (e.g., the current machine state of the device that it is pretending to be). Eventually, the universal machine will HALT, with the answer to the question written on the ticker tape region for holding data.

However, the universal Turing machine does not understand the ticker tape’s meaning and does not know that the ticker tape holds different information at different places. A universal Turing machine is purely formal, and it works like any other Turing machine by reading a symbol, noting the current machine state, and picking an operation from the machine table. The operation will involve either writing a symbol or moving along the tape, and it will determine the machine head’s next state.

In short, a universal Turing machine also illustrates the formalist’s motto. With respect to syntax (formal operations), a universal Turing machine is just another Turing machine. With respect to semantics (the interpretation of its behaviour), a universal Turing machine simulates another machine described on the ticker tape.

Importantly, the universal Turing machine changes behaviour without needing its own machine table to be altered. To change the behaviour of the universal Turing machine, we simply write a new machine description on the ticker tape. A universal Turing machine’s ability to simulate any other Turing machine also means that it is an exceptionally powerful information processor. A universal Turing machine can answer any formally expressed question. It can answer any question that a modern computer can answer.

1.6 Why Is the Turing Machine Important?

The Turing machine was one of the 20th century’s most important ideas. In mathematics, the Turing machine was important because its computational power originated from simple operations (Section 1.5). Therefore, it could be included in mathematical proofs because its mechanisms were simple and non-controversial (Hodges, 1983).

The Turing machine was central to proving that some mathematical statements are undecidable (Turing, 1936). For an undecidable statement, no method exists to decide whether the statement is true or false. For such a problem, a Turing machine never HALTs; instead, it enters an infinite loop. Turing’s proof revolutionized the field because, prior to Turing, most mathematicians believed that all mathematical statements were decidable.

Created to be used in mathematical proofs, the Turing machine affected other fields as well. It provided the essential foundation for modern computers. The Turing machine’s core components (Figure 1-11) describe the basic properties of computers: a data structure, a basic set of operations, and a method of control.

The modern computer behaves like a Turing machine but far more efficiently. For instance, modern computers use random access memory, permitting immediate access to symbols stored anywhere in memory. A Turing machine accesses memory far less efficiently and must move through a sequence of tape cells to obtain information from a different memory location.

Although modern computers solve problems faster than Turing machines, they are not more powerful. Modern computers cannot answer any question that a universal Turing machine cannot also answer. The Turing machine’s power—the breadth of questions that it can answer—explains its impact on studying cognition.

A Turing machine can solve some psychologically interesting information processing problems. For example, a Turing machine can determine whether a symbol string written on the ticker tape is grammatical or not. One example of such behaviour comes from studying an extremely simple-looking artificial grammar (Bever et al., 1968). Sentences from the grammar contain only two different “words”: a and b. The grammar that Bever et al. studied was b^Nab^N, where N gives the number of b’s in the string. According to this grammar, strings such as a, bab, and bbabb are grammatical, but strings such as ab, babb, bbb, and bbabbb are not. A string is grammatical only if the same number of b’s appear before and after the a.

Bever et al.’s (1968) grammar exhibits embedded clauses: each b before the a is paired with another b after the a. A Turing machine can evaluate grammaticality if strings contain embedded clauses. Humans can as well because natural human languages have embedded clauses. We know that in the sentence “The dog who did not like cats who liked mice ran” the verb ran is associated with the noun dog because of our ability to process embedded clauses.

Less powerful information processors, such as the finite state automaton, cannot deal with embedded clauses in grammars. A finite state automaton is like a Turing machine because it processes a ticker tape with a machine head. However, a finite state automaton can only read symbols, cannot write to the tape, and can only move in one direction along the tape. It reacts to each symbol that it reads: the machine state represents the reaction. When the finite state automaton reaches the end of the question, it stops; its final state represents the answer to the question.

A finite state automaton cannot judge whether symbol strings were generated by a grammar such as b^Nab^N (Bever et al., 1968). Because the device cannot move in both directions along the tape, it cannot track the pairings of b’s that define embedded clauses. Thus, if human cognition is information processing, then cognitive operations must be like those performed by a Turing machine and not like those of a finite state automaton. Processing the embedded clauses of human grammar, for instance, cannot be accomplished by simpler information processors. When cognitivists assume that “cognition is information processing,” they also assume that cognition can be described with a universal Turing machine.

1.7 The Modern Computer

Turing proposed the Turing machine as a hypothetical device to include in mathematical proofs. The Turing machine was never intended to be built; its simplicity made it impractical. However, the Turing machine inspired a more practical device, the digital computer, developed to meet the challenges of the Second World War.

British engineer Tommy Flowers built the first electronic computer, Colossus, in 1943. Colossus deciphered encoded German military messages. In 1946, John Mauchly and J. Presper Eckert created the first American electronic computer (ENIAC) at the University of Pennsylvania; ENIAC created artillery firing tables for the United States Army.

In 1951, the world saw the first commercial computers. The University of Manchester received the first, the Ferranti Mark I, in February. Soon after the University of Toronto purchased a similar machine. The advent of commercial computers permitted researchers to explore which problems computers could solve (Boden, 1977; Feigenbaum & Feldman, 1963; Hofstadter, 1979; McCorduck, 1979; Nilsson, 2010).

Early research focused on programming computers to play board games such as chess or checkers. Formal games provided ideal test cases for exploring machine intelligence. As we have seen, the rules for formal games are simple, but they can create complex game situations to challenge even the best human players. If computers could play high-level chess or checkers, then perhaps machines could achieve human-like intelligence.

The first successful game-playing programs appeared in the early 1950s (Samuel, 1959). Arthur Samuel developed the first checkers program in 1952. By 1955, his program could learn to improve performance by playing against itself. His program would eventually become a good, but not an expert, player.

Four decades later the Chinook program developed at the University of Alberta by Johnathan Schaeffer became the world checkers champion (Schaeffer et al., 1992; Schaeffer et al., 1995; Schaeffer et al., 1993). In 1994, Chinook defeated the reigning human champion, Dr. Marion Tinsley. Similar stories can be told about computers playing other formal games. IBM’s Deep Blue defeated world chess champion Gary Kasparov in a match in 1997 (Campbell et al., 2002). Google’s AlphaGo defeated world go champion Lee Sedol in 2016.

Computers also produced intelligent behaviour outside the realm of games. In the mid-1950s, Herbert Simon, Allan Newell, and John Shaw created a program, the logic theorist, for developing logical proofs (Newell & Simon, 1956). It successfully derived 38 proofs in Russell and Whitehead’s Principia Mathematica. An undergraduate class taught by Simon in 1956, attended by artificial intelligence pioneer Edward Feigenbaum, was told that, “over Christmas, Allan Newell and I invented a thinking machine” (Grier, 2013, p. 74). Simon was talking about the logic theorist.

Many early computer scientists believed that intelligent machines were inevitable. Alan Turing wrote a landmark paper in 1950 to propose how to identify machine intelligence. Two decades into the 21st century, we live in the age of intelligent machines. Computers perform many complex tasks. Banks rely on artificial intelligence to decide about investments and fraud protection. Computers—including our smartphones—translate the spoken word into text. Security systems identify objects and recognize faces. Medical programs diagnose diseases and process huge amounts of patient data. Most domains of human life come into contact with computer programs performing tasks that seemingly require intelligence.

Yet modern computers are formal symbol manipulators no different in kind from Turing machines. Clearly, the formal manipulation of symbols permits machines to behave intelligently. As a result, many researchers believe that symbol manipulation also underlies human intelligence. Perhaps brains perform operations similar to those performed by computers.

1.8 Explaining How Computers Process Information

Cognitive psychology adopts a key working hypothesis: human thinking involves formal operations like those of chess, Turing machines, and electronic computers. Thus, explanations of human cognition will be similar to explanations of computers. How do we explain a computer’s information processing?

We explain computers at different levels of analysis (Chomsky, 1957; Marr, 1982; Pylyshyn, 1984). Each level involves asking a different question and then using a distinct method to answer the question. The most abstract is the computational level of analysis. At the computational level, we answer the question “What information processing problem is the computer solving?” Typically, we express answers to computational questions as proofs, using formal methods such as mathematics and logic.

For example, consider the Section 1.4 Turing machine, which—like any other Turing machine—receives a question and then produces an answer. The computational level of analysis defines which question is being answered. Computational accounts define the mapping from the initial question to the final answer.

The computational level of analysis expresses explanations using mathematics or logic because of a many-to-one relationship. Many different question-answer pairings all belong to the same information processing problem. For instance, 2 + 3 = 5, 1 + 6 = 7, 4 + 9 = 13, and so on all involve calculating integer sums. In fact, an infinite number of different examples of adding integers exist; the Turing machine of Section 1.4 could handle each and every one.

Rather than providing an infinitely long list of question-answer pairings, computational explanations are far more compact. For instance, the Section 1.4 Turing machine deletes the string 0B0 separating the 1’s of the two integers on the initial tape and then moves all the symbols down three cells to fill in these three deleted values, creating a single integer (the sum of the original two). Describing the machine in this way proves that it adds two integers; the proof provides a computational account of the Turing machine.

A second approach examines a computer at the algorithmic level of analysis. An algorithm or program is a sequence of operations for accomplishing a task. An algorithmic account of a computer explains its behaviour by describing the program being executed. The computer behaves one way when executing a word processing program, but it behaves differently when executing a web browser program. An algorithmic account of a universal machine would focus on the “machine description” on the ticker tape, which serves as the program that the universal machine is executing. If we change the machine description on the tape, then the universal Turing machine’s behaviour will change.

A third approach to explaining a computer occurs at the architectural level of analysis. The architecture consists of the properties built into a computer to process information. Architectural accounts answer questions such as “What serves as the device’s memory?” “Which symbols can the device store?” “Which basic operations manipulate symbols?” “How are these basic operations selected?” An architectural account of a universal Turing machine would focus on symbols on the ticker tape, on possible machine states, and on machine table contents.

We call a computer’s architecture primitive because the architecture belongs to the machine’s physical structure. Later we will see that identifying an architecture—an information processor’s primitives—converts cognitive descriptions into cognitive explanations.

Physical properties bring a computer’s architecture into being. As a result, the implementational level of analysis provides a fourth approach to explaining a computer. An implementational account explains how the computer’s physical properties create primitive information processing properties (the architecture). How do physical mechanisms produce the primitive operations used to manipulate symbols?

In summary, we can explain a computer at four different levels of analysis: implementational, architectural, algorithmic, and computational. A complete explanation requires appealing to each level: explaining which problem is being solved, which algorithm is being used, which basic operations make up the algorithm, and which physical mechanisms bring primitive operations to life. When we assume human cognition to be information processing, human information processing must be explained in a similar fashion. Cognitive psychologists try to explain human cognition in the same way that computer scientists explain computers.

1.9 A Hierarchy of Levels

The different types of analysis for explaining information processors are hierarchically organized; a many-to-one relationship exists from one level to the level above it (Dawson, 1998, 2013).

A many-to-one relationship exists from the algorithmic level to the computational level. Different algorithms can solve the same problem. Consider calculating the product of two integers, x and y. One algorithm adds x to itself y different times. A different algorithm computes the logarithm of x, computes the logarithm of y, adds the two logarithms together, and takes the antilogarithm of the sum. Both algorithms determine the product of x and y but are very different from one another.

Another many-to-one relationship exists from the architectural level to the algorithmic level. Different architectures can run the same algorithm. Imagine multiplying two integers together using the logarithmic algorithm described above. The algorithm could be carried out by the specialized machine table of Turing machine Z. But a Turing machine with a very different architecture could execute the same algorithm: the universal Turing machine simulating Turing machine Z.

Finally, a many-to-one relationship exists from the implementational level to the architectural level. Different physical mechanisms can bring the same architecture to life. Consider constructing an architecture to define a particular Turing machine. We might imagine an architecture with an electromechanical tape head for processing a paper ticker tape. But other physical designs are possible. Turing machines have been constructed from LEGO, Meccano, wood, and toy train sets (Ferrari, 2006; Stewart, 1994).

Figure 1-12 illustrates the many-to-one relationships between levels, showing that one architecture can be implemented by many different physical implementations, many different architectures can be used to program one algorithm, and many different algorithms can carry out the same computation.

When we explain information processing, we must consider relationships between levels. Explanations must detail how particular operations are primitive, how operations are organized to create an algorithm, and how the algorithm solves an information processing problem. Comparisons between two systems (e.g., between a computer simulation and a human subject) must also be made at different levels. Do the two systems solve the same problem? Do the two systems use the same algorithm? Do the two systems use the same architecture?

However, comparing systems at the implementational level is not a priority. Provided that two systems bring the same architecture into being, we need not worry whether they do so with different physical mechanisms, provided that we endorse functionalism (Section 1.2). Indeed, computer simulations of cognition make sense only when we ignore implementational differences between computers and brains.

1.10 Explaining Human Cognition

Computers use formal operations to manipulate symbols stored in data structures. Computers preserve meanings, or create new meanings, even though formal operations ignore what symbols represent. Computers bring the formalist’s motto to life by taking care of the syntax while letting the semantics of symbols take care of itself.

Cognitive psychologists assume that they can explain human cognition just as we would explain a computer’s information processing. How do we explain a computer? We could detail the properties of its data structures, of its basic operations, and of its control. When we assume that cognition is computation, we must assume that the same approach can be applied to human thinking. Alternatively, we could examine a computer at multiple levels: computational, algorithmic, architectural, and implementational. Cognitivists believe that human cognition can be explained at these different levels.

However, there is an important difference between computers and humans, making human cognition much harder to explain.

Consider asking a programmer to add new features to a computer program. Computers have operations to permit the programmer to see a program’s properties. The programmer can list the program’s steps or examine the data files that the program processes. In other words, the programmer can directly observe the computer’s information processing.

Psychologists cannot examine human cognition in the same fashion. For a cognitive psychologist, a human participant is a black box. Researchers can directly observe stimuli presented to a participant as well as a participant’s responses. However, cognitive psychologists cannot directly observe internal processes of converting stimuli into responses. These psychologists assume that human thinking is rule-governed symbol manipulation but cannot directly observe human information processing’s data structures, operations, or control.

In response, cognitive psychologists design clever experiments to permit them to observe subtle relationships between stimuli and responses. Armed with such data, they infer the properties of the information processing that cannot be directly observed. Cognitive psychologists create models of human information processing and use the fine details of experimental data to validate their models. Chapter 2 introduces the reader to this research strategy.

1.11 Chapter Summary

According to Vico’s certum quod factum principle, we are only “certain of what we build.” Science exploits Vico’s principle by using the properties of well-understood human devices to illuminate less-understood phenomena. For instance, cognitive psychologists treat thinking as analogous to the operations carried out by computers. They hope that the well-understood properties of computers will help us to understand human cognition. Computer performance fuels their hope because computers can perform many tasks that ordinarily require human intelligence.

If computers can produce intelligent behaviour, then computer-like operations might provide the foundation for human intelligence. Thus, cognitive psychologists assume that cognition is computation, where “computation” is rule-governed symbol manipulation.

To explain a computer’s information processing, we could detail data structures, basic operations, and control. We could also examine a computer at multiple levels of analysis. What information processing problem is being solved? Which algorithm is used to solve the problem? What are the operations used by the algorithm? Which mechanisms bring the operations into being?

Cognitive psychologists aim to explain human cognition the same way. What are the properties of the data structures, operations, and control of human cognition? How can we explain human cognition at the four different levels of analysis?

However, cognitive psychologists encounter a difficult problem when answering such questions. Unlike computer programmers, cognitive psychologists cannot directly observe the core properties of human information processing. Instead, they can only observe stimulus-response relationships mediated by human information processing. Clever experiments must be designed to permit cognitive psychologists to infer information processing details from observable behaviour.

We can now explore the research strategies used by cognitive psychologists. Chapter 2 provides example experiments conducted by cognitive psychologists to support the assumption that cognition is computation. With these examples in hand, Chapter 3 introduces the philosophical foundations of theories of human cognition.