讲义教程基础算法org

1、Fluid Concepts&Creative AnalogiessComputer MComputer Msof the FundamentalMechanismsof Thoughtof the FundamentalMechanismsof Thought*byDouglas Hofstadterand theby Douglas HofstadterFluid Analogies ResearchGroupand theFluid Analogies ResearchGroupBBCXl<SA Member of the Perseus Books GroupA Memb

2、er of the Perseus Books GrouCopyright © 1995 by BasicBooks, A Memberof the PerseusBooksGroup Composition by Acme Art, Inc. Printed in the United States of America. No part of this book may be reproduced in any manner whatsoever without written permission except in the case of brief quotations e

3、mbodied in critical articles and reviews. For information, address BasicBooks, 10 East 53rd Street, New York, NY 10022-5299.Library of Congress Cataloging-in-Publication Data Hofstadter, Douglas R, 1945-Fluid concepts and creative analogies: computer ms of the fundamental mechanisms of thought / by

4、Douglas Hofstadter and the Fluid Analogies Research Group.p.cm.Includes bibliographical references and index. ISBN 0-465-05154-5(cloth)ISBN 0-465-02475-0(paper)1. Cognitive science.2. Analogy-Computersimulation.3. Artificial intelligence.I. Fluid Analogies Research Group.II. Title.BF311.H6171994153.

5、4-dc2093-44294CIP99RRD98765ToD. andM.-Table of ContentsPrologue:Chapter 1.Preface 2:Chapter 2.Preface 3:Chapter 3.Preface 4:Chapter 4.Preface 5:ChapterS.Preface 6:Chapter 6.Preface 7:Chapter 7.Preface 8:Chapter 8.Preface 9:Chapter 9.Preface 10:Chapter 10.Epilogue:List of Illustrations. . . . . . . .

6、 . . . . . . . . . . . .The lVhy, the lVhen, the lVhere, and the lVho of This Book To Seek Whence Cometh a Sequence. . . . . . . . . . .(Douglas Hofstadter)The Unconscious Jugglingof Mental Objects The ArchitectureofJumbo. . . . . .(Douglas Hofstadter)ArithmeticalPlay and Nondeterminism. . . . .Numb

7、o:A Study in Cognition and Recognition(Daniel Defays)The Ineradicable Eliza Effect and Its Dangers. . High-level Perception,Representation,and Analogy:A Critique of Artificial-intelligenceMethodology. . .(David Chalmers, Robert French, and Douglas Hofstadter)Conceptual Halos and Slippability. . . .

8、. . . . . . . . . .The Copycat Project: A M of Mental Fluidity and Analogy-making. . . . . . . . . . . . .(Douglas Hofstadter and Melanie Mitchell)Two Early AI Approaches to Analogy. Perspectives on Copycat: Comparisonswith Recent Work (Melanie Mitchell and Douglas Hofstadter)Retrieval of Old and In

9、ventionof New Analogies Prolegomenato Any Future Metacat. . . . . .(Douglas Hofstadter)Analogy-makingin a Coffeehouse. Tabletop, BattleDp,Db-Platte,Potelbat, Belpatto, Platobet (Douglas Hofstadter and Robert French)The Knotty Problem of EvaluatingResear I and Cognitive Science. . . . . . . . . . . .

10、The Emergentalityof Tabletop,a Perception-basedM of Analogy-making(Douglas Hofstadter and Robert French)The IntoxicatingWorld of Alphabets and Their Styles . . . . . . .Letter Spirit:Esthetic Perceptionand Creative Play in the Rich Microcosmof the Roman Alphabet (Douglas Hofstadter and Gary McGraw)O

11、n Computers, Creativity, Credit,Brain Mechanisms,and the Turing Test. . . . . . . . . . . . .References . Index .ui. 1 1387971271311551691952052692753013073401407467493502List of illustrationsFront cover: Back cover:Prologue:P-l:Progression of five gridfonts, from "a" through "rn"

12、;, Progression of the same five gridfonts, from "n" through "z",Schematic representationof the flickering-clusters m of thestructure of water3Chapter 1:1-1:1-2:Temporal flow of ideas in the discovery of a mathematical pattern Schematic representationof a "mountain chain"

