-2
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 10
    $\begingroup$ 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? $\endgroup$
    – Joel David Hamkins
    Commented Aug 26, 2011 at 10:49
  • $\begingroup$ @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. $\endgroup$
    – mikitov
    Commented Aug 26, 2011 at 13:13
  • $\begingroup$ Could you elaborate on "the theoretical limits of the nowadays information technology era"? $\endgroup$
    – j.c.
    Commented Aug 26, 2011 at 14:38
  • $\begingroup$ @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. $\endgroup$
    – mikitov
    Commented Aug 26, 2011 at 14:53

3 Answers 3

Reset to default
2
$\begingroup$

See

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Good one, but I was looking for more concrete examples. $\endgroup$
    – mikitov
    Commented Aug 26, 2011 at 14:54
  • 6
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Aug 26, 2011 at 16:33
0
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

Madhu Sudan talked about a strictly related issue. His talk is online at http://people.csail.mit.edu/madhu/talks/2011/CommComp-UIUC.ppsx

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .