1.6—
Formalization and Computation
CTM's advocates believe that machine computation provides a paradigm for understanding how one can have a symbol-manipulating system that can cause derivations of symbolic representations in a fashion that "respects" their semantic properties. More specifically, machine computation is believed to provide answers to two questions: (1) How can semantic properties of symbols be linked to causal powers that allow the presence of one symbol token s1 at time t to be a partial cause of the tokening of a second symbol s2 at time t +
The answers that CTM's advocates would like to provide for these questions can be developed in two stages. First, work in the formalization of symbol systems in nineteenth- and twentieth-century mathematics has shown that, for substantial (albeit limited) interpreted symbolic domains (such as geometry and algebra), one can find ways of carrying out valid derivations in a fashion that does not depend upon the mathematician's intuition of the meanings of the symbols, so long as (a ) the semantic distinctions between the symbols are reflected by syntactic distinctions, and (b ) one can develop a series of rules, dependent wholly upon the syntactic features of symbol structures, that will license those deductions and only those deductions that one would wish to have licensed on the basis of the meanings of the terms. Second, digital computers are devices that store and manipulate symbolic representations.
Their "manipulation" of symbolic representations, moreover, consists in creating new symbol tokens, and the regularities that govern what new tokens are to be generated may be cast in the form of derivation-licensing rules based upon the syntactic features of the symbols already tokened in computer storage. In a computer, symbols play causal roles in the generation of new symbols, and the causal role that a symbol can play is determined by its syntactic type. Formalization shows that (for limited domains) the semantic properties of a set of symbols can be "mirrored" by syntactic properties; digital computers offer proof that the syntactic properties of symbols can be causal determinants in the generation of new symbols. All in all, the computer paradigm shows that one can coordinate the semantic properties of representations with the causal roles they may play by encoding all semantic distinctions in syntax.
These crucial notions of formalization and computation will now be discussed in greater detail. These notions are, no doubt, already familiar to many readers. However, how one tells the story about these notions significantly influences the conclusions one is likely to draw about how they may be employed, and so it seems worthwhile to tell the story right from the start.
1.6.1—
Formalization
In the second half of the nineteenth century, one of the most important issues in mathematics was the formalization of mathematical systems. The formalization of a mathematical system consists in the elimination from the system's deduction rules of anything dependent upon the meanings of the terms. Formalization became an important issue in mathematics after Gauss, Bolyai, Lobachevski, and Riemann independently found consistent geometries that denied Euclid's parallel postulate. This led to a desire to relieve the procedures employed in mathematical deductions of all dependence upon the semantic intuitions of the mathematician (for example, her Euclidean spatial intuitions). The process of formalization found a definitive spokesman in David Hilbert, whose book on the foundations of geometry, published in 1899, employed an approach to axiomatization that involved a complete abstraction from the meanings of the symbols. The formalization of logic, meanwhile, had been undertaken by Boole and later by Frege, Whitehead, and Russell, and the formalization of arithmetic by Peano.
While there were several different approaches to formalization in nineteenth-century mathematics, Hilbert's "symbol-game" approach is of
special interest for our purposes. In this approach, the symbols used in proofs are treated as tokens or pieces in a game, the "rules" of which govern the formation of expressions and the validity of deductions in that system. The rules employed in the symbol game, however, apply to formulae only insofar as the formulae fall under particular syntactic types. This ideal of formalization in a mathematical domain requires the ability to characterize, entirely in notational (symbolic and syntactic) terms, (a ) the rules for well-formedness of symbols, (b ) the rules for well-formedness of formulas, (c ) the axioms, and (d ) the rules that license derivations.
What is of interest about formalizability for our purposes is that, for limited domains, one can find methods for producing derivations that respect the meanings of the terms but do not rely upon the mathematician's knowledge of those meanings, because the method is based solely upon their syntactic features. Thus, for example, a logician might know a derivation-licensing rule to the effect that, whenever formulas of the form p and pÉq have been derived, he may validly derive a formula of the form q . To apply this rule, he need not know the interpretations of any of the substitution instances of p and q , or even know what relation is expressed by É , but need only be able to recognize symbol structures as having the syntactic forms p and p Éq . As a consequence, one can carry out rational, sense- and truth-preserving inferences without attending to—or even knowing—the meanings of the terms, so long as one can devise a set of syntactic types and a set of formal rules that capture all of the semantic distinctions necessary to license deductions in a given domain.
1.6.2—
A Mathematical Notion of Computation
A second issue arising from turn-of-the-century mathematics was the question of what functions are "computable" in the sense of being subject to evaluation by the application of a rote procedure or algorithm. The procedures learned for evaluating integrals are good examples of computational algorithms. Learning integration is a matter of learning to identify expressions as members of particular syntactically characterized classes and learning how to produce the corresponding expressions that indicate the values of their integrals. One learns, for example, that integrals with the form
Such computational methods are formal, in the sense that a person's ability to apply the method does not require any understanding of the
meanings of the terms.[10] To evaluate
1.6.3—
The Scope of Formal Symbol-Manipulation Techniques
It turns out that formal inference techniques have a surprisingly wide scope. In the nineteenth and early twentieth century it was shown that large portions of logic and mathematics are subject to formalization. And this is true not only in logic and number theory, which some theorists hold to be devoid of semantic content, but also in such domains as geometry, where the terms clearly have considerable semantic content. Hilbert (1899), for example, demonstrated that it is possible to formulate a collection of syntactic types, axioms, and derivation-licensing rules that is rich enough to license as valid all of the geometric derivations one would wish for on semantic grounds while excluding as invalid any derivations that would be excluded on semantic grounds.
Similarly, many problems lying outside of mathematics that involve highly context-specific semantic information can be given a formal characterization. A game such as chess, for example, may be represented by (1) a set of symbols representing the pieces, (2) expressions representing possible states of the board, (3) an expression picking out the initial state of the board, and (4) a set of rules governing the legality of moves by mapping expressions representing legal states of the board after a move m to the set of expressions representing legal successor states after move m + 1. Some games, such as tic-tac-toe, also admit of algorithmic strategies that assure a winning or nonlosing game. In addition to games, it is
also possible to represent the essential features of many real-world processes in formal models of the sorts employed by physicists, engineers, and economists. In general, a process can be modeled if one can find an adequate way of representing the objects, relationships, and events that make up the process, and of devising a set of derivation rules that map a representation R of a state S of the process onto a successor representation R* of a state S* just in case the process is such that S* would be the successor state to S . As a consequence, it is possible to devise representational systems in which large amounts of semantic information are encoded syntactically, with the effect that the application of purely syntactic derivation techniques can result in the production of sequences of representations that bear important semantic relationships: notably, sequences that could count as rational, cogent lines of reasoning.
1.6.4—
Computing Machines
The formalizability of limited symbolic domains shows that semantic distinctions can be preserved syntactically and that the application of syntactic derivation rules can result in a semantically cogent sequence of representations. In crude terms, formalization shows us how to link semantics to syntax. What is required, however, is a way of linking the semantic properties of representations with their ability to play a causal role in the generation of new representations to which they bear interesting semantic relationships (see fig. 3). In and of themselves, formal proof methods and formal algorithms do not provide such a link, since they depend upon the actions of the human computer who applies them. It is the paradigm of machine computation that provides a way of connecting the causal roles played by representations with their syntactic properties, and thus indirectly linking semantics with causal role.
The crucial transition from formal techniques dependent upon a human mathematician to mechanical computation came in Alan Turing's "On Computable Numbers" (1936). This paper was framed as an answer to the mathematical problem of finding a general characterization of the class of functions that admit of computational (i.e., algorithmic) solutions. Turing's approach to this problem was to describe a machine that was capable of scanning and printing symbols printed on a tape and governed in part by internal mechanisms and in part by the specific symbols found on the tape. Some of the details of this machine are described in chapter 5, but for present purposes it suffices to say that Turing
Figure 3
showed that any computation that can be evaluated by application of a formal algorithm can be performed by a digital machine of the sort he specifies. The original intent of Turing's article was to provide a general description of all computable functions: a function is computable just in case it can be evaluated by a Turing machine. But in providing this answer to a problem in mathematics, Turing also showed something far more interesting for psychologists and philosophers: namely, that it is possible to design machines that not only passively store symbols for human use, but also actively distinguish symbols on the basis of their shape and their syntactic ordering, and indeed operate in a fashion that is partially determined by the syntactic properties of the symbols on which they operate. In short, Turing showed that it is possible to link syntax to causal powers in a computing machine.
A computing machine is a device that possesses several distinctive features. First, it contains media in which symbolic representations can be stored. These symbols, like written symbols, can be arranged into expressions having syntactic structures and may be assigned interpretations through an interpretation scheme. Second, a computer is capable of differentiating between representations in a fashion corresponding to distinctions in their syntactic "shape." Third, it can cause the tokening of new representations. Finally, the causal regularities that govern what new symbols the computer will cause to be tokened are dependent upon the syntactic form of the symbols already stored by the machine.
To take a simple example, suppose that a computer is programmed to sample two storage locations A and B where representations of integers are stored and to cause a tokening of a representation at a third
location C in such a fashion that the representation tokened at C will be a representation of the sum of the two numbers represented at A and B . The representations found at A , B , and C have syntactic structure: let us assume that each representation is a series of binary digits (1s and 0s). They also have semantic interpretations: namely, those assigned to them by the interpretation scheme employed by the designer of the program. Now when the computer executes the program, it will cause the tokening of a representation at C . Just what representation is tokened at C will depend upon what representations are found at A and B . More specifically, it will depend upon the syntactic type of the representations found at A and B —namely, upon what sequences of binary digits are present at those locations. What the computer does in executing this program is thus analogous to the application of a formal algorithm (such as that employed in column addition), which is sensitive to the syntactic forms of the representations at A and B . If the program has been properly designed, the overall process will accurately mimic addition as well, in the sense that what is tokened at C will always be a representation of the sum of the two numbers represented at A and B . That is, if the program is properly designed, the syntactically dependent operations performed by the machine will ensure the production of a representation at C that bears the desired semantic relations to the representations at A and B as well.[11] The semantic properties of the representations play no causal role in the process—they are etiologically inert. But since all semantic distinctions are preserved syntactically, and syntactic type determines what a representation can contribute causally, there is a correspondence between a representation's semantic properties and the causal role it can play.
This example illustrates three salient points. The first is the insight borrowed from formal logic and mathematics that at least some semantic relations can be reflected or "tracked" by syntactic relations. The second is the insight borrowed from computer science that machines can be made to operate upon symbols in such a way that the syntactic properties of the symbols can be reflected in their causal roles. Indeed, for any problem that can be solved by the application of a formal algorithm A , it is possible to design a machine M that will generate a series of representations corresponding to those that would be produced by the application of algorithm A . These two points jointly yield a third: namely, that it is possible for machines to operate upon symbols in a way that is, in Fodor's words, "sensitive solely to syntactic properties" of the symbols and "entirely confined to altering their shapes," while at the same time
Figure 4
the machine is so devised that it will transform one symbol into another if and only if the propositions
expressed by the symbols that are so transformed stand in certain semantic relations—e.g.,
the relation that the premises bear to the conclusion of a valid argument. (Fodor 1987: 19)
In brief, "computers show us how to connect semantical with causal properties for symbols " (ibid.). And this completes the desired linkage between semantics and causality: for domains that can be formalized, semantic properties can be linked to causal properties by encoding semantic differences in syntax and designing a machine that is driven by the syntactic features of the symbols (see fig. 4).