Subject: From: AIList Moderator Kenneth Laws <AIList-REQUEST@SRI-AI>

From: [email-masked]
Date: Tue, 21 May 85 06:37:11 edt

Received: from sri-ai.arpa by csnet-relay.arpa id aa18514; 21 May 85 2:59 EDT
Date: Mon 20 May 1985 23:32-PDT
Reply-to: AIList@SRI-AI
US-Mail: SRI Int., 333 Ravenswood Ave., Menlo Park, CA  94025
Phone: (415) 859-6467
Subject: AIList Digest   V3 #67
To: AIList@SRI-AI
Received: from rand-relay by vpi; Tue, 21 May 85 06:29 EST

AIList Digest            Tuesday, 21 May 1985      Volume 3 : Issue 67

Today's Topics:
  Query - Cooking Knowledge,
  Theory - Classes of Turing Machines,
  Games - Computer Cheating,
  Humor - Qualitative Calculator,
  Seminars - Constraint-Interpreting Reference (MIT) &
    Exceptions in Data/Knowledge Bases (LBL)

----------------------------------------------------------------------

Date: Mon, 20 May 85 14:41:54 -0200
From: [email-masked]
Subject: Cooking Knowledge

Doing research on collaboration between robot systems, we need to
implement knowledge about cooking. I've heard that long, long ago,
a group in San Diego worked on that, and that some Mrs. Cordier in
Paris has done research in that field.
Does anyone have more information on these, or on other projects
using cooking knowledge, or does someone have any ideas about the
subject which might be useful?

Thanks,
                                                          Biep.
        {seismo|decvax|philabs|garfield|okstate}!mcvax!vu44!klipper!biep

------------------------------

Date: Mon, 20 May 85 15:06 CDT
From: Patrick_Duff <[email-masked]>
Subject: RE: a "new" turing thesis

> From: Lydia Defilippo <[email-masked]>
> Subject: Seminar - A New "Turing" Thesis (CMU)
>
> ....  Turing machines are computational devices with unbounded resources.
> First, we adapt Turing's thesis to the case when only devices with bounded
> resources are considered.

    When I studied Turing machines in an AI course I took back in college,
this had already been done.  Here is a summary of the four types of Turing
Machines (with various bounds on the available resources), from my class
notes [if you have any corrections or additions, please send them to me]:

TYPE 3 TURING MACHINE:
   Description:
      1)  Tape has finite length;
      2)  Control unit has one read head and no write heads;
      3)  Read head is initially positioned at beginning of tape;
      4)  Read head cannot be moved backwards;
      5)  Control unit is deterministic;
      6)  Control unit has finite memory.
   Remarks:
      1)  Recognizes exactly all regular languages;
      2)  Making control unit non-deterministic does not increase power;
      3)  Equivalent to a finite-state automaton;
      4)  Able to decide whether a number is odd, compute the sum of two
          numbers, or decide whether a number is divisible by 3, for instance.

TYPE 2 TURING MACHINE:
   Description:
      1)  Tape has finite length;
      2)  Control unit has one read head and no write heads;
      3)  Read head is initially positioned at beginning of tape;
      4)  Read head cannot be moved backwards;
      5)  Control unit is deterministic;
      6)  Control unit has finite memory.
      7)  Control unit has a push-down stack.
   Remarks:
      1)  More powerful than TYPE 3;
      2)  Recognizes exactly all context free languages;
      3)  Making control unit non-deterministic does not increase power.
      4)  Ability to read any position in push-down stack would make it more
          powerful;
      5)  Letting read head move both ways adds power;
      6)  Letting head read and write adds power--more powerful than even
          without the push-down stack;
      7)  If a second push-down stack is added, it can do anything a TYPE 0
          can do;
      8)  Using a single counter instead of a push-down stack is more
          powerful than TYPE 3 but less powerful than TYPE 2 [could check
          for an arbitrary string of symbols on tape or see if parentheses
          are balanced, for instance].

TYPE 1 TURING MACHINE:
   Description:
      1)  Tape has finite length;
      2)  Control unit has one read/write head;
      3)  Read/write head is initially positioned at beginning of tape;
      4)  Read/write head can be moved both forwards and backwards;
      5)  Control unit is deterministic;
      6)  Control unit has finite memory.
   Remarks:
      1)  Recognizes context sensitive languages;
      2)  Also called a linear bounded automata;
      3)  Adding multiple tapes does not increase power;
      4)  It is not known whether a non-deterministic control unit increases
          power.

TYPE 0 TURING MACHINE:
   Description:
      1)  Tape has infinite length;
      2)  Control unit has one read/write head;
      3)  Read/write head is initially positioned somewhere on tape;
      4)  Read/write head can be moved both forwards and backwards;
      5)  Control unit is deterministic;
      6)  Control unit has finite memory.
   Remarks:
      1)  Adding multiple tapes does not increase power;
      2)  Adding multiple read/write heads does not increase power;
      3)  Adding push-down stack does not increase power;
      4)  Non-deterministic control unit does not increase power;
      5)  Infinite memory control unit does not increase power;
      6)  Able to determine whether a number is prime or whether a program
          has infinite loops, for instance;
      7)  Claimed to be "an adequate and complete model of processes
          that can be carried out mechanically (effective processes)"
          [Church-Turing thesis].

   regards, Patrick

   Patrick S. Duff, ***CR 5621***          pduff.ti-eg@csnet-relay
   5049 Walker Dr. #91103                  214/480-1659 (work)
   The Colony, TX 75056-1120               214/370-5363 (home)
   (a suburb of Dallas, TX)

