Copy Link
Add to Bookmark
Report
AIList Digest Volume 1 Issue 034
AIList Digest Monday, 8 Aug 1983 Volume 1 : Issue 34
Today's Topics:
Fifth Generation - Opinion,
Translation - Natural Language,
Computational Complexity - Parallelism,
LOGO - Request,
Lab Descriptions - USENET Sites,
Conferences - AAAI Panel to Honor Alexander Lerner
----------------------------------------------------------------------
Date: 5 Aug 83 20:14:19-PDT (Fri)
From: harpo!floyd!vax135!cornell!uw-beaver!ssc-vax!ditzel @ Ucb-Vax
Subject: Re: Japanese Effort
Article-I.D.: ssc-vax.377
Whereas it is true the Unites States holds a substantial lead in AI
over the Japanese, it really is beyond me how a person can believe
that they do not have the resources to overcome such a lead. In my
*opinion* some things make a possible Japanese lead in AI machines
possible. Like:
*It is a national effort with an attempt to coordinate goals. The fact
that the project will be a coordinated effort rather than various
incongruously related developments should facilitate compatibility
among the different topics.
*It may well be that Japan will have to go to the outside world to
make their project a success. What of it...a success is still a
success.
*In addition to believe that a priority project supported by both
government and industry will not try to encourage,educate and nurture
talented individuals toward the topics covered by the 5th generation
is not realistic.
*Worse yet, to believe such a project will not have an intense
political and social effect on Japan is also ignoring reality. If and
when successes in project goals do come, various segments of the
society and industrial sectors may begin to participate.
*The 5th generation project at least is visionary, a bit idealistic
and very ambitious. The outside 'egos' don't have an equivalent
project in the United States. (i.e.-one that has substantial backing
from industry and government *and* has fairly substantial financing
for the next five to ten years).
The point is we are very early into the project.... wait a bit.... we
may learn a thing or two if we are not energetic enough.
cld
------------------------------
Date: 5 Aug 83 14:50:43-PDT (Fri)
From: decvax!microsoft!uw-beaver!ssc-vax!sts @ Ucb-Vax
Subject: Re: Japanese Effort
Article-I.D.: ssc-vax.376
Concerning your lack of concern about the Japanese:
They may not have the manpower now, but they have been hiring outside
Japan and giving some pretty strong support to their researchers. I'd
go in a minute if they made me an offer...
stan the leprechaun hacker
ssc-vax!sts (soon utah-cs)
------------------------------
Date: 5 Aug 83 12:51:22-PDT (Fri)
From: decvax!linus!utzoo!watmath!echrzanowski @ Ucb-Vax
Subject: 5th generation computers
Article-I.D.: watmath.5613
I recently had an opportunity to show a visiting prof from the
University of Kyoto around our facilities. During one of our
conversations I asked him about the 5th generation computers in Japan.
His response was that it was only a large government promotional
campaign and nothing more. Sure they are building some new computers
but not to the degree that we are expected to believe.
If anyone else has any ideas or comments on 5th generation computers I
would like to see them.
(watmath)!echrzanowski
------------------------------
Date: 6 Aug 83 13:01:14-PDT (Sat)
From: decvax!genrad!mit-eddie!smh @ Ucb-Vax
Subject: Re: 5th generation computers
Article-I.D.: mit-eddie.551
About the professor from Kyoto who claimed that the 5th generation
project was only a big government promotional effort:
Maybe so, maybe not. Weren't there some similar gentlemen in
Washington making similar assurances about a different matter around 5
Dec 1948?
------------------------------
Date: Sat, 6 Aug 83 19:42 EDT
From: Tim Finin <Tim%UPenn@UDel-Relay>
Subject: natural language translation
... A real translator essentially reads and understands the
text in one language, and then generates the appropriate
text in the other language. Since understanding general
texts requires huge amounts of real-world knowledge,
unrestricted machine translation will arrive about the time
AI programs can pass the Turing test. In my opinion, this
will be substantially longer than ten years....
The long-standing machine translation project at the University of
Texas at Austin is not a system based on a deep understanding of the
text being translated yet has been giving good results in translating
technical manuals from German to English. Slocum reported on its
status in the ACL Conference on Applied Natural Language Processing
held in Santa Monica in February 83. In this case, good meant
requiring less post-translation editing than the output of human
translators.
------------------------------
Date: 6 Aug 83 11:09:57 EDT (Sat)
From: Craig Stanfill <craig%umcp-cs@UDel-Relay>
Subject: NP-completeness and parallelism
David Rogers commented that in parallel computing it makes sense to
assume a processor with an infinite number of processing elements,
much as a Turing machine has an infinite amount of memory. He then
goes on to suggest that this might allow the effective solution of
NP-hard problems.
If we do this, we need to consider the processor-complexity of our
algorithms, not just the time-complexity. For example, are there
algorithms for NP-hard problems which are linear in time but NP-hard
in the number of processors? I suspect this is the case.
Parallelism is not the solution to combinatorial explosions; it is
just as limiting to use 2**n processors as it to use 2**n time.
However, the speedup is probably worth the effort; I would rather work
with a computer that uses 64,000 processors for one second than one
which uses 1 processor for 64,000 seconds. Now, if we can just figure
out how to do this ...
------------------------------
Date: 7 Aug 83 16:57:17-PDT (Sun)
From: harpo!gummo!whuxlb!pyuxll!ech @ Ucb-Vax
Subject: Re: NP-completeness and parallelism
Article-I.D.: pyuxll.388
A couple of clarifications are in order here:
1. NP-completeness of a problem means, among other things, that the
best known algorithm for that problem has exponential
worst-case running time on a serial processor. That is not
intended as a technical definition, just an operational one.
Moreover, all NP-complete problems are related by the fact
that if a polynomial-time algorithm is ever discovered for
any of them, then there is a polynomial-time algorithm for
all, so the (highly oversimplified!) definition of
NP-complete, as of this date, is "intrinsically exponential."
2. Perhaps obvious, but I will say so anyway: n processors yoked in
parallel can't do better than to be n times faster than a
single serial processor. For some problems (e.g. sorting),
the speedup is less.
The bottom line is that the "biggest tractable problem" is
proportional to the log of the computing power at your disposal;
whether you increase the power by speeding up a serial processor or by
multiplying the number of processors is of small consequence.
Now for the silver lining. NP-complete problems often can be tweaked
slightly to yield "easy" problems; if you have an NP-complete problem
on your hands, go back and see if you can restrict it to a more
readily soluble problem.
Also, one can often restrict to a subproblem which, while it is still
NP-complete, has a heuristic which generates solutions which aren't
too far from optimal. An example of this is the Travelling Salesman
Problem. Several years ago Lewis, Rosencrantz, and Stearns at GE
Research described a heuristic that yielded solutions that were no
worse than twice the optimum if the graph obeyed the triangle
inequality (i.e. getting from A to C costs no more than going from A
to B, then B to C), a perfectly reasonable constraint. It seems to me
that the heuristic ran in O(n-squared) or O(n log n), but my memory
may be faulty; low-order polynomial in any case.
So: "think parallel" may or may not help. "Think heuristic" may help
a lot!
=Ned=
------------------------------
Date: 5 Aug 83 17:56:34-PDT (Fri)
From: harpo!eagle!allegra!jdd @ Ucb-Vax
Subject: LOGO wanted
Article-I.D.: allegra.1721
A colleague of mine is looking for an implementation of LOGO, or any
similar language, under UNIX (one that already ran on both Suns and
PDP-11/23's would be ideal, but fat chance of that, eh?). Failing
that, she would like to find a reasonably portable version (e.g., in
MacLisp). In any case, if you have suggestions, please send them to
me and I shall forward.
Cheers, John ("This Has Been A Public Service Announcement")
DeTreville Bell Labs
------------------------------
Date: 5 Aug 83 13:15:42-PDT (Fri)
From: decvax!linus!utzoo!utcsrgv!kramer @ Ucb-Vax
Subject: Re: USENET and AI
Article-I.D.: utcsrgv.1898
We at the University of Toronto have a strong AI group that has been
in action for years:
Area Major Project
Knowledge Representation PSN (procedural semantic network)
Databases and Knowledge TAXIS Representation
Vision ALVEN (left ventricular motion understanding)
Linguistics Speech acts
A major summary of our activities is being prepared to appear in the
magazine for AAAI at some point.
Our research is being done on VAXen under UNIX*. Presently at
utcsrgv, we will soon (September) be moving to a VAX dedicated to ai
work.
------------------------------
Date: 6 Aug 83 13:40:14-PDT (Sat)
From: ihnp4!houxm!hocda!spanky!burl!duke!unc!bts @ Ucb-Vax
Subject: More AI on USENET only
Article-I.D.: unc.5673
The Computer Science Department at UNC-Chapel Hill is another
site with (some) AI interests that is on USENET but not ARPANET. We
are one of CSNET's phone sites, but this still doesn't allow us to FTP
files. (Yes, in part, this is a plea for those folks who can FTP to
share with the rest of us on USENET!)
Our functional programming group has a couple of projects with
some AI overtones. We have begun to look at AI style programming
languages for Gyula Mago's string reduction tree-machine. This is a
small-grain parallel computer which executes Backus' FFP language.
We're also looking at automatic FP program transformations.
Along with our neighbors at Duke University, we have some Prolog
programmers. Right now, that's C-Prolog at UNC and NU7 UNIX Prolog at
Duke.
Bruce Smith, UNC-Chapel Hill
duke!unc!bts (USENET)
bts.unc@udel-relay (other NETworks)
------------------------------
Date: 5 Aug 83 15:11:37 EDT (Fri)
From: JACK MINKER <minker%umcp-cs@UDel-Relay>
Subject: AAAI Panel to Honor Alexander Lerner
In conjunction with the AAAI meeting in Washington, D.C. a
session is being held to honor the 70th birthday of the Soviet
cyberneticist, Professor Alexander Lerner. The session will be held
on:
Date: Tuesday, August 23, 1983
Time: 7:00 PM
Location: Georgetown Room, Concourse Level
The session will consist of a brief description of Dr.
Lerner's career, followed by a panel discussion on:
Future Directions in Artificial Intelligence
The following have agreed to be on the panel with me:
Nils Nilsson
John McCarthy
Patrick Winston
Others will be invited to participate in the panel session.
We hope that you will be able to join us to honor this
distinguished scientist.
Jack Minker
University of Maryland
------------------------------
End of AIList Digest
********************
