Recognizing Apples
|
In
this example the idea that a machine computes a function is illustrated
by creating a machine that computes an "apple function."
(I realize that the picture to the right has no apples but it
wasn't apple season when I was last at the market in Paris.)
That is, our goal is to create a machine that accepts descriptions
that satisfy our definition of an apple.
The recipe for creating this
example involves several steps:
- define the set of fruits that
are to be distinguished from apples;
- define a language for describing
fruits that will allow apples to be uniquely described;
- define a machine that will accept
descriptions of apples and only descriptions of apples.
|
|
|
Notice
that if we are going to recognize apples computationally (as
opposed to asking someone else if something is an apple or perhaps
intuiting applehood) we are forced to define an apple in some
language that we must concoct for the task. What are the various
fruits that we want to distinguish from apples? We have cherries,
apricots, and peaches in the above picture and perhaps we should
also include oranges, lemons, plums, and bananas along with apples.
The choice of the set of fruits that are to be considered will
guide our choice of language.....we simply need a language rich
enough to distinguish these fruits. Another possible way of developing
our "fruit language" would be to describe every aspect
of each of these fruits that we can think of or perceive. But
when we develop the apple acceptor machine, we will see that
a rich language only makes our task harder to accomplish.
The
language for defining fruits is given below. Note that four dimensions
are used where the shape, size and taste dimension can take on
any one of three different values but the color dimension has
five possible values.
|
|
These 14 possible values
define the vocabulary associated with the machine that we wish
to define; that is:
Sigma = { r,y,g,o,p,c,v,a,l,m,s,w,u,t
}
If fruits are always described
by first specifying the color, next shape, next size, and finally
taste; then the "language of apples" is the set of
strings:
L(apple) = {rcmw, rcmt, ycmw,
ycmt, gcmw, gcmt}
|
Language for Defining Fruits
|
Dimension |
Values |
| Color |
Red
(r), Yellow (y), Green (g), Orange (o) or Purple (p) |
| Shape |
Round
(c), Oval (v) or Arc (a) |
| Size |
Large
(l), Medium (m) or Small (s) |
| Taste |
Sweet
(w), Sour (u) or Tart (t) |
|
| With
this ordering restriction in place, a rather simple finite state
machine (FSM) can be defined to recognize this language
(or equivalently, compute this function). The Markov diagram
for such a machine is shown below. |
| |
|
|
| However,
the limitations of an FSM become quite apparent if we allow the
information regarding a fruit to be input in any arbitrary order.
In this case the language that must be recognized is much larger.
Each of the six strings in the ordered language above can appear
in any permutation. Thus, the cardinality of the language of
apples changes from 6 to 6 x 4! or 144 possible strings. This
isn't exactly disastrous but remember that there are 4! or 24
different permutations of the four dimensions used to define
an apple. A machine for another of these orderings is shown below.
In this machine the expected order is Color-Shape-Taste-Size.
I leave the remaining 22 machines to your imagination. And, while
you are imagining remember that we must compose these 24 machines
into a single machine that will respond appropriately to all
144 possible types of apples! |
| |
|
|
| Luckily
we can consider using a more powerful machine, namely a Turing
Machine(TM). It will be particularly useful here because the
TM allows the agent to determine the order in which to consider
the input. Recall that in an FSM the agent is required to deal
with the input in the order in which it appears on the tape.
There are essentially four subproblems that must be solved in
order to recognize whether or not the input describes an apple.
The four subproblems correspond to the four dimensions used to
define an apple. For each dimension the agent must determine
whether an "apple-appropriate" value appears on the
input tape; and that no inappropriate values are present. Notice
that the structuring of the language into these dimensions is
not explicit in the language. However, it will be explicitly
exploited in the TM shown below. |
 |
|
In this example the states
shown in yellow indicate the subgoals of determining first the
color, next the taste, next the
shape, and finally the size. The read head moves from the left-most
symbol on the tape and reads each symbol until it finds a valid
color for the apple. It then replaces this color with a % symbol
and moves to a state depicted in green. This state termed NTaste
accomplishes a "control" subgoal. It serves to move
the read head to the end of the input string and when the end
is reached, the direction is reversed and a valid taste is sought
in the input string. This basic pattern is followed until all
of the subgoals have been satisfied. The final subgoal is simply
to check that there is nothing left on the tape but blanks (#)
and % symbols. If this final subgoal is satisfied, then a 1 is
written on the tape to indicate that the input string satisfied
the definition for an apple and the TM halts. This TM would "hang"
on any input string that was not in our "apple language."
Recall
that it was claimed that the TM would take advantage of the structure
of the definition of an apple. The definition of an apple can
be stated as:
((r OR y OR g) AND (w OR t) AND
(c ) AND (m))
Note that the subgoals in the
TM above correspond to the conjuctive components of the definition.
The ability to decompose a problem into subproblems and to utilize
this decomposition in searching for a solution will figure importantly
in our computational study of intelligence.
There
are several things that I hope you take away from this example.
First, a language must be defined that is adequate for defining
the function that is to be computed. Second, although we could
have (with a great deal of patience) written an FSM to compute
this function; the power of the TM made the task much simpler.
And, perhaps just a importantly, we were able to define a TM
that reflected in some sense the structure of the problem.
|
|
