| We have arrived at a rather minimal agent who can understand and carry out very simple instructions. (If you want to read Turing's development of these ideas, click here.) But can this agent be instructed to solve any really interesting problems? Only a very small subset of problems? All problems? ... |
| Well, we can define several interestingly different agents by only slightly altering the way they are constructed. The simplest machine or automaton that we think of as a computational device is called a finite state machine (FSM). This machine can read from its input tape, but most significantly, it can not write on the tape. So what, you might say. Well, think of yourself doing some long division problem, or shopping for a big party, or doing the cryptarithmetic problem that we did earlier. Now, what if you couldn't write anything down to aid yourself in carrying out the computation required? It turns out that if you can't write to a memory, then certain types of functions can not be computed using this limited instruction set/agent. Exactly what these limits are is a bit more subtle than you probably can imagine. So don't trust your intuitions. But, do explore the idea of an FSM a bit further by perusing some of the further information provided below. |
The example above showed that we could recognize the set consisting of 0 to n a's followed by 1 to m b's. Note, this set has no largest element. One million a's followed by 10 b's or whatever, is included. So the size of the set or language recognized is not the critical feature. What is critical is whether the agent has to keep track of dependencies in the strings that make up the elements of the set. If we change the set or language to strings that involve n a's followed by n b's, then no FSM can recognized this set. In order to recognize this set, we have to keep tack of and make sure that there are exactly the same number of a's as b's. We can write an FSM to do this for a bounded n, say up to 100, but we can't do it in general. And, perhaps more significantly, the FSM doesn't capture regularities of this sort in a succinct and elegant way. A Turing Machine (TM) can recognize this set. The Turing Machine can write to the tape as well as move either direction on the tape. A seemingly small change but one that has some rather amazing consequences. But, before we move on to those, it will help if you study the representation of the Turing Machine referred to below. Try to build a picture of how and why this algorithm works. |
|
Now that you have seen how simple even these machines are, let's turn to the amazing aspects of all this. The first aspect is referred to as Church's Thesis or the Church-Turing Thesis. This thesis is the proposal that the informal notion of "a function that can be computed by an algorithm" (or computed "mechanically") can be identified with the the set of functions computable by a Turing Machine. Roughly, this says that we won't be able to come up with any formalism, F, that captures our intuitive notion of an algorithm that will be more powerful than a Turing Machine. Here "more powerful" means that there are functions that can be computed by F that are not computable by a Turing Machine but not the converse. Thus, this very simple device appears to be sufficient to compute anything that is computable. Aha, the qualification! It turns out that not everything is computable....there are an infinite number of functions that are; and, there are an infinite number of functions that are not...such is life. At least, we now have some understanding of what the limits of computation (or following instructions) are as well as an appreciation for the source of these limitations. Now, for the other amazing aspect. One can construct something called a Universal Turing Machine. It is a Turing Machine just like the others except that its instructions are about how to simulate another Turing Machine! A Turing Machine can be thought of simply as long string of symbols...the tuples that we have become acquainted with. In addition to the tuples, there is the tape, which is also just a string of symbols. And, finally, there are the two control pieces of information that the machine keeps track of...namely; its current control state and the current location of the read head. All of the information can be put together on to a tape. This tape can then be seen as the input to our Universal Turing Machine. The tape contains the program (the specific TM), and the input data. Thus, one can view a TM as data or as instructions describing a process. |
Now, despite being overwhelmed by these amazing facts, you may still wonder what this all has to do with human reasoning! From the advent of work on computation there has always been the question of the relation between computation and the mind. If human reasoning is a kind of computation, then we are a kind of computational device. And, it follows then, that one way to develop an understanding of human reasoning is to try to determine exactly what kind of computational device we are and also determine exactly how we accomplish various reasoning tasks. If we aren't computational devices, then we have to figure out some other way to talk about and study the mind. But even if we aren't a computational device; it is important to understand exactly what constitutes a computational device in order to understand the differences between mind and machine. |
Computational Approach |
||
| © Charles F. Schmidt | ||