Greg Bowering 1998
One theory for how the mind represents facts about the world postulates an internal quasi-linguistic symbolic code. The theory then attempts to explain how the mind works by postulating automatic formal systems, rules for manipulating such representations. This is the essence of the Classical Computational Theory of Cognition (Classicism) (Pylyshyn, 1984, and Fodor, 1975, cited by both Bechtell, 1988, Ch.4, and Copeland, 1993, Ch.9).
The Artificial Intelligence (AI) research effort aims to devise machines that behave intelligently. Computer Science has successfully developed machines that are astoundingly good at moronic symbol-crunching. Many tasks have successfully been couched in terms of such symbol-crunching: algorithms reduce such tasks to collections of simple, discrete symbol manipulations. However, other tasks have been found more problematic to so reduce: either no algorithm can be easily devised, or those that are turn out to be awkward and inefficient, often to the extreme of being infeasible to implement, or too slow to be useful. Ironically, a good deal of tasks that humans accomplish with apparent ease fall into this category. Nature has teasingly proved the existence of one solution for these problematic tasks: that employed by the human mind. This gives some hope to the research efforts of Strong AI, which aims to develop AI not merely as a useful tool, but as a provider of a second solution to all such problems, to create a machine that can at least equal the intelligence that humans possess. For a second solution to exist, the mind must have multiple realisability: the property that in principle the mind can be implemented in something besides the brain, in the same manner that the game of chess is not restricted to being played on just one kind of chess-set. However, the mind presents properties and abilities that seriously resist explanation, replication or simulation in terms of systems of formal symbol manipulation. This is the problem that confronts the Traditional (symbolic) approach to AI.
Traditional AI postulates that intelligence can be manifest in an appropriate symbol system, the "Symbol System Hypothesis" (SSH)(described in Copeland, 1993, Ch.4). In precise terms, Copeland's portrayal of the hypothesis is that an appropriate symbol system is sufficient for general intelligence. The hypothesis is that 'yes' is the correct answer to Turing's question, "Can Machine's Think?" The SSH raises the possibility that human intelligence might be the manifestation of internal symbol systems. In so doing, it lends necessary (but not sufficient) support to Classicism (in that Classicism relies on the SSH being true, but does not follow automatically).
Where strong AI intersects with traditional AI we find the "Strong Symbol System Hypothesis" (SSSH)(Copeland, 1993, Ch.9, and in Rich and Knight, 1991, Ch.1). It postulates that symbol systems are the only things that can be intelligent. Accordingly, symbol systems are both necessary and sufficient for general intelligent action. In particular, if the SSSH is true, human intelligence is a manifestation of symbol systems. In this sense the SSSH and Classicism have a logical equivalence: either both are true or both are false. Thus the SSSH and Classicism must go hand-in-hand, face both support and objections together, and survive or perish together in the mind. Whilst the SSSH proposes that all intelligence is manifest in symbol systems, it equally proposes that anything not qualifying as a symbol system cannot be intelligent. It therefore excludes other theories of mind that are incompatible with Classicism.
For logical completeness, it is worth considering a less known sister of the SSH, which for convenience we might term the "Weak Symbol System Hypothesis" (WSSH). Although this hypothesis has most likely been entertained elsewhere, I have yet to encounter it stated explicitly: that a symbol system has necessary means for general intelligent action. The truth of the WSSH would guarantee that symbol systems play an essential role in realising intelligence, but not guarantee that they are the only necessary ingredient. It does not therefore guarantee that Classicism can provide the whole answer. The prospect of formal symbol systems being insufficient for the mind is a serious threat to Classicism. Similarly, because of its reliance on purely formal symbol systems, the possibility of multiple realisability of the mind would be cast into doubt. The SSSH is as much of an extension of the WSSH as it is of the SSH, and if the strong hypothesis were to be false, at most one of the two weaker might yet be true (the SSSH is the logical conjunction of the SSH and the WSSH).
Dennett (1984) points out that we know an infinite number of propositions. For example, we know that "0 is greater than -9876". Classicism is thus required to accept, by issue of finite brain size, that we can only represent a fragment of our knowledge in explicit quasi-linguistic form. There must be a lot of knowledge stored in potentially explicit representations. For example, the number relation above, and an infinite number of others like it can inferred from more general, generative facts about number theory. But which generative facts do we use, and how many inferences does it take? More to the point, at the level of syntactic symbol manipulations, what symbols do we manipulate, and how many manipulations must be executed? It is a fact that most Von-Neumann computers evaluate the "greater than" relation on integers by subtracting one number from the other and then testing the sign of the result. However it must be noted that such computers have been blessed with this knowledge being tacitly encoded (Fodor, 1981) in their central processor's circuit-logic. For this reason, these computers can evaluate "greater than" rapidly, reliably, and in the same time regardless of the nature of the numbers involved. By comparison, it is intuitively clear that at least most people would more quickly, easily and reliably "know" that "90873245 is greater than 0" than they would "-528707414055555555555 is greater than -5287074140555555555555".
Unfortunately for Classicism, such knowledge can only be used after it is rendered explicit (Block?,1990? cited in O'Brien, 1998, Lecture 10). Consequently Classicism must posit that any reasoning process involving this knowledge must process it deliberately and discretely. This fact alone raises serious doubts as to Classicism's credibility. The reasons for these doubts are presented and discussed in the following sections.
The knowledge problem became evident when traditional AI attempted to devise systems capable of real-time planning in complex environments. Although algorithms for planning are not in themselves difficult to design, most rely on some search of possible courses of action (Rich and Knight, 1991, Ch.13), and this approach runs into difficulties when extended to real-world problem domains and confronted with real-time performance issues. The example of The Robot Shakey (Raphael, 1976, cited in Copeland, 1993, Ch.5) illustrates these difficulties: it required a painted line to delineate walls from floors, and took days to complete a 'simple' block moving task, stoping for hours at a time to plan each move.
The absolute difference in time is not the most important issue here, since that can be fixed with faster computers. The major concern regards what Computer Science terms the Inherent Intractability of some problems (Garey and Johnson, 1979, cited in Aho and Ullman, 1995). The term Order of Complexity of a computational solution describes the relationship between the size of the problem and the time required to compute a solution via that solution. If the size of the problem is denoted by n, the time-order of complexity for a given solution, denoted O(f(n)) states that computation time varies as some function f of n. The most rare and sought-after algorithm might have f a constant (such as an algorithm for adding a new item to one end of a list). Much more common, but still favourable algorithms exhibit O(n), which is to say that computation time is directly proportional to problem size (as exhibited by an algorithm for counting the number of elements in a list). The term nondeterministic polynomial (NP) describes the set of problems for which no algorithm has been devised that has at most a polynomial order of complexity. The hardest NP problems have been proved to be equivalent in terms of their inherent tractability. Such problems are termed NP-complete. They share the property that if a deterministic polynomial order computational solution is ever discovered for one, it proves the existence of such a solution for all others in the class. Unfortunately a large proportion of tasks facing AI are NP-complete, which explains why the performance of algorithms for accomplishing them so often degrade in dismal disproportion to the problem size. Since the algorithms of formal systems are all deterministic, they can never, by definition, solve an NP-complete problem in polynomial time. This theory of inherent intractability imposes no such limitations on alternative nondeterministic computational systems.
The knowledge problem confronts any system that has to in some sense "blunder" its way towards a result. Such blundering is acceptable in very simple problem-domains or where time is not important, but in real-world situations it turns out that there is an explosion in the amount of blundering required due to a similar explosion in the amount of knowledge required by the system. This explosion in blundering leads to a drastic degradation in speed. More specifically, the problem can be divided firstly into issues relating to how a system can maintain a vast knowledge-base whose performance degrades more gracefully as its size and complexity increases. A second aspect of the knowledge problem concerns the question of how such knowledge can be effectively applied in real-time planning and problem-solving tasks.
Issues facing the symbolic knowledge-base include both syntactic and semantic problems (Dennett, 1984). The syntactic problem covers the questions regarding how knowledge should be represented and organised so as to allow for efficient storage, retrieval and revision. Subtle differences in representational scheme can have wide-reaching implications for the efficiency of the system. Consider Figure 1 below which shows two alternative syntactic representations (from Rich and Knight, 1991, Ch.11) for facts about the room in McCarthy's robot-task (as described in Dennett, 1984). The consequences of the action PULLOUT(WAGON1,ROOM1) are easier to determine in the representation (A) whose structure more closely matches that of the thing it represents. (More about this example soon.) The semantic problems include both the content problem (what should the system know and what should it believe about both real and counterfactual worlds?) and the update problem (how should knowledge and beliefs be revised in light of new evidence, discovered inconsistency, success and failure, or temporal changes in the world?) The part of the update problem caused by the temporal-logical consequences of events was what originally inspired McCarthy and Hayes (1969, cited in Haugeland, 1985) to formulate the "frame problem". In its original formulation, it is the problem of how a system is to distinguish between perennial knowledge, and that which is subject to temporal change. Figure 1 hints at a way in which the structure of syntax used can allow for some of the problem to be avoided. In the second knowledge-base (B), PULLOUT(WAGON1,ROOM1) requires a complicated decision as to what propositions should change followed by a deliberate exhaustive search-and-replace revision to be made over discrete terms. By contrast, the first knowledge-base (A) is structured in such a way that only one re-location of a definite collection of symbols is required (those within the scope of WAGON1) and the logical consequences are automatically taken care of by the structure.
A:
(ROOM1:
colour-of: #FF0000
has-in:
(WAGON1:
colour-of: #00B000
has-on:
(BATTERY1:
colour-of: #9500C0
)
(BOMB1:
colour-of: #000000)
)
(BIN1: ... )
)
B:
colour-of(ROOM1,#FF0000)
colour-of(WAGON1,#00B000)
colour-of(BATTERY1,#9500C0)
colour-of(BOMB1,#000000)
in(WAGON1,ROOM1)
in(BIN1,ROOM1)
on(BATTERY1,WAGON1)
on(BOMB1,WAGON1)
Figure 1: the role of structure in representations.The relevance problem is central to the question of how knowledge can be efficaciously brought to bear on a given task (Dennett, 1984). As Dennett points out, it does not solve the problem for the system to be able to discretely identify an irrelevant fact or inference. What is required is for irrelevant information to never even enter into the process. Ideally, the required relevant information would nominate itself for the problem at hand. The problem is: how? Returning to Figure 1, case A intuitively appears to have advantages over case B. In the former, the fact that both the bomb and the battery move with the wagon is implicit in the representation. In the latter, additional logic must be employed to infer this fact.
One reason why representational structure might help save Classicism from the Knowledge Problem is that hierarchical structure allows for abstract information processing. Whilst abstract processing is always possible in the sense that high-level "procedures" can spare the programmer from exposure to the underlying detailed complexity, such language-level abstraction is merely a programmer's aid, and has no effect on the program's performance. The atomically abstract manipulation of abstract data (such as changing the name or location of a computer file by modifying a directory entry, as opposed to laboriously copying the file piecemeal) provides unlimited performance benefits over solutions composed of large numbers of primitive operations. Perhaps a symbol system based on a different set of primitives to those of von-Neumann machines would serve to avoid aspects of the Knowledge Problem. Possible candidates may include McCarthy's LISP (1959, cited in Haugeland, 1985), and Newell's Production Systems (1976, cited in Haugeland, 1985). Although such systems appear to handle knowledge problems in one sense, it sometimes turns out that they have only been displaced, and ultimately turn up in other guises.
The Knowledge Problem highlights the inadequacy of the current state of Classicism in providing explanation for the mind to maintain and use knowledge and beliefs about both the real world and counterfactual worlds. Part of the problem lies in the way Classicism is forced to admit that most of the information represented in the mind is only potentially explicit. Such representations are problematic for the real-time performance of a symbol system because they can only be causally efficacious once rendered explicit. Furthermore, since formal systems are self-contained and do not reference the outside world (Haugeland, 1985), Classicism cannot allow for the meaning of a mental token to depend on its context, nor for tokens to be categorised on the basis of their meanings. Therefore Classicism is bound to a scheme of processing whereby symbols are accessed individually and processed discretely, a scheme that seems to require an discouragingly number of little steps in order to achieve even simple tasks in the real world.
The relatively dismal performance of symbol system algorithms is evident in two distinct ways. The first, as previously mentioned, relates to the disproportionate rate at which performance degrades in relation to problem size. Since real-world complexities threaten vast problem sizes, inherently intractable algorithmic solutions have no hope of meeting real-time performance goals. Thus Classicism is slain by the dual natures of algorithmic computability and real-world complexity. Copeland (1993, Ch.9) identifies another problem with the speed of symbol systems which is revealed by neuroscience. The transition delay inherent in neurons (how long it takes for a change in dendritic stimulation to propagate effect through the neuron and axonal projections and hence influence neighbouring neurons) is about a million times slower than the state transition of an electronic flip-flop. Similarly, we can compare the rate at which modern personal computers perform machine-level instructions(200-300MHz), with the firing frequencies of neurons (20-500Hz) and find another million-fold speed disparity. If modern electronic digital hardware has a million-fold speed advantage over human "wetware" and yet cannot achieve more than a scratch against the latter's performance, we must wonder whether the digital approach is not seriously flawed somehow.
Both Classicism and its more creative, hands-on counterpart, Strong Traditional AI espouse the view that appropriate automatic formal symbol systems are in themselves the essence of intelligence, and furthermore, the only such essence. The reality presented by the Knowledge Problem, in its various forms seriously challenges this view to demonstrate precisely how such systems can possibly explain or replicate real-world, real-time intelligent performance. Interrogated under the empirical spotlight, it seems that nothing short of a plausible solution to the Knowledge Problem can spare Classicism such fatal torture. That is why the Knowledge Problem is considerably one of the most formidable facing the Classical Computational Theory of Cognition.
Aho, A.V.and Ullman, J.D. 1995. Foundations of Computer Science, C ed. W.H. Freeman.
Bechtell, W. 1988. Philosophy of mind: an overview for Cognitive Science. Hillsdale, NJ: Lawrence Erlbaum Associates.
Copeland, J. 1993. Artificial Intelligence: A Philosophical Introduction, Ch.5. Blackwell.
Dennett, D.C. 1984. Cognitive Wheels: The frame problem of AI. In C. Hookaway, ed., Minds, Machines and Evolution, pp.129-151. Cambridge University Press.
Fodor, J. 1981. Representations, Ch.2. MIT Press.
Haugeland, J. 1985. Artificial Intelligence: The Very Idea, pp.185-254. MIT Press.
Haugeland, J. 1987. An overview of the frame problem. In Z.W. Pylyshyn, ed., The Robot's Dilemma, pp.77-93. Norwood, NJ: Ablex.
O'Brien, G. 1998. Cognitive Science: Minds, Brains and Computers. Lecture 10. Unpublished lecture notes.
Rich, E. and Knight, K. 1991. Artificial Intelligence, 2nd ed., McGraw-Hill.
Winston, P.H. 1981. Artificial Intelligence, 2nd ed., Addison-Wesley.