From Alan Turing we know what we can expect from a computer and from Claude Shannon what we can expect from a communication channel.


Does anyone know any connection between these two theories (namely, Automata Theory and Information Theory) which actually set the theoretical limits of the nowadays information technology era?



Turing-Shannon connection
See 


<http://en.wikipedia.org/wiki/Algorithmic_information_theory>


