MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Would it be possible for you to focus your question a little more sharply? What kind of connection do you seek? Which structural features do you want the connection to respect? – Joel David Hamkins Aug 26 '11 at 10:49
@Joel: I was in thinking in how the capacity of a channel can be related to the capacity of an automata for accepting a language. – mikitov Aug 26 '11 at 13:13
Could you elaborate on "the theoretical limits of the nowadays information technology era"? – j.c. Aug 26 '11 at 14:38
@jc Indeed, information theory on its primal approach was devoted to study the limits of the communication. Moreover, Automata theory is focused on the limits of the computer science. Computers and communication devices are the support of nowadays technological society. – mikitov Aug 26 '11 at 14:53
up vote 2 down vote accepted


share|cite|improve this answer
Good one, but I was looking for more concrete examples. – mikitov Aug 26 '11 at 14:54
Then, mikitov, you might ask a more focussed question to elicit such. I invite you to read the FAQ and how-to-ask pages for guidance. Gerhard "Ask Me About System Design" Paseman, 2011.08.25 – Gerhard Paseman Aug 26 '11 at 16:33

Turing's limit is logic - it speaks about static data if you will. Shannon's has to do with data transmission - movement, so to speak. There is some thought of combining logic with communication in the context of control theory. Turing's and Shannon's theorems appear in hybrid control theory to be precise - the branch that studies dynamic controls together with logic and switching. Nevertheless, they seem to be fundamentally different facts.

share|cite|improve this answer

Madhu Sudan talked about a strictly related issue. His talk is online at

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.