LAWS@SRI-AI.ARPA (06/06/85)
From: AIList Moderator Kenneth Laws <AIList-REQUEST@SRI-AI> AIList Digest Thursday, 6 Jun 1985 Volume 3 : Issue 74 Today's Topics: Games - Scrabble References, Terminology - MMI/HMI, Automata - Size of Self-Reproducing Systems, Report - Computational Natural Language, Bibliography - Recent Literature ---------------------------------------------------------------------- Date: Mon, 3 Jun 85 09:31:54 edt From: "William J. Rapaport" <rapaport%buffalo.csnet@csnet-relay.arpa> Subject: scrabble reference What is the state of the art in computer Scrabble? What work has been done? References? Software? Anecdotal remarks? Here's one reference that I know about: Shapiro, Stuart C., "A Scrabble Crossword Game Playing Program," IJCAI-79, Vol. Two, pp. 797-99. William J. Rapaport Assistant Professor Dept. of Computer Science, SUNY Buffalo, Buffalo, NY 14260 (716) 636-3193 uucp: ...{rocksvax|decvax}!sunybcs!rapaport csnet/arpanet: rapaport%buffalo@csnet-relay ------------------------------ Date: Mon, 3 Jun 85 09:55:47 edt From: "Stuart C. Shapiro" <shapiro%buffalo.csnet@csnet-relay.arpa> Subject: scrabble reference There are two papers on SCRABBLE in the book, Computer Game-Playing: Theory and Practice, edited by M.A. Bramer, Ellis Horwood Ltd (distributed in the U.S. by Halsted Press, a division of John Wiley & Sons), 1983: A competitive Scrabble program, by P.J. Turcan, pp. 209-220 Scrabble crossword game-playing programs, by S.C. Shapiro, pp. 221-228 ------------------------------ Date: 6 June 1985 0912-PDT (Thursday) From: gross@nprdc (Michelle Gross) Subject: MMI/HMI Ron Jacob-- List "man-machine interaction" as "human-machine interaction," or HMI. This is how the field is referred to by people at the university that I attend. Some link should be made between the two names. --Michelle Gross ------------------------------ Date: Mon, 03 Jun 85 07:39:55 EDT From: cugini@NBS-VMS Subject: size of self-reproducing system; intelligence? > Q: What's the minimum "size" for a self-reproducing thing? > For an "intelligent" thing?? > A measure of "size" probably needs to include the complexity of the > environment ... for instance, a virus takes advantage of a highly-ordered > set of cell mechanisms and can reproduce with only a few thousand (or so?) > bits of information ... its "size" measure should be bigger than the amount > of DNA in it might seem to imply. All living creatures make use of some > of the physical laws of the universe (mostly chemistry), and should be > charged some for that in "size" measure ... > Self-reproducing cellular automata that I've heard of seem to > generally require billions and billions of cells or so (as in > Conway's LIFE); they live in a very simple universe, where there is almost > no information stored in their environment. On the other hand, most of > the self-reproducing automata I've seen are quite huge and inefficient, > because they're structured to be comprehensible to people.... I recently ran across a new book, "The Recursive Universe" by William Poundstone that covers a lot of these issues. It's written in a somewhat gee-whiz style, but there's a lot of good information, especially for Life aficianados. Anyway, according to the book: Von Neumann could have allowed a distinct cellular state for every possible component of a machine. The fewer the states, the simpler the physics, however. After some juggling, he settled on a cellular array with 29 different states for its cells...The [next] state of a cell...depends only on its state and the states of its...neighbors.... What Von Neumann did is this: he proved that there are starting patterns that can reproduce themselves...Von Neumann's pattern, or machine reproduced in a very powerful way. It contained a complete description of its own organization. It used that information to build a new copy of itself. Von Neumann's machine reproduction was more akin to the reproduction of living organisms than to the growth of crystals, for instance. Von Neumann's suspicion that a self-reproducing machine would have to be complicated was right. Even in his simplified checkerboard universe, a self-reproducing pattern required about 200,000 squares. > Are the questions of self-reproduction and intelligence related? I'm > thinking vaguely about notions of Godel's theorem, complexity of human > brains, self-reference, etc. > > This might have interesting implications as to how hard it will be to make > AI systems with human-like consciousness ... how many logic elements or gates > will be required, how many gigaflops (or gigalips) are needed to think at a > human pace, etc.... > -zim@mitre My feeling is that many people are too ready to assume self-reference= intelligence=consciousness, eg Hofstadter's "Godel, Escher, Bach" and/or "The Mind's I". Von Neumann's machine seems self-referential enough, but not too bright, and hardly conscious. I assume that dogs, cats, birds, lizards...?? are conscious (feel pain, have visual experience,..) but some of them aren't too bright either. I say this knowing that they perform complex tasks such as nest-building, but I don't believe that such performance is prima facie evidence for intelligence, in that intelligence should include some notion of a *general* ability to deal with abstract problem representation (calculators can do trig functions, but they're not intelligent). John Cugini <Cugini@NBS-VMS> National Bureau of Standards Bldg 225 Room A-265 Gaithersburg, MD 20899 phone: (301) 921-2431 ------------------------------ Date: Tuesday, 4 Jun 1985 10:16:06-PDT From: billmers%rayna.DEC@decwrl.ARPA (Meyer Billmers) Subject: Re: size of self-reproducing system; intelligence? > Q: What's the minimum "size" for a self-reproducing thing? For an >"intelligent" thing?? ... >the self-reproducing automata I've seen are quite huge and inefficient, >because they're structured to be comprehensible to people.... I'm not sure I agree. For straightforward replication, it has been shown (Fredkin, Winograd, and others) to be easy. For example, in a 2-D cellular automaton, if the states are 0 and 1 and if the result state is computed by taking the sum of the neighbors modulo 2, then any initial configuration will replicate forever. It could be argued that this doesn't count as "self-reproducing" because there is no agent which "intentionally" reproduces itself (whatever that means). But Banks (MIT MAC TR-81, Jan. 1971) showed that a 4 state, 5 neighbor 2-D cellular automaton could be constructed which was a) a universal computer, e.g. given the correct encoding of a function, could compute any function, and b) a universal constructor, e.g. could "build" another configuration in the space which would then be capable of computing any function. a) and b) taken together imply a self-reproducing automaton which certainly displays some degree of intentionality. And it doesn't seem to require even millions of cells; indeed, Banks outlines its construction as an appendix of about 10 pages (although he doesn't actually display the entire beast). Hope that helps. -Meyer ------------------------------ Date: Wed 5 Jun 85 16:59:26-PDT From: Emma Pease <Emma@SU-CSLI.ARPA> Subject: Report on Natural Language [Excerpted from the CSLI Newsletter by Laws@SRI-AI.] Report No. CSLI-85-24, ``Computationally Relevant Properties of Natural Languages and Their Grammar'' by Gerald Gazdar and Geoffrey K. Pullum, has just been published. This report may be obtained by writing to David Brown, CSLI, Ventura Hall, Stanford, CA 94305 or Brown@SU-CSLI. ------------------------------ Date: 5 Jun 1985 16:12-EST From: leff%smu.csnet@csnet-relay.arpa Subject: New Bibliography Format I am using a new format in handling submissions of material. This format is the BIB citation format. BIB comes in the BSD UNIX 4.2 release. This is similar to the refer available with UNIX in general. The only major difference is the allowance of a definition file which I use for things like many articles from the same conference. That is I can define a string like BOOK11 for a specific conference in a definition file and then type BOOK11 for each paper in the conference for the information about editor, conference title, etc. Those users who use refer can insert the definitions in manually with a text editor. Definitions: D BOOK11 First Conference of Robotics Europe--Robot Technology and Applications\ %C Brussels, Belgium\ %D June 27-28 1984\ %E K. Rathmill\ %E P. Mac Conaill\ %E S. O'Leary\ %E J. Browne bib citations: %T Early Users Give Thumbs Up to TI's Expert System Tool %D April 15 %P 13 %J ComputerWorld %A P. Macconaill %T Esprit and Robotics Europe %J BOOK11 %P 1 %A H. J. Warnecke %A G. Schiele %T Performance Characteristics and Performance Testing of Industrial Robots - State of the Art %J BOOK11 %P 5 %A M. Priel %A B. Schatz %T Project for Development of a Photogrammetric Method for the Evaluation of the Dynamic Performance of Industrial Robots %J BOOK11 %P 18 %A J. H. Gilby %A R. Mayer %A G. A. Parker %T Dynamic Performance Measurement of Robot Arms %J BOOK11 %A 31 %A H. J. Warnecke %A R. D. Schraft %A M. C. Wanner %T Application of the Experimental Modal-Analysis in the Performance Testing Procedure of Industrial Robots %J BOOK11 %P 45 %A N. Percival %T A review of Safety Standards %J BOOK11 %P 55 %A J. P. Vautrin %T Safety of Robot Installations in France %J BOOK11 %P 61 %A R. Bell %T Assessment of Programmable Electronic Systems with Particular Reference to Robotics %J BOOK11 %P 68 %A P. Nicolaisen %T Occupational Safety and Industrial Robots - Present State of Discussions Within the Tripartite Group on Robotic Safety %J BOOK11 %P 74 %A F. Duggan %A R. H. Jones %A K. Khodabandehfoo %T Towards Developing Reliability and Safety Related Standards Using Systematic Methodologies %J BOOK11 %P 90 %A J. J. Hunter %T International Standards Activities in the Field of Industrial Robots %J BOOK11 %P 108 %A B. Knoerr %T Standardization in the Industrial Robot Field %J BOOK11 %P 116 %A H. Tipton %T International Standardization Related to Industrial Robots %J BOOK11 %P 122 %A G. Gini %A M. Gini %T Robot Languages in the Eighties %J BOOK11 %P 126 %A C. Launer %T Robot Programming Using a High-Level Language and CAD Facilities %J BOOK11 %P 139 %A C. Blume %T Implicit Robot Programming Based on a High-Level Explicit System and Using the Robot Data Base RODABAS %J BOOK11 %P 156 %A R. Dillman %T Robot Architecture for the Integraiton of Robots into Manufacturing Cells %J BOOK11 %P 172 %A K. Collins %A A. J. Palmer %A K. Rathmill %T The Development of a European Benchmark for the Comparison of Assembly Robot Programming Systems %J BOOK11 %P 187 %A H. Ford %A L. R. Hunt %A Renjeng Su %T A simple algorithm for computing canonical form %J Computers and Math %V 10 %N 4-5 %D 1984 %P 315 %A C. V. Negoita %T Fuzzy Systems in Knowledge Engineering %J Kuberneles %V 14 %N 1 %D 1985 %A Michael Strizenec %T Cognitive Psychology and AI %P 3 %J Kybernetika %V 21 %N 1 %D 1985 %A K. B. Zun %A V. V. Malyshev %T Generalized Minimax Approach to Solving Optimization Problems with Chance Constraints %J Engineering Cybernetics %V 22 %N 1 %P 105 %A L. A. Sholomov %T On Representation of a Binary Relation by a Collection of Criteria %J Engineering Cybernetics %V 22 %N 1 %P 93 %A Michael Georgeoff %T Transformations and Reduction Strategies for Typed Lambda Expressions %J ACM TOPLAS %V 6 %N 4 %D OCT 1984 %P 603 %A P. H. Winston %T The AI Business - A Perspective %J Manufacturing Engineering %V 94 %N 3 %D MAR 85 %P 75 ------------------------------ End of AIList Digest ********************