for
CSCI 301: Great Ideas in Computer Science
(c) 1993, 1994, 1995 John E. Howland, All Rights Reserved
Department of Computer Science
Trinity University
Stadium Drive
San Antonio, Texas 78212-7200
Internet: jhowland@ariel.cs.trinity.edu
Turing's test involves a room which encloses (hiding the identity of) a terminal which is operated by a human and a completely separate computer.
Outside the room, there are two identical terminals; one being attached to the terminal in such a manner so that someone sitting at the terminal outside the room could communicate with the hidden person sitting at the terminal inside the room, the second is attached to the computer inside the room. It is not known to test subjects which terminal is wired to the terminaly inside the room and which terminal is wired to the computer inside the room.
Turing's test is performed as follows: a test subject sits at the first terminal and communicates with the person or the computer about any subject he or she wishes. The subject next sits at the other terminal and again communicates with the person or the computer about a subject of his or her choosing. After these two conversations are completed, the subject attempts to identify which terminal is connected to the computer and which terminal is connected to the terminal operated by a human hidden in the room.
Turing hypothesized that it is reasonable to accept the possibility of an intelligent machine if a machine can be built which can reliably fool the average test subject's choice of which terminal is connected to the machine.
The mathematician, John Von Neuman, developer of the stored program architecture for a computer, studied this question. He proposed a theorem which stated that a machine could be built which was capable of constructing a replica of itself! His first proof of this theorem was a proof by contradiction. He assumed that such a machine wasn't possible and showed this assumption lead to a contradiction. Later, he gave a constructive proof of this same result. Needless to say, this result lead many to reasses their thinking about the roles of human beings in a world where ever more powerful computing machines are being designed and built.
In what way?
They're always bugging us about something or other.
Can you think of a specific example?
Well, my boyfriend made me come here.
Your boyfriend made you come here.
He says I'm depressed much of the time.
I am sorry to hear you are depressed.
It's true. I am unhappy
Do you think coming here will help you not to be unhappy?
I need some help, that much seems certain.
What would it mean to you if you got some help?
Perhaps I could learn to get along with my mother.
Tell me more about your family.
My mother takes care of me.
Who else in your family takes care of you?
My father.
Your father.
You are like my father in some ways.
What resemblance to you see?
You are not very aggressive but I think you don't want me to notice that.
What makes you think I am not very aggressive.
You don't argue with me.
Why do you think I don't argue with you?
You are afraid of me.
Does it please you to believe I am afraid of you?
My father is afraid of everybody.
What else comes to mind when you think of your father?
Bullies.
Does that have anything to do with the fact that your boyfriend made you come here?
The rather amazing Eliza program became rather famous quite quickly and many researchers in psychology and other related fields began derivative works on Eliza. For example, the psychologist Colby seriously believed that the Doctor script could grow into a nearly completely automatic form of psychotherapy.
Also, people, when conversing with Eliza, quickly seem to become emotionally involved with Eliza and quickly anthropomorphized Eliza. Finally, people began to believe that Weizenbaum had solved the problem of machine understanding of natural language.
Weizenbaum was very disturbed by these developments because he knew that Eliza had absolutely no understanding at all of what was input. Eliza simply transformed (admitedly in a clever manner) input sentences to response sentences using a script. Weizenbaum elaborates his thesis that computers cannot be programmed to be truely intelligent beings in his book Computer Power and Human Reason: From Judgement to Calculation.
Weizenbaum believes that science is creative, that the creative act in science is equivalent to the creative act in art, that creation springs only from autonomous individuals and that these ideas, while simple, should also be obvious.
In the early years, 1950's to 1980, there was considerable optimism about the possibility of constructing truly intelligent machines. However, in recent years this optimism has given way to a more pragmatic view that it may be possible to devise programs which know alot about a rather limited domain of knowledge and can be useful tools inconjunction with human intelligence to solve certain kinds of problems. Such systems are called expert systems. Experiments have been made to construct expert systems which are capable of medical diagnosis of certain kinds of illness, offer expert advice about certain kinds of business decisions, make decisions about where to drill for oil, play games such as checkers and chess, etc.
An association list, abreviated as alist, is a list of related pairs. For example,
(define ls '((a . 1) (b . 2) (c . 3)))defines a 3 element alist which pairs a and 1, b and 2, c and 3.
There is a built-in function, assoc, which searches alists.
(assoc 'b ls) ==> (b . 2) (assoc 'jack ls) ==> #fAlthough assoc is a built-in function in Scheme, it is useful to see how it could be implemented. Notice that it is very similar to the database lookup function we studied earlier.
(define assoc
(lambda (symbol alist)
(if (null? alist)
#f
(if (equal? symbol (caar alist))
(car alist)
(assoc symbol (cdr alist))))))
If
we have two lists which have the same number of elements it is convenient to be
able to easily construct an alist. The function pairlis accomplishes
this.
(define pairlis
(lambda (ls1 ls2)
(if (null? ls1)
'()
(cons (cons (car ls1)
(car ls2))
(pairlis (cdr ls1)
(cdr ls2))))))
(pairlis '(a b c) '(1 2 3)) ==> ((a . 1) (b . 2) (c . 3))
Of
course, the items used in alists may be arbitrary Scheme items.
(put 'jack 'name "John Howland")defines the name property for the symbol jack to be "John Howland". Similarly,
(put 'jack 'height 76)defines the height property for the symbol jack to be 76. Also,
(put 'jack 'age 52)defines an age property for the symbol jack to be 52. Property values may be retrieved useing the get function. For example:
(get 'jack 'height) ==> 76Here are some other property definitions.
(put 'glynne 'name "Glynne Howland") (put 'glynne 'age '?) (put 'glynne 'spouse 'jack) (put 'jack 'spouse 'glynne) (get 'glynne 'age) ==> ? (get (get 'glynne 'spouse) 'age) ==> 52The verb symbol-plist returns an alist of all the properties defined for a given symbol.
(symbol-plist 'jack) ==> ((spouse . glynne) (height . 76) (age . 52) (name . "John Howland")) (symbol-plist 'glynne) ==> ((spouse . jack) (age . ?) (name . "Glynne Howland"))As we have seen in Chapter 6, Data Structures, compound lists may be used to represent tree structures. For example,
(define tree '(((a b) (c d)) ((e f) (g h))))defines a tree structure similar to the diagram:
The root of tree is the top node in diagram 14.2.5. The leaves of tree are the symbols a, b, ... h. We can define a verb, display-leaves, which will "walk" through the entire tree structure and display all of the leaves of tree.
(define display-leaves
(lambda (tree)
(if (null? tree)
#t
(if (pair? tree)
(begin (display-leaves (car tree))
(display-leaves (cdr tree)))
(begin (display tree)
(newline))))))
(display-leaves tree) ==>
a
b
c
d
e
f
g
h
#t
The
last #t is the result returned by display-leaves. The
important thing to note here is that every leaf node of tree is
"visited" by this walk through. Rather than displaying leaf nodes as they are
encountered, some other operation, of course, could be performed. If we
"walked" down the right branch before the left branch each leaf would still be
encountered, but the visitation order would be different as illustrated below.
(define display-leaves1
(lambda (tree)
(if (null? tree)
#t
(if (pair? tree)
(begin (display-leaves1 (cdr tree))
(display-leaves1 (car tree)))
(begin (display tree)
(newline))))))
(display-leaves1 tree) ==>
h
g
f
e
d
c
b
a
#f
The memory model hypothesizes that memories of objects in the real world are organized into some sort of tree like hierarchy such as Figure 14.2.5. At the bottom of the hierarchy are all of the objects in memory. Each of these objects has a set of particular attributes which distinguish each object from other similar objects. For example, you can distinguish your mother from Queen Elizabeth II by the attributes associated with each.
Whenever we have two or more leaf nodes which are descendants of the same class of object, any attributes which they share in common should be separated from the leaf objects and associated with the containing node. Those attributes which are unique to leaves remain at that level in the hierarchy and serve to distinguish one leaf node from another leaf node. Notice that there are no real-world objects corresponding to any nodes in the tree except the leaf nodes. All other nodes represent classes of objects. We next explore these concepts with a simple example.
(define *tree*
'(root
(physical-entity
(living-thing
(carnivore
(human
(woman (mother queen-elizabeth))
(man (father prince-philip))))))))
This
tree structure is shown in the diagram
The process of collecting common attributes (abstracting) at the leaf level and moving them up one level continues at all levels. For example, any attributes which are shared by men and women should be moved up to the human level, etc. This process should continue all the way up to the top of the tree.
The links in Diagram 14.3.2 represent the relationship "is a". We can use the property list system to assign the attributes at each level of this hierarchy.
(put 'physical-entity 'isa 'root) (put 'living-thing 'isa 'physical-entity) (put 'carnivore 'isa 'living-thing) (put 'human 'isa 'carnivore) (put 'woman 'isa 'human) (put 'man 'isa 'human) (put 'queen-elizabeth 'isa 'woman) (put 'prince-philip 'isa 'man) (put 'mother 'isa 'woman) (put 'father 'isa 'man)Some additional attributes:
(put 'carnivore 'eats 'meat) (put 'human 'contains 'soul)The isa property is used to indicate the parent node of any give node in the tree diagram. This will allow us to search back up the tree from any given leaf node. The following remember function will allow us to perform such searches.
(define remember
(lambda (node property value)
(cond
((eq? node 'root) 'no)
((equal? (get node property) value)
'yes)
(else
(remember (get node 'isa) property value)))))
(remember 'mother 'isa 'woman) ==> yes
(remember 'mother 'contains 'soul) ==> yes
(remember 'mother 'eats 'meat) ==> yes
(remember 'father 'isa 'man) ==> yes
(remember 'mother 'isa 'man) ==> no
(<rule-name> <antecedent-ls-1> <antecedent-ls-2> ... <antecedent-ls-n> ==> <consequent-ls>)Each antecedent-ls is a list of items and the consequent-ls is also a list of items. The meaning of a rule is determined as follows. A working memory contains all known facts at any given time. Each fact is simply a list of items. The rule interpreter looks at a rule. If each of the antecedent facts is in working memory, then the rule interpreter adds the consequent fact to the working memory; otherwise the rule interpreter continues by interpreting another rule. The rule interpreter is said to fire a rule if all of the rule's antecedent facts are in working memory. The result of firing a rule is to add its consequent fact to working memory.
A rule set is a list of rules
(<rule1> <rule2> ... <rulem>)Following is a rule set which the President of the United States or the President of Russia might use concerning nuclear threats.
(define first
'((rule-f (red light)
(president awake)
(chiefs summoned)
(hotline used)
(worldwide red alert)
(button pushed)
==>
(%%halt%%))
(rule-e (red light)
(president awake)
(chiefs summoned)
(hotline used)
(worldwide red alert)
==>
(button pushed))
(rule-d (red light)
(president awake)
(chiefs summoned)
(hotline used)
==>
(worldwide red alert))
(rule-c (red light)
(president awake)
(chiefs summoned)
==>
(hotline used))
(rule-b (red light)
(president awake)
==>
(chiefs summoned))
(rule-a (red light)
==>
(president awake))))
The
Scheme property list functions, get and put, are used to
separate the rules into their antecedent and consequent parts and are attached
to the rule-name symbol as 'antecedent and 'consequent
properties. You will need to use the set-up-rules function to set up
a rules database. The following functions are already entered into the
rules.scm file which you have loaded.
; set-up-rules
(define set-up-rules
(lambda (ruleset-name rules)
(store-ruleset
(map (lambda (rule)
(store-rule (antecedent-part-of rule)
(consequent-part-of rule)
(name-part-of rule)))
rules)
ruleset-name)))
; store-ruleset
(define store-ruleset
(lambda (ruleset ruleset-name)
(put *rules* ruleset-name ruleset)))
; store-rule
(define store-rule
(lambda (antecedent consequent rule-name)
(put rule-name 'consequent consequent)
(put rule-name 'antecedent antecedent)
rule-name))
; antecedent-part-of
(define antecedent-part-of
(lambda (rule)
(define list-head
(lambda (ls k)
(if (or
(null? ls)
(zero? k))
'()
(cons (car ls)
(list-head (cdr ls) (- k 1))))))
(let ((r (cdr rule)))
(list-head r (- (length r) 2)))))
; consequent-part-of
(define consequent-part-of
(lambda (rule)
(if (pair? (cdr rule))
(consequent-part-of (cdr rule))
rule)))
; name-part-of
(define name-part-of
(lambda (rule)
(car rule)))
To
set up the rule set database enter the following Scheme sentence:
(set-up-rules 'first first)
; ps
(define ps
(lambda (ruleset working-memory goal)
(set! *working-memory* working-memory)
(set! ruleset (get *rules* ruleset))
(production-system ruleset goal)))
; the production-system rule interpreter
(define production-system
(lambda (ruleset goal)
(let ((fired-rule? #t))
(if (or
(halt-signaled?)
(goal-achieved? goal)
(not fired-rule?))
(begin
(writeln "Rule Interpreter Halted")
(cond
((halt-signaled?) (writeln "Halt Signaled"))
((goal-achieved? goal) (writeln "Goal " goal " Achieved"))
((not fired-rule?) (writeln "No Rules Fired")))
(writeln "Final Contents of Working Memory")
(display *working-memory*))
(begin
(set! fired-rule? (fire-rule (find-rule-to-fire ruleset)))
(production-system ruleset goal))))))
; halt-signaled?
(define halt-signaled?
(lambda ()
(member '(%%halt%%) *working-memory*)))
; goal-achieved?
(define goal-achieved?
(lambda (goal)
(member goal *working-memory*)))
; fire-rule
(define fire-rule
(lambda (rule)
(if rule
(begin
(set! *working-memory*
(append (consequent rule)
*working-memory*))
(if *verbose*
(writeln "Rule: "
rule
" fired, "
(consequent rule)
" put in working memory.")
#f)
rule)
#f)))
; consequent
(define consequent
(lambda (rule)
(get rule 'consequent)))
; find-rule-to-fire
(define find-rule-to-fire
(lambda (ruleset)
(cond
((null? ruleset) #f)
((recognize-rule (car ruleset)))
(else (find-rule-to-fire (cdr ruleset))))))
; recognize-rule
(define recognize-rule
(lambda (rule)
(if (match-antecedent (antecedent rule))
rule
#f)))
; antecedent
(define antecedent
(lambda (rule)
(get rule 'antecedent)))
; match-antecedent
(define match-antecedent
(lambda (antecedent)
(cond
((null? antecedent) #t)
((match-conjunct-with-working-memory (car antecedent))
(match-antecedent (cdr antecedent)))
(else #f)))) ; the else case should never be taken
; match-conjunct-with-working-memory
(define match-conjunct-with-working-memory
(lambda (conjunct)
(match* conjunct *working-memory*)))
; match*
(define match*
(lambda (pattern patterns)
(cond
((null? patterns) #f)
((match pattern (car patterns)) #t)
(else (match* pattern (cdr patterns))))))
; match
(define match equal?)
(symbol-plist 'rule-a) (get 'rule-a 'antecedent) (get 'rule-a 'consequent) (symbol-plist 'rule-b) (get 'rule-b 'antecedent) (get 'rule-b 'consequent) (symbol-plist 'rule-c) (get 'rule-c 'antecedent) (get 'rule-c 'consequent) (symbol-plist 'rule-e) (symbol-plist 'rule-e) (symbol-plist 'rule-f) (symbol-plist 'first) (symbol-plist *rules*) (get *rules* 'first)etc.
Next you should execute the rule system, starting with the fact '(red light), and try to achieve the goal '(green light). Do this by entering:
(ps 'first '((red light)) '(green light))Next change the consequent of rule-e by entering:
(put 'rule-e 'consequent '((green light)))and execute:
(ps 'first '((red light)) '(green light))Repeat the above experiments after tracing some of the matching programs. For example, you might start with:
(trace recognize-rule)Remember that after changing the consequent of rule-e you need to rebuild the rule database before re-doing the tracing phases of the experiment.