LAWS@SRI-AI.ARPA (05/21/85)
From: AIList Moderator Kenneth Laws <AIList-REQUEST@SRI-AI>
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: mcvax!vu44!klipper!biep@seismo.ARPA
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 <pduff%ti-eg.csnet@csnet-relay.arpa>
Subject: RE: a "new" turing thesis
> From: Lydia Defilippo <DEFILIPPO@CMU-CS-C.ARPA>
> 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: jcma@MIT-MC.ARPA
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
********************