Monday, May 29, 2006

Ants ants ants!

Can a million simple intelligences solve complex problems for us in reasonable time?

Well check these links...
1- Ants solve tough problems
2- CE-Ants: Ant-Like Agents for Path Management in the Next-Generation Internet

...for example :)

In fact this idea of using simpler euristics instead of optimal algorithms (with a higher complexity) is very intriguing :)
For examples context-free grammars are more powerfull than regular expressions (or finite automata), but I wander if it is possible to "emulate" somehow the power of grammars by layering automata...

And after some research, I found these 2 very interesting articles proving that:

  • first - it is possible to use F.A. to approximate to some degree context-free grammars, and
  • in the field of natural language modelling, it is also known that:

    Word formation of European languages can essentially be modelled in terms of
    regular languages.


    Sentence formation is theoretically of higher complexity ... But the more complex structures do not occur very often in
    real texts and are said to be psychologically too complex for practical use.

This could imply that somehow the Chomski hierarchy could be reconsidered from a different angle and since iteration/recursion seems to be one of the favourite tricks in Nature, why not: some "fractal" state machines could maybe prove to approximate the power of turing machines, without incurring too much in loop-like traps...

A few final mind-blowing ideas:
1- iterated cellular automata
2- iterated finite automata

No comments:

Post a Comment