13、; sequence.41.57Preface 2:11-0:Hierarchical glomofletters that occurs ining a word.94Chapter 2:II-I:An example oftheumblegame98Chapter 3:III-I:III-2:III-3:III-4:III-5:III-6:An extract from Numbo's Pnet136A possible configuration of Numbo's cytoplasm140Trace of a run of Numbo . . . . . . . .

14、. . . . .144Numbo's Pnet at an early stage in a typical run.146Numbo's cytoplasm at an intermediate stage of the same run.147Comparative protocols of a human and Numbo, tackling thesame challenge152Chapter 4:IV-I:Predicate-calculus representations of two situations183Chapter 5:V-I:V-2:V-3:V-

15、4:Bar graph of Copycat's behavior on the problem"abc => abd; ijk => ?".Bar graph of Copycat's behavior on the problem"aabc => aabd; ijkk => ?".Bar graph of Copycat's behavior on the problem"abc => abd; kji => ?" . . . . . . . . . . . . . .

16、. . .Bar graph of Copycat's behavior on the problem"abc=>abd;mnjjj=>?".41vnV-5:Bar graph of Copycat's behavior on the problem"abc abd; rssttt ?"243V-6:Bar graph of Copycat's behavior on the problemV-7:"abc abd; xyz ?"Bar graph of Copycat&#

17、39;s behavior on the problem245"rst rsu; xyz ?". . . . . . . . . . . . . . .247V-8:Screen dumps of Copycat solving the problem"abcabd; mrrjjj?"251-255Chapter 6:Vl-l:Vl-2:Vl-3:Pictorial representations of two real-world situations.Predicate-calculus representations of the same two

18、 situations. A complicating factor that might be added to Figure Vl-2.276277281Preface 8:VlII-O:A "translation" into the Tabletop domain of a real-world analogy.320ChapterS: VlII-l: VlII-2: VlII-3: VlII-4: VlII-5: VlII-6:VlII-7: VlII-8: VlII-9: VlII-I0:Chapter 9:IX-I:IX-2:IX-3:Henry and El

19、iza sitting across a table from each other. A simple Tabletop analogy problem. . . . . . . .A more complex Tabletop analogy problem. . . .A cartoon based on the idea of Ob-Platte analogies A famous puzzle . . . . . . . . . . . . . . . . . . . .Working towards rendering the "East St. Louis of Il

20、linois" Ob-Platte problem in the Tabletop domain. . . . . . . .Gettingr to the "East St. Louis of Illinois" problem. Gettingjust a bit r to the "East St. Louis of Illinois" problem A "blockage" scenario in the Tabletop domain . . . . . . .Human perception of groups

21、 inside groups inside groupsSix members of the "Surround" family of analogy problems Six members of the "Blockage" family of analogy problems Six members of the "Buridan" family of analogy problems322324324335349353353354355357.394-5.396-7.398-9Preface 10:x-o."Norm

22、alcy": a gridfont that plays with style oycerebral level404uuiChapter 10:X-I:Transformation rules and sample output fromthe DAFFODIL program410X-2:Study #1 in lowercase 'a": a sampler revealing the abstractnessof the concept. . . . . . . . . . . . . . . . . . . . . . . . . . .413X-3:Tw

23、o different breakdowns of a letterform into roles . . . . . . .415X-4:The Letter/Spirit matrix, with "letter" represented by columnsand "spirit" represented by rows. . . . . . . . . . . . . .418X-5:The Letter Spirit grid, with three sample gridletters . . . .421X-6:Ten human-desi

24、gned gridfonts suggesting the richness ofthe domain422X-7:X-8:X-9:X-I0:X-ll:X-12:X-13:X-14:X-15:X-16:X-17:X-18:X-19:X-20:X-21:X-22:Epilogue:E-1:E-2:Study #2 in lowercase "a": showing how the constraints of the grid enhance the tendency to play at the fringes of letter categories.424Three g

25、ridletters that are semally distant butsyntactically . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425Four human-designed gridfonts illustrating various mechanismsfor the propagation of style428The creative pathways leading to Benzene "a" and Benzene "x"430Steps in th

