On Fri, Dec 26, 2008 at 8:31 PM, J. Andrew Rogers <[email protected]> wrote: > Never mind discovering "a small number of clever algorithms" for AI, we > have not even discovered a great many basic algorithms for routine computer > science. > For example, there is no general indexing algorithm described in computer > science.
I noticed that neither linked lists nor arrays were particularly efficient for general operations that would include insertions, deletions and searches, which, when you think about it, are pretty much the norm. How often do you need a large data index that only rarely needs to be searched. The irony is that you cannot combine the two forms in a simple manner so that you can have a linked list for fast insertion and deletion and an array for fast searches. This seems like such a fundamental necessity that it is amazing that a linked list is still presented as anything more than an oh-that's-really-interesting method appropriate for short indexes. And with indirect indexes (using a handle or an index to an location entry) the data requires frequent compression (to squeeze out the gaps in the data area) if there is a heavy insertion and deletion. I believe the problem is directly related to agi because data relevant to some particular situation will tend to be distributed in a file so that a lot of relational indexing is needed. Since a lot of data can be described as being analogously similar to other kinds of data and since many variations in some particular kind of data might already exist in a database, a great many complicated modifications of concepts could, hypothetically, be done by modifying the indexes alone. Or at least, many quick initial changes could be done quickly through indexing if indexing was a more sophisticated art. Jim Bromer On Fri, Dec 26, 2008 at 8:31 PM, J. Andrew Rogers <[email protected]> wrote: > Never mind discovering "a small number of clever algorithms" for AI, we > have not even discovered a great many basic algorithms for routine computer > science. > > I think many people greatly underestimate how many gaping algorithm holes > there are in computer science for even the most important and mundane tasks. > The algorithm coverage of computer science is woefully incomplete, which is > why after a half century people are *still* finding general, elegant > algorithms for basic problems, many of which are bloody obvious in > hindsight. In short, we have no idea what important and fundamental > algorithms will be discovered from one year to the next that change the > boundaries of what is practically possible with computer science. > > For example, there is no general indexing algorithm described in computer > science. In fact, the only useful indexing algorithm index points on a > line. Not points in arbitrary space, not intervals on lines, not > hyper-rectangles in high-dimensionality space, never mind more complex > relations. Oddly enough, most computer scientists are ignorant of the fact > that no useful indexing algorithm exists for most data representations or > that a vast number of software applications are not tractably implementable > as a result. > The ability to tractably index almost nothing has consequences. Relational > database theory describes the manipulation of hyper-rectangles, but we fake > it very badly with indexes we actually have algorithms for. Did you ever > wonder why no one has built a massively distributed SQL database despite the > obvious value? It is not because it is theoretically impossible, but > because it is only possible if someone discovers a general algorithm for > indexing hyper-rectangles -- faking it is not distributable. Several other > big limitations in software are actually based in (the absence of) this > algorithm. It is utterly trivial to describe, and there are literally > several dozen algorithms that come close, but after 40 years no one has > published such an algorithm. When such an algorithm is finally published, > it will completely reset everything we think we know about many algorithms > and data structures. > > > There is a really large laundry list of undiscovered fundamental algorithms > like this that we work around with mediocre alternatives. If you look at > most of the limits of software, the vast majority are not theoretical limits > but limits based on the fact that there a lot of missing pages in our data > structures and algorithm texts. > > > Spatial indexing, for example, currently uses "insanely, infeasibly much > computation resource", so no one implements it beyond uselessly trivial > systems. But as most people familiar with the minutiae of the related > theoretical computer science will tell you, not only is it very probable > that a broadly general algorithm exists, but it will almost certainly scale > like Google does. We will go from "intractable" to "insanely cheap" in one > day. >... > And what ever happened to Machine is Software is Data? Ignoring this seems > to be a frequent enabler of specious reasoning. > > Cheers, > > J. Andrew Rogers > > > > ------------------------------------------- > agi > Archives: https://www.listbox.com/member/archive/303/=now > RSS Feed: https://www.listbox.com/member/archive/rss/303/ > Modify Your Subscription: > https://www.listbox.com/member/?&; > Powered by Listbox: http://www.listbox.com > ------------------------------------------- agi Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: https://www.listbox.com/member/?member_id=8660244&id_secret=123753653-47f84b Powered by Listbox: http://www.listbox.com
