Department of Computer Science

Computability, Complexity and Randomness


“Algorithmic information theory (AIT) is the result of putting Shannon’s information theory and Turing’s computability theory into a cocktail shaker and shaking vigorously. The basic idea is to measure the complexity of an object by the size in bits of the smallest program for computing it.” (G. J. Chaitin).

The group work includes theoretical and experimental results in AIT (with various models of computation) and applications to mathematical logic and quantum randomness; automatic structures; computable model theory; games played on graphs and logic; model checking, specifications and verifications.

Members (academic staff or PhD students):

C.S. Calude, A. Nies, M.J. Dinneen, B. Khoussainov

More information:

Algorithmic Information Theory