------------------------------

Date: Tue, 21 May 85 00:46 EDT
From: Henry Lieberman <Henry@OZ>
Subject: Computers cheat at chess?

The chess columnist of the Boston Globe wrote an article claiming that computer
programs cheat in chess tournaments! He had two arguments for this:

 * Tournament rules forbid the players to use an extra board to move pieces
while considering their moves during the game. He argued that tree searching of
moves in computer programs constitutes using an extra board.

 * Tournament rules forbid the players to consult books during the game.
Most programs rely on a book to play openings.

These arguments seemed silly to me at first, but on reflection, I think he
might have a point, especially with the second point about book openings.
It might be worthwhile to try human-computer chess tournaments with relaxed
rules that, for example, permit the human to consult a book of openings, or
even better, the same on-line data base of openings that the program uses.

------------------------------

Date: Thu, 16 May 85 18:01:50 edt
From: Walter Hamscher <hamscher at mit-htvax>
Subject: Revolting Seminar - Qualitative Calculator

           [Forwarded from the MIT bboard by SASW@MIT-MC.]

DATE:   Friday, 17 May
TIME:   12 NOON
PLACE:  8th FLOOR PLAYROOM
HOST:   Michael Kashket

    QUALITATIVE CALCULATORS IN CLINICAL DECISION MAKING

                 (-:    Tex Tuftsman    :-)

The classical approach to decision analysis in medicine has been
based on constructing decision trees, giving numerical weights to
outcomes, and banging away at the keys of an ordinary 16-key
calculator to choose between appropriate therapies.  Some of the
weaknesses in this approach can be avoided by using a QUALITATIVE
CALCULATOR (c) from Ronco.

Envision yourself with a QUALITATIVE CALCULATOR (c) -- A QUALITATIVE
CALCULATOR especially designed for Naive Physicists.  Comes with [+],
[-], and [0] keys, plus a Clear key and a DeClear key.  Was $20.99,
marked down to [+].  But wait -- There's more!  Qual before [0] tonight
and get a free State Map for your locality.  Operators are standing by!
Don't miss this landmark value!

------------------------------

Date: Sun, 19 May 85 18:02 EDT
From: [email-masked]
Subject: Seminar - Constraint-Interpreting Reference (MIT)

                             AI REVOLVING SEMINAR

                          John Mallery (JCMa@MIT-MC)

                     "Constraint-Interpreting Reference"

                         Tuesday, May 21, 1985 at 4pm

                       8th Floor Playroom, AI Laboratory, MIT

        This talk will discuss the theory of reference used in the Relatus
Natural Language System, an AI program developed at the MIT AI Laboratory in
collaboration with Gavan Duffy.  Relatus parses sentences and uses a reference
system to incrementally construct a semantic model.  The reference system
matches graphs and creates (interns) graph structure in a semantic network.
The separation of the constraint interpreter from specific constraints
describing the matching problem yields various benefits.  For instance:

*  Matching speed is independent of database size, normally faster than linear
   in the size of the smallest accessible set of potential referents.

*  A powerful and extensible constraint language provides the ability to
   describe an infinite number of matchers, each tuned to recognize and prefer
   specific structures.

In addition to the theoretical ideas, some practical uses of the implemented
reference system will also be discussed:

*  It is regularly used in intersentential reference, finding references
   to previously interned descriptions in new sentences.  Relatus can
   presently parse and reference a 10-page text (250 sentences) in under
   10 minutes while running on a Symbolics 3600 (1536K real memory).

*  It is regularly used to answer literal and explicit questions.  The
   approach to question answering depends on both the reference system and a
   procedure which is actually the inverse of reference.  Semantic inversion
   builds constraint descriptions from the graph structure previously created
   by the reference system.

------------------------------

Date: Mon, 20 May 85 13:32:05 pdt
From: (Frank Olken [csam]) olken@lbl-csam
Subject: Seminar - Exceptions in Data/Knowledge Bases (LBL)

                      CSRD Colloquium
                Lawrence Berkeley Laboratory

 **********************************************************

       Living with Exceptions in Data/Knowledge Bases

 **********************************************************

                     Alexander Borgida
               Department of Computer Science
                     Rutgers University

The ``schema'' of a large database is usually used to  vali-
date  the  data  being  entered and to help set up efficient
access structures.  Because the  real  world  is  irregular,
unpredictable  and  evolves,  we  contend  that  useful data
management systems,  including  large  ``knowledge  bases,''
must  be tolerant of deviations from the constraints imposed
by the schema, including type and  semantic  integrity  con-
straints.  We   therefore  examine  the problems involved in
accommodating exceptions to constraints, and propose a solu-
tion  based on the concept of exception handling in Program-
ming Languages.  This technique can also  be  used  to  deal
with  problems  such  as  null  values and estimates, and in
addition has good Software Engineering properties.  We  con-
clude  by  discussing  the  formal  logic of assertions with
exceptions, and hint at the utility of exceptions  in  data-
base re-design through learning.

          Wednesday, May 22, 1985, 2:00pm - 4:00pm
           Bldg. 50D, Room 116 - Conference Room

For further information, call Harry Wong at (415) 486-6884.  Dept. of
Computer Science Research; LBL; One Cyclotron Road; Berkeley, CA
94720.

------------------------------

End of AIList Digest
********************