AIT and computational complexity theory arguably underlay all other sciences. They allow us to define randomness (http://www.cs.auckland.ac.nz/~chaitin/georgia.html), pattern, probability (http://www.scholarpedia.org/article/Algorithmic_probability), inference (http://www.wisegeek.com/what-is-solomonoff-induction.htm), ignorance, and perhaps one day consciousness.
They allow us to prove, with absolute certainty, whether we are talking to a deity ( http://scottaaronson.com/blog/?p=56), and to prove that some questions will forever be beyond our grasp.
Even discounting Zuse and Wheeler's "It's from Bits" conception of information and computation as the basis of physics (http://en.wikipedia.org/wiki/Digital_physics), these disciplines promise to help us solve our hardest and most interesting problems by, first of all, telling us whether they are solvable at all, and if so, whether they are solvable before the heat death of the universe. Consider that Goedel, Cohen, and Turing struck down the Continuum Hypothesis from Hilbert's list of open problems, allowing us to abandon a futile line of inquiry and focus on other problems. Current developments in quantum computability theory may similarly strike down vast swathes of sterile ideas, directing us toward questions whose answers are solvable.