Schmidhuber's "New AI" seeks to base AI in prediction. It benefits by being based purely on the theory of computation. It need thus only be generally computable and not necessarily regular:

"One of the most brilliant mathematicians of the last and current century is John Horton Conway. Near the middle of the last century he formalized a notion of game in terms of a certain recursive data structure. He went on to show that every notion of number that has made it into the canon of numerical notions could be given representations in terms of this data structure. These ideas are documented in his delightful On Numbers and Games. Knuth popularized some of these ideas in his writings on surreal numbers."

http://biosimilarity.blogspot.com/2008/03/naming-as-dialectic.html

Rudy Rucker on cellular automata: "I was first hooked on modern cellular automata by [Wolfram84]. In this article, Wolfram suggested that many physical processes that seem random are in fact the deterministic outcome of computations that are simply so convoluted that they cannot be compressed into shorter form and predicted in advance. He spoke of these computations as "incompressible," and cited cellular automata as good examples."

"We have seen that the Glider Gun generates ordered gliders every 30 generations, and that the generation process is chaotic: it exhibits the butterfly effect."

http://www.upscale.utoronto.ca/GeneralInterest/Harrison/LifeEnergy/LifeA...