Copy Link
Add to Bookmark
Report
AIList Digest Volume 1 Issue 039
AIList Digest Friday, 12 Aug 1983 Volume 1 : Issue 39
Today's Topics:
Textnet - Publish Adventure,
Representation - Current Adequacy,
Computational Complexity - NP-Completeness & FFP Machine,
Programming Languages - Functional Programming,
Fifth Generation - Opinion & Pearl Harbor Correction,
Programming Languages & Humor - Comment
----------------------------------------------------------------------
Date: 11-Aug-83 13:52 PDT
From: Kirk Kelley <KIRK.TYM@OFFICE-2>
Subject: Re: Textnet
I have spent most spare minutes for the last ten years designing a
distributed hyper-service using NLS and Augment as a development tool.
We can simulate, via electronic mail, the beginnings of a
self-descriptive service-service called the "Publish adventure". The
Xanadu project's Hypertext, because of its devotion to static text, is
a degenerate case of the Publish adventure. If you are interested in
collaborating on the design of the protocol, let me know.
-- Kirk Kelley
------------------------------
Date: 10 Aug 83 16:36:29-PDT (Wed)
From: harpo!floyd!vax135!cornell!uw-beaver!ssc-vax!sts @ Ucb-Vax
Subject: A Real AI Topic
Article-I.D.: ssc-vax.398
First let me get in a one last (?) remark about where the Japanese are
in AI - pattern recognition and robotics are useful but marginal in
the AI world. Some of the pattern recognition work seems to be making
the same conclusions now that real AI workers made ten years ago
(those who don't know history are doomed to repeat it!).
Now on to the good stuff. I have been thinking about knowledge
representation (KR) recently and made some interesting (to me, anyway)
observations.
1. Certain KRs tend to show up again and again, though perhaps in
well-disguised forms.
2. All the existing KRs can be cast into something like an
attribute-value representation.
Space does not permit going into all the details, but as an example,
the PHRAN language analyzer from Berkeley is actually a specialized
production rule system, although its origins were elsewhere (in
parsers using demons). Semantic nets are considered obsolete and ad
hoc, but predicate logic reps end up looking an awful lot like a net
(so does a sizeable frame system). A production rule has two
attributes: the condition and the action. Object-oriented programming
(smalltalk and flavors) uses the concept of attributes (instance
variables) attached to objects. There are other examples.
Question: is there something fundamentally important and inescapable
about attribute-value pairs attached to symbols? (ordinary program
code is a representation of knowledge, but doesn't look like av-pairs
- is it a valid counterexample?)
What other possible KRs are there?
Certain KRs (such as RLL (which is really a very interesting system))
claim to be universal and capable of representing anything. Are there
any particularly difficult concepts that *no* KR has been able to
represent (even in a crude way)? What is so difficult about those
concepts, if any such exist?
Just stirring up the mud,
stan the leprechaun hacker
ssc-vax!sts (soon utah-cs)
[I believe that planning systems still have difficulties in
representing continuous time, hypothetical worlds, beliefs, and
intentions, among other things. In vision, robotics, geology, and
medicine, there are difficulties in representing shape, texture, and
spatial relationships. Attribute-value pairs are just not very
useful for representing continuous quantities. -- KIL]
------------------------------
Date: Mon 8 Aug 83 17:19:42-PDT
From: David Rogers <DRogers@SUMEX-AIM.ARPA>
Subject: NP-completeness
I forward this message because it raises an interesting point, and
I thought readers may care to see it. I had a reply to this, but
perhaps someone else may care to comment.
Date: Sun, 7 Aug 83 18:28:09 CDT
From: Mike.Caplinger <mike.rice@Rand-Relay>
Claiming that a parallel machine makes NP-complete problems
polynomial (given that the machine has an infinite number of
processing elements) is certainly true (by the definition of
NP-completeness), but meaningless. Admittedly, a large number of
processing elements might make a finitely-bounded algorithm faster,
but any finitely-bounded algorithm is a constant time algorithm.
(If I say N is never greater than the number of processors, then N
might as well be a constant.)
------------------------------
Date: 10 Aug 83 13:19:32-PDT (Wed)
From: ihnp4!we13!burl!duke!unc!koala @ Ucb-Vax
Subject: Matrix Multiplication on the FFP Machine
Article-I.D.: unc.5687
Since the subject has been brought up, I felt I should clear
up some of the statements about the FFP machine. The machine consists
of a linear vector of small processors which communicate by being
connected as the leaves of a binary tree.
Roughly speaking, the FFP machine performs general matrix
multiplication in O(nxn) space and time. Systolic arrays can multiply
matrices in O(n) time, but do not provide a flexibility in the size of
matrices that can be handled.
Order notation only presents half the picture - in real life,
constant factors and other terms are also important. The machine's
matrix multiply operation examines each element of the two matrices
once. Multiplying two matrices, mxn and nxp, requires accessing (mxn
+ nxp) values, and this is the measure of the time for the
computation. Each cell performs n multiplications, dominated by the
access. Further, when you multiply two matrices, mxn and nxp, the
result is of size mxp. (Consider multiplying a column by a row).
Thus, when n < (mxp)/(m+p), extra space must be allocated for the
result. This is also a quadratic time operation.
David Middleton
UNC Chapel Hill
decvax!duke!unc!koala
------------------------------
Date: 11 Aug 83 16:23:19-PDT (Thu)
From: harpo!gummo!whuxlb!floyd!vax135!cornell!uw-beaver!ssc-vax!sts@Ucb-Vax
Subject: Re: Matrix Multiplication on the FFP Machine
Article-I.D.: ssc-vax.406
I must admit to being a little sloppy when giving the maximum speed of
a matrix multiplication on an FFP machine (haven't worked on this
stuff for a year, and my memory is slipping). I still stand by the
original statement, however. The *maximum* possible speed for the
multiplication of two nxn matrices is O(log n). What I should have
done is state that the machine architecture is completely unspecified.
I am not convinced that the Mago tree machine is the ultimate in FFP
designs, although it is very interesting. The achievement of O(log n)
requires several things. Let me enumerate. First, assume that the
matrix elements are already distributed to their processors. Second,
assume that a single processor can quickly distribute a value to
arbitrarily many processors (easy: put it on the bus (buss? :-} ) and
let the processors all go through a read cycle simultaneously).
Third, assume that the processors can communicate in such a way that
addition of n numbers can be performed in log n time (by adding pairs,
then pairs of pairs, etc). Then the distribution of values takes
constant time, the multiplications are all done simultaneously and so
take constant time, leaving only the summation to slow things down. I
know this is fast and loose; its main failing is that it assumes the
availability of an extraordinarily high number of communication paths
(the exact number is left as an exercise for the reader).
stan the leprechaun hacker
ssc-vax!sts (soon utah-cs)
ps For those not familiar with FP, read J. Backus' Turing Lecture in
CACM (Aug 78, I believe) - it is very readable, also he gives a
one-liner for matrix multiplication in FP, which I used as a basis for
the timing hackery above
------------------------------
Date: 11 Aug 83 19:32:18-PDT (Thu)
From: harpo!floyd!vax135!cornell!uw-beaver!ssc-vax!sts @ Ucb-Vax
Subject: Functional Programming and AI
Article-I.D.: ssc-vax.408
It is interesting that the subject of FP (an old interest of mine) has
arisen in the AI newsgroup (no this is not an "appropriate newsgroup"
flame). Having worked with both AI and FP languages, it seems to me
that the two are diametrically opposed to one another. The ultimate
goal of functional programming language research is to produce a
language that is as clean and free of side effects as possible; one
whose semantic definition fits on a single side of an 8 1/2 x 11 sheet
of paper (and not in microform, smart-aleck!). On the other hand, the
goal of AI research (at least in the AI language area) is to produce
languages that can effectively work with as tangled and complicated
representations of knowledge as possible. Languages for semantic
nets, frames, production systems, etc, all have this character.
Formal definitions are at best difficult, and sometimes impossible
(aside: could this be proved for any specific knowledge rep?). Now
between the Japanese 5th generation project (and the US response) and
the various projects to build non-vonNeumann machines using FP, it
looks to me like the seeds of a controversy over the best way to do
programming. Should we be using FP languages or AI languages? We
can't have it both ways, right? Or can we?
stan the leprechaun hacker
ssc-vax!sts (soon utah-cs)
------------------------------
Date: Mon 8 Aug 83 13:58:36-PDT
From: Robert Amsler <AMSLER@SRI-AI.ARPA>
Subject: Japanese 5th Generation Effort
It seems to me that the 5th generation effort differs from most
efforts we are familiar with in being strictly top-down. That is to
say, the Japanese are willing to start work not only without knowing
how to solve the nitty-gritty problems at the bottom--but without
knowing what those nitty-gritty problems actually are. Although
dangerous, this is a very powerful research strategy. Until it gets
bogged down due to an almost insurmountable number of unsolvable
technical problems one can expect very rapid progress indeed. When it
does get bogged down, their understanding of the problems will be as
great as that of anyone else in the world. The best way to learn is by
doing.
------------------------------
Date: 9-AUG-1983 15:24
From: SHRAGER%CMU-PSY-A@CMU-CS-PT
Subject: On Science and the Fifth Generation
I'm a little confused about why this Japanese business seems to be
scaring the pants off of the US research community; why scientists are
quoted in national news magazines as being "panic stricken", and why
terms like "race" and "ahead" are being thrown around in a community
of "scientists"; why anyone cares if the fifth generation thing is
propoganda or not. You'll find out when they make it work or they
don't!
Science is a cooperative effort. If Japan wants to jump forward
(note, not "ahead" in any sense) in technology and understanding it is
the position of every other scientist to applaud their boldness and
provide every ounce of critical advice we can give them. So what if
symbolics goes bankrupt becuase Japan makes a machine that makes the
3600 look like an Apple!? It will probably cost one third as much and
I'll be able to have one on my desk to further my research efforts.
Likewise, whatever the Japanese research community learns will
certainly benefit my research, even if just by learning what roads are
not fruitful.
Worry about the arms race, not the computer race! Work as hard as you
can to further science and technology, not to beat the Japanese! Work
toward the Nth generation, not the fifth or the sixth or the
seventh.... A little competition is probably useful sometimes, but
not to the detrement of the community spirit of science. If we start
hiding things from one another, do we have the right to call ourselves
scientists?
When I begin to worry is when Japan decides to build a better MX
missle, not a better computer system. Then issues of scientific
morals are involved and it's a whole 'nother ballgame.
------------------------------
Date: 9 Aug 83 21:04:30-PDT (Tue)
From: decvax!microsoft!uw-beaver!ssc-vax!tjj @ Ucb-Vax
Subject: Re: Pearl Harbor Day
Article-I.D.: ssc-vax.393
OK folks, especially those of you from various parts of tektronix-land
who don't seem to have access to or have interest in reading a history
book, let's review the bidding for your edification at least. A very
unsavory reference was made in the context of a remark from a
present-day visiting professor from Japan regarding the Japanese Fifth
Generation Project. The first bid for a date was 5 Dec 1948. This
was changed by the same author after he received at least one
electronic mail reply to 5 Dec 1945! This may have been with
tongue-in-cheek, as I know that he was given the correct date at least
once prior to his second message. It's a matter of record that the
Japanese Ambassador was instructed to visit the Secretary of State on
Friday, December 5, 1941. Whether he or his representative were again
doing so on Sunday, December 7, 1941 is a moot point, as I am certain
that they were very busy at the old trash incinerator that morning.
Although we should not forget history, lest we be doomed to repeat it,
I do think that comparison of this episode with the present day 5th
Generation Project, even in the context of the devastation of Detroit,
is stretching things beyond the breaking point. If you want to flame,
send mail to me, as I already have my asbestos suit on, but let's
graduate net.ai back to something more appropriate and certainly more
interesting.
TJ (with Amazing Grace) The Piper ssc-vax!tjj
------------------------------
Date: 10 Aug 83 12:02:09-PDT (Wed)
From: teklabs!done @ Ucb-Vax
Subject: Re: 5th generation computers
Article-I.D.: teklabs.2322
<flame on>
I can't stand this any longer:
"YESTERDAY, DECEMBER 7, 1941; A DATE WHICH WILL LIVE IN INFAMY!"
Carefully memorize this date and PLEASE DON'T SCREW IT UP AGAIN. Or
maybe infamy needs to be expressed in binary for you Computer Science
folks.
<flame off>
Don Ellis | USENET: {aat,cbosg,decvax,harpo,ihnss,orstcs,pur-ee,ssc-vax
Tektronix | ucbvax,unc,zehntel,ogcvax,reed} !teklabs!done
Oregon, USA | ARPAnet: done.tek@rand-relay CSNet: done@tek
------------------------------
Date: 10 Aug 1983 1244-EDT
From: MONTALVO%MIT-OZ@MIT-ML
Subject: Re: HFELISP
Date: 27 Jul 1983 0942-PDT
From: Jay <JAY@USC-ECLC>
Subject: HFELISP
HFELISP (Heffer Lisp) HUMAN FACTOR ENGINEERED LISP
ABSTRACT
HFE sugests that the more complicated features of (common) Lisp
are dangerous, and hard to understand. As a result a number of
Fortran, Cobol, and 370 assembler programmers got together with a
housewife. ...
How dare you malign the good sense of housewives by classing them with
Fortran, Cobol, and 370 assembler programmers!
Fanya Montalvo
------------------------------
End of AIList Digest
********************
