Path: utzoo!attcan!uunet!lll-winken!csd4.milw.wisc.edu!bionet!agate!shelby!rutgers!aramis.rutgers.edu!athos.rutgers.edu!nanotech From: dmo@turkey.philips.com (Dan Offutt) Newsgroups: sci.nanotech Subject: Swamping AI-based design with computational complexity Message-ID: Date: 30 Jun 89 00:17:21 GMT Sender: nanotech@athos.rutgers.edu Organization: Philips Laboratories, Briarcliff Manor, NY Lines: 59 Approved: nanotech@aramis.rutgers.edu The largest number of the in-principle most powerful AI-based design systems cannot possibly design working active shields. I have no doubt that such AI could design other, simpler devices. But active shields would be too complex. There are problems that are simple to describe, but which would easily swamp 10**100000 supercomputers all running in parallel. A randomly-chosen million-city traveling salesman problem would keep 10**100000 supercomputers busy for much much more than a trillion years, though one could code up an algorithm to solve (given enough time) such a problem on a single workstation in a few of pages of C code. When people bring up the possibility of a 10**6 (10**10, 10**50 -- whatever) speedup of AI-based designers, I am always reminded of the ease with which apparently simple problems lead to a combinatorial/exponential explosion in demand for computing resources. This is one reason I am convinced that problems such as active-shield design are likely to be totally intractable. AI-based active shield design could rapidly consume a 10**50 speedup and swamp every "fast" AI-based designer (of the "smart" kind, not the "idiot savant" kind) that would fit on this planet. One could argue that knowledge (of the human body and its interactions with nanoreplicators, for example) would be built into AI-based designers to speed active shield design. (Search can be speeded either by using faster and/or parallel hardware, or by using knowledge to guide search -- if such knowledge is available.) But the required knowledge of how nanoreplicators and the human body would interact does not exist. And creating that knowledge would probably require many (tens? billions?) years of experiments in which human beings would be infected with various noxious nanoreplicators and the effects observed. (This is effectively what natural evolution had to do to develop existing immune systems. And it took billions of years.) Such experiments are clearly out of the question. So the knowledge needed by AI-based designers to design working active shields does not exist, and it cannot be created except by doing forbidden experiments over a very long period of time. At the same time, simple-to-state problems beyond solution by the fastest parallel machines of any realizable structure (intelligent or otherwise) are ubiquitous. And active shield design (at least of the artificial immune system type) is clearly much more complex than these many simple-to-state, computationally-intractable problems. So the best AI-based designers will never design working active shields. More attention should thus be devoted to discussion of static barriers, sterilization methods, and other potentially-tractable approaches to protection from gray goo. Dan Offutt dmo@philabs.philips.com [The problem of finding *the* *optimal* active shield is surely as intractable as you describe. However, these same arguments apply to writing optimizing compilers, or playing chess. This doesn't mean that the problem of writing a useful optimizer or playing an acceptable game is intractable. It just means that designing active shields is like the rest of life, with no absolute guarantees of success. --JoSH]