Structure of AI (was: Re: [extropy-chat] COMP: Distributed Computing)

[J. Andrew Rogers]

On Nov 21, 2004, at 11:43 AM, Samantha Atkins wrote:
>
> Interesting.  Please provide some citations to the relevant work.  
> Googling I find a great deal by GJ Chaitin and others on "Algorithmic 
> Information Theory".   Can you point out what you believe is the most 
> accessible and AI relevant material?   Such pointers would be much 
> appreciated.


Chaitin is mostly unrelated to these specific issues, even though it is 
the same field of mathematics.  His popularity and fame in various 
matters google bombs the rest of the field.

Directly pertinent to what I was talking about would be Hutter's and 
Schmidhuber's work at IDSIA.  Hutter has some papers on a universal 
theory of AI based on algorithmic probability and decision theory from 
circa 2000 that are both accessible and frame some aspects of the 
problem very well, and the references in the appendices will point you 
to most of the foundational mathematics (Kolmogorov, Solomonoff, and 
Levin mostly).  The de facto standard text for algorithmic information 
theory is Li and Vitanyi, which is also quite good.

To sum up rather crudely, you can formally integrate universal 
induction, decision theory, and some other bits into an elegant 
universal mathematical definition of intelligence, and derive system 
models from it that one can prove are universally optimal predictors 
and decision makers.  Unfortunately, while we can show that all 
intelligent systems have to be a derivative system of this in some 
fashion, the theoretically pure system derivation is utterly 
intractable due primarily to the universal induction aspect.  The 
nature and shape of the algorithm space suggested by this mathematics 
is very different than the traditional assumptions of AI research.

It is interesting to note that while the basic theory of universal 
induction was published in the late 1970s, to date no useful and 
tractable approximation has ever been described in literature despite 
the fact that this was a thoroughly trod area even prior to the 
mathematical formalization.  From the standpoint of the above 
mathematics, the problem of general AI is reduced to a long-standing 
theoretical computer science problem of tractable induction.

cheers,

j. andrew rogers