Now a Turing Machine and by extension a physical symbol system specifies the "stuff" needed in order to "write a program" that computes some desired output from some input expression. However, up until now some person has written the program. A truly intelligent device should be able to write its own programs! There are two extreme possibilities for accomplishing this. The first would be a kind of extreme "nativist" position. On this view, the device starts out with all of the "programs" that it could ever want or use and it simply has to be able to recognize which program is appropriate to a given situation and perhaps parametrize the program appropriately. This is a kind of program library idea of intelligence. The other extreme is that the device begins its life as a kind of "blank" Turing Machine. That is, it has a memory or tape, some general and fixed finite automaton to control its basic processes of reading, writing, and moving the tape (i.e., accessing its memory), and it has some stock of symbols together with a syntax for constructing expressions from these symbols. This "blank" or "initial" Turing Machine then learns all of its programs as a result of its experience. This is a kind of extreme "empiricist" position.

Can we say anything about which of these views is correct? Well, it looks like we can reject both of these extreme positions. The flexibility of human behavior and our ability to adapt to entirely new and unique situations suggests that we are not limited to a fixed set of "biologically" provided programs. Thus, this extreme nativist position seems quite implausible. It also turns out that we can reject the extreme empiricist position because we can prove that certain types of "programs" can not be learned by a Turing Machine even with unlimited "tape" and "time". The rules that govern our use of natural language seem to be one of the things that can't be learned by our "initial" Turing Machine. Rather, we require the system to have an appropriate bias in order to learn natural language.

Consequently, the current general position is that in order for a system to be intelligent it must be capable of learning or "programming itself" and at the same time it probably must, in many cases, approach its world with just the right biases about how to learn or "program itself".

 Weak Methods

AI attempted to respond to this problem of how to achieve intelligence without "programming" by "augmenting" the basic computational model defined by a Turing Machine. They did this by introducing the idea of a Weak Method. What is desired is to identify a perfectly general "program" or "method" that is as dumb as imaginable, but can provide the basis for "becoming more intelligent" through some learning mechanism.

The basic idea is referred to as generate and test. What this involves is being able to generate candidate solutions to some problem and then being able to test whether a candidate solution is in fact the solution to the problem. For example, say you are given the problem 2x + 2 = 10 and asked to provide the value for x. Now, assume you know absolutely nothing about algebra; that is, you have no special "program" or method for solving this type of problem. What could you do?

Well, let's assume that you do know how to evaluate an arithmetic expression. Consequently, you can compute the value of an expression like 2(100) + 2 = 202. Given this ability to evaluate arithmetical expressions, you can then use that ability to specify a test. That is, you can see if 202 equals 10. Since it does not, you can conclude that 100 is not the solution to this problem. Now, you also need the ability to generate these candidate solutions. In this case this ability to generate candidate solutions can be achieved by simply being able to generate a number,...any number. So you need some sort of rule that generates a number, then you test that number to see if it is a solution. If the test succeeds, then stop and write out the solution. If not, simply generate another number, and so on. This is what is known as blind search. It is blind in the sense that there is not only no knowledge that is being used to direct the search, but also in the sense that the search is unsystematic. It is about the dumbest thing that we can imagine. The idea goes back to what is termed the British Museum Algorithm which gets its name from the notion that if you put a chimp or whatever in front of a typewriter, then eventually this chimp will generate all the books in the British Museum!

Graph Search

Blind search is obviously a very unsystematic and inefficient procedure. In order to increase efficiency we must explore various ways in which to control the generation of alternatives. Thus, in addition to a set of generators and a way of testing the candidates generated, we also need a control structure. Different types of control can easily be visualized if we represent the various candidates generated as nodes in a search graph. In state space search, we can think of each node as representing a legal state, i.e., some representation that denotes a state consistent with some "axiomatization" of the domain. A link from one such node N (state) to another node M (state) is used to denote the fact that the application of some generator to state N maps this state into state M. In this case, state M is said to be directly reachable from state N. There, of course, may be many states other than M that are directly reachable from N. The number of such states is often referred to as the branching factor. Graphically, these alternatives are represented as a set of links going from N to the set of directly reachable states {M1, M2, ...Mi,...,Mj}. Of course, it is typically the case that many different states can be reached from each of the states Mi. For example, state L1 may be directly reachable from M1, and so on. In this case we say that L1 is reachable from N since there exists a path of states from N to L1. Of course, there may be more than one path from N to L1 and there may be many ways to reach L1 that do not go through N. A systematic search method is one that efficiently organizes the generation and search for such paths. Since state space search typically begins with the start state/node and proceeds via generation of reachable states from this start state; the representation of the space searched at any point in the process has the appearance of a tree. (It isn't technically a tree of states unless the search method includes within it a procedure which insures that any cycle, i.e., a path to a state already reached on that path; is eliminated. However, it is a tree if we think only in terms of the generation of the nodes (rather than the states "associated with" the nodes). In a tree, the start node is often referred to as the root of the tree. (The root is at the "top", however.) The nodes that are directly reached from another node N, are often referred to as the children of node N and node N as the parent. If two nodes have the same parent, they are said to be siblings. Nodes that are on the path to a node, M, are referred to as the ancestors of M.

These ideas will become clearer if we examine some graphic example of the basic Exhaustive Search Methods