Free Republic
Browse · Search
News/Activism
Topics · Post Article

To: tortoise
Go ahead and look it up; very few programmers even know what algorithmic induction is even though it is the theoretical elephant in the room of software engineering and computer science.

Got any pointers? A Google search is not very enlightening. (Amusingly, the third hit is your FR posts page).

298 posted on 04/15/2005 3:33:32 PM PDT by ThinkDifferent (These pretzels are making me thirsty)
[ Post Reply | Private Reply | To 195 | View Replies ]


To: ThinkDifferent
Got any pointers? A Google search is not very enlightening.

Not many. Very little research is published on this (now) hot topic due to its commercial value.

Put very crudely and simply: Algorithmic induction is a universal mechanism for generating the shortest program that will generate a particular output string. In conventional computer science, the program is given and the output is generated. With algorithmic induction the output is given and the ("a" really) program is generated. In essence, algorithmic induction reverse engineers the internal state of a black-box process from its output from which it can predict future states to the maximum predictive accuracy allowed by mathematics. A lot of very interesting properties fall out of this, like mathematically optimal decision-making. There are a number of classes of algorithm that are known to require algorithmic induction as a component of their implementation. Right now, we rely on humans to do algorithmic induction type processes.

The catch: there is only one description of universal algorithmic induction in computer science and it is known to be severely intractable, having limited use for narrow applications such as data compression. No approximations with better than geometric complexity have ever been publicly described. As a result, computer science is confined to only using algorithms that do not require algorithmic induction. Unfortunately, a lot of extremely important algorithms are in that group that requires algorithmic induction, and recent improvements in that area of mathematics have allowed us to understand the nature of the beast much better. There is an entire body of computer science that most programmers don't even know exists locked behind that one problem.

As a point of fact, the human brain demonstrably expresses a crude approximation of algorithmic induction that evidently scales "well enough". Crude though it may be, nothing currently described in computer science demonstrates similar efficiency at its level of scalability.

301 posted on 04/15/2005 4:23:55 PM PDT by tortoise (All these moments lost in time, like tears in the rain.)
[ Post Reply | Private Reply | To 298 | View Replies ]

Free Republic
Browse · Search
News/Activism
Topics · Post Article


FreeRepublic, LLC, PO BOX 9771, FRESNO, CA 93794
FreeRepublic.com is powered by software copyright 2000-2008 John Robinson