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:
http://www.idsia.ch/%7Ejuergen/newai/newai.html