Information Technology Reference
In-Depth Information
Turing's carefully worked definition has withstood the test of time. Although dif-
ferent models of computation have been proposed (including a strikingly different
one by Alonzo Church), they have all been shown to be equivalent to Turing's. Every
computer built so far has been a special case of a Turing machine and subject to the
restrictions proved by Turing. The claim that this will be true of any physical computer
to be built is called the Church-Turing thesis [8].
Regarding thinking as computation, there is a superb though somewhat advanced
philosophical book on this subject by Pylyshyn [10]. Much of the argument presented
here about how actions are conditioned by what is known derives from this insightful
book. (In the terminology he uses, those actions are said to be cognitively penetrable.)
Outside of philosophy, there is a subarea of AI called knowledge representation and
reasoning that starts with the work of McCarthy and is concerned with the issue of
representing knowledge in symbolic form and devising computational procedures to
reason with it effectively. A graduate-level textbook on this area of research is by
Brachman and Levesque [1]. The state of the art in this research area is reviewed in a
(quite advanced) technical handbook [4].
Finally, although this topic concentrates on small knowledge bases, the CYC project
[7] is an example of a project whose goal is to build a large knowledge base along the
lines discussed here.
Exercise
Consider the procedure PROCX in figure 1.7. It assumes there are other procedures
elsewhere that will do some arithmetic (subtraction, multiplication, and less-than
comparisons). It also assumes that one can concatenate strings of digits: x ˆ y means
the string consisting of the digits in x followed by those in y . It works by repeatedly
setting new values to u , v , bot , top , and side as the digits of the input are worked
through in pairs from left to right.
Figure out what the procedure PROCX is doing. Hint: Trace its behavior when the
input is 137641 .
 
 
Search WWH ::




Custom Search