26、e perception of a gridletter. . . . . . . . . . . .440Role-regrou within the Platonic concept "t'', with somegridletters that are therebyaccessible445Perceiving various potential stylistic attributes in a particular letter.450 A typical Letter Spirit analogy puzzle . . . . . . . . . . .

27、 . . .451Two possible solutions to the preceding puzzle452How essentially the same puzzle was handled by the designerof Friz Quadrata. . . . . . . . . . . . . . . . . . . . . . . . .453A possible seed letter "f" featuring a very striking norm-violation.455One far-out idea for realizing the

28、 concept "t" in the same style .455Two refinements of the preceding shape . . . . . . . . . . . . .455Fourteen letters fed to the GridFont network to suggest the fullhuman-designed style called "Hunt Four"461The remaining letters of Hunt Four as designed by the font's human i

29、nventor, and as produced by the GridFont network.462The first half of Hermann Zapf's typeface Optima464"Adam and Eve", a drawing by Harold Cohen's program Aaron.469Two waysto prove that an isosceles triangle has equal base angles:the standard wayand Pappus' tricky way479ixAckno

30、wledgmentsPrior Sources for ChaptersChapter 2 ("The Architectureof Jumbo" by D. Hofstadter)appearedin a highly condensed version in 1983, under the same title, on pages 161-170 of the Proceedings of the International Machine Learning Workshop, edited by R. Michalski,. Carbonell, and T. Mit

31、chell, published by the University of Illinois Press (Urbana, Illinois).Essentially the whole of Chapter 2 also appearedin 1985, in an Italian translation,underthe title "L'architetturadel 'umbo'", on pages 298-333 of La Sfida della Complessita, edited by G. Bocci and M. Ceruti

32、, published by Feltrinelli(Milan).Chapter 3 ("Numbo: A Study in Cognition and Recognition" by D. Defays) originally appeared in 1990, under the same title, on pages 217-243 of TheJoumalfor the Integrated Study of Artificial Intelligence, Cognitive Science, and Applied Epistem?logy, vol. 7,

33、 no. 2.Chapter4 ("High-levelPerception,Representation,and Analogy:A Critiqueof Artificial-intelligenceMethodology"by D. Chalmers,R. French,and D. Hofstadter) appearedin a slightly longer version in 1992, under the same title, on pages 185-211 of The Journal of Experimental and Theoretical

34、Artificial Intelligence, vol. 4, no. 3.Chapters 5 and 6 ("The Copycat Project: A M of Mental Fluidity and Analogy-making" and "Perspectives on Copycat: Comparisons with Recent Work" by D. Hofstadterand M. Mitchell) originally appearedtogether in 1993 as a single article, bearing

