Kolmogorov Complexity and Algorithmic Information Theory

Measuring complexity of an algorithm by using length of the shortest possible description (series of instructions)

Turing machine/ Universal Turing machine - programs form a prefix free set (Kologorov complexity/ analogous to information theory) [1]

Church Turing thesis

[1] Elements of Information Theory