35、the same title as Chapter 5, on pages 31-112 of Advances in Connectionist and Neural Computation Theory, Vol. 2: Analogical Connections, edited by K. Holyoak and.Barnden,publishedby Ablex Corporation(Norwood, New Jersey). Reprintedwith permission from Ablex Publishing Corporation.Chapter 7 ("Pr

36、olegomena to Any Future Metacat" by D. Hofstadter) originally appeared in 1993 as the Afterword (pages 235-244) to M. Mitchell's book Analogy-Making as Perception, published by MIT Press (Cambridge, Massachusetts).Parts of Chapter 8 ("Tabletop, BattleOp, Ob-Platte, Potelbat, Belpatto,

37、Platobet" byD. Hofstadterand R. French)appearedin 1992, in a somewhatdifferentand quite condensedform, in Chapter3 of Tabletop: An Emergent, Stochastic Computer M of Analogy-making, French's Ph.D. dissertationin ComputerScience and Engineeringat the University of Michigan.The final six sect

38、ions of the Epilogue ("On Computers, Creativity, Credit, Brain Mechanisms, and the Turing Test" by D. Hofstadter)appearedin 1993, in somewhat different form, as part of the article "Analogy-making, Fluid Concepts, and Brain Mechanisms", published in Essays in Honour of Alan Turin

39、g, Vol. 2: Connectionism, Concepts, and Folk Psychology, edited by P. Millican and A. Clark, and published by Oxford University Press (Oxford, England).Figure CreditsJumble cartoon, p. 98, reprinted by permission: Tribune Media Services. Cartoon by Dana Fradon, p. 335, © 1992 The New Yorker Mag

40、azine, Inc. "Adam and Eve", p. 469, reprinted by permission: W. H. man.Prologue:The Why,the When,the Where, and the Who of This BookA Short History of FARG and FARGonautsThis book attempts to present roughly a decade and a half of research in cognitive science carried out by a significant

41、number of people. It all began in 1977, when I became an assistant professor of computer science at Indiana University and officially started doing researrtificial intelligence.A word on the term "artificial intelligence" . In the 1970's, I enthusiasti- cally embraced this provocative

42、phrase (or its acronym, "AI") as a good way of describing my field of research and my own goals. For me and probably for a good many other people, the term conjured up an exciting image -that of questing after the deepest secrets of the human mind and expressing them as pure, abstract patt

43、erns. In the early 1980's, however, that term, as words are wont to do, gradually started changing connotations, and began to exude the flavor of commercial applications and expert systems, as opposedto basic scientific research about the nature of thinking and being conscious. Then, even worse,

44、 it slid down the slope that ends up in meaningless buzzwords and empty hype. As a result I came to feel much less comfortable saying or writing "AI". Luckily, a new term was just then co into currency -"cognitive science" -and I started to favor that way of describing my researc

45、h interests, since it clearly stresses the idea of fidelity to what actually goes on in the human mind/brain,as well as the pure-science nature of the endeavor. Nowadays, I seldom call myself an "artificial-intelligence researcher" any more, choosing instead to saythat I am a cognitive sci

46、entist. But once in a blue moon, the term "Al"still manages to creep into my speech or writing.Myfirst AI research project, one in sequence extrapolation, led me to a series of related projects, and over the years, a number of graduate s joined me in develo them. In these early days - the

47、late 1970's and early 1980's - Marsha Meredith and Gray Clossman were my st co-workers, and both of them eventually completed Ph.D.' s under my supervision. In particular,2Douglas HofstadterMarsha developed the Seek-Whence program, which perceived linear patterns and extrapolated them. S

48、eek-Whence was the first large project representing our approach.In 1983, I took a sabbatical year at MIT's famous Artificial Intelligence Lab, courtesy of Marvin Minsky, and there I was very fortunate to meet yet another "MM", named Melanie Mitchell, who subsequently did her Ph.D. wit

49、h me on the Copycat project, which had sprung largely from Seek-Whence but was devoted to ming creative analogical thinking. At MIT, I was also accompa- nied by David Rogers, who came as a postdoc and continued working with me for another few years, and graduate Marek Lugowski.About halfway through

50、the year I spent at MIT, the University of Michigan offered me a very attractive position, and consequently I moved there in the fall of 1984. Peter Steiner, Dean of the School of Literature, Science, and the Arts, and Al Cain, Chair of the Psychology Department, me feel very much at home at the U-M

51、. Perhaps the strongest attraction for me of Michigan was the presenceof JohnHolland, whose intellectualand humancompanionship helped make my four years at Michigan unforgettably rich.The move to Michigan in the fall of 1984 marks, in my mind, the official beginning of the Fluid Analogies Research G

52、roup, or "FARG", as we - the FARGonauts (as we sometimes refer to ourselves) - usually refer to it. The silly-sounding acronym was more or less intended to be such.As for the term "fluid", this has occasioned some puzzlement now and then, but I think that it exudes quite a clear

53、image of flexibility, mutability, nonrigidity, adaptability, subtlety, pliancy, continuousness,smoothness, slip- periness, suppleness . By chance, as I was ty the preceding sentence, I noticed how rigid, unpliant, and unsupple my fingers were starting to get in this chilly Italian office. Given the

54、context of my thoughts, I took this discomfort as an invitation to renew my acquaintance with the nature of fluidity. So I walked down the corridor, filled up a sink with nice hot water, and immersed my hands in it. As they grew warmer, I thought about what was so special about water and how it move

55、s. A fluid responds to pressures by constantly changing shape in the most supple, flowing manner; it is neither rigid and brittle like a solid, nor volatile and insubstal like a gas. Where do these special properties come from? From the invisible molecular substrate, of course.As I pondered this, I recalled one of my favorite images and phrases from all of science - that of "flickering clusters". This poeti tle phrase encapsu- lates a well-known theory of