13 ms·

A Mathematical Theory of Communication (1948) [pdf]

SatvikBeri 10y ago
Trivia: this paper was renamed The Mathematical Theory of Communication the following year, after people realized just how significant it was.
- Bromskloss 10y ago
  And the year after that, simply _The Theory_.
epistasis 10y ago
Great to see this classic. But when I saw it was on worrydream.com I got my hopes up that it would be a link to a Bret Victor explanatory web experiment...
- j2kun 10y ago
  Looks like he's not quite ready to kill math?
minipci1321 10y ago
Also, the OpenCourseWare course 6.450 by Prof. Gallagher on YouTube can be helpful to digest the main ideas.
0xdeadbeefbabe 10y ago
This paper and lots of others are mentioned in the book The Dream Machine: J.C.R. Licklider and the Revolution That Made Computing Personal. I'm reading it now, and it's wonderful. Thanks HN. Edit: It's like a very entertaining index.
danielam 10y ago
For those interested in the nature of information as such and as it relates to computation, you might find "From Aristotle to John Searle and Back Again: Formal Causes, Teleology, and Computation in Nature" by E. Feser interesting.
- gshubert17 10y ago
  Feser's blog post about his paper, and some interesting comments: http://edwardfeser.blogspot.com/2016/05/aristotle-searle-and-computation-in.html http://edwardfeser.blogspot.com/2016/05/aristotle-searle-and...
  - SilasX 10y ago
    Don't think it's going to be of much interest to HN readers: >Yet, a powerful objection has been raised by John Searle, who argues that computational features are observer-relative, rather than intrinsic to natural processes. If Searle is right, then computation is not a natural kind, but rather a kind of human artifact, and is therefore unavailable for purposes of scientific explanation. >In this paper, I argue that Searle’s objection has not been, and cannot be, successfully rebutted by his naturalist critics. Computation inaccessible to science? Searle being correct about computation? Waterfalls play chess, as viewed by the right observers?
    - cgio 10y ago
      Do you refute Searle by just asking? Waterfalls play chess regardless the observer? Do my 4 apples compute their sum just by virtue of being 4?
      - eggy 10y ago
        The quote made by a poster referencing another party's paper on Searle about being not natural, an artifact of the observer, raises some cautions to me even if I get the drift. I think man is part of nature, is nature, and therefore arguments couched from the 'supernatural' perspective are faulty from the get go. Take the hexagonal pattern of honeycombs. Nobody really knows yet how bees actually pull it off. There are hypotheses about the pheromone or chemical trail fading, and circle-walking they carry out with the hexagaonal shape being an emergent property. The hexagonal shape also happens to be one of the 'Close Packing' methods, HCP, or Hexagonal Close Packing. I am re-reading Cellular Automata: A Discrete Universe by Andrew Ilachinski published in 2001. I am on the chapter about possibly defining a new physics, "Information Physics", section 12.4 to be exact. Paraphrasing a bit, the term 'primordial information', or the notion that information exists independently of the semantics used to ascribe meaning to it. That "all observables found in nature are essentially 'data structures' that the universe uses to encode information with." It goes on to remark that all computations are inherently physical processes (slide rule, electrons in computers) and that information is possibly more than just a concept, but one of the fundamental units woven into the very fabric of the universe. I have become less of a reductionist as I get older, and I have been following Complexity Science since the 1980s/90s. I am starting to lean towards 'information' as not being just a concept, but something real and physical no matter how it is encoded or contained. I guess from a superficial point this puts me at odds with Searle, or the indirect quote of his works. I'll have to read Searle; I've only learned of him via second-hand quotes, and his counters with Daniel Dennett.
pklausler 10y ago
It's somewhat depressing how much smarter people seem to have been in the past than they seem to be now.
- vecter 10y ago
  What gives you that impression? When Newton alive, no one knew calculus. He had to invent it (along with Leibniz). Now we learn calculus in high school.
  - qubex 10y ago
    Everything we take for granted today must have been by definition been invented previously, so any list of who-invented-what contains Great People Of The Past but doesn't contain the rank and file of those who worked in obscurity and achieved little, leaving the impression that in the past folks were smarter. It is a form of survivorship bias.
- jonnybgood 10y ago
  People of today are just as smart. It was only simpler then. Math has grown in complexity and has caused mathematicians to become more specialized. So, in order to see the good stuff and the smart people of today, it requires going deep in to those specialized fields. It's a matter of accessibility.
  - amelius 10y ago
    Could you give some examples in the field of Computer Science then perhaps?
    - jackmott 10y ago
      http://tomasp.net/coeffects/ http://tomasp.net/coeffects/ http://www.scottaaronson.com/blog/?p=2741 http://www.scottaaronson.com/blog/?p=2741
  - privong 10y ago
    > People of today are just as smart. It was only simpler then. An additional effect is that when people learn the major past discoveries (e.g., calculus, mechanics), the version that is taught is often significantly different from how the discoverer cast it or how the idea was originally formulated. Years of teaching, refinement, and finding other techniques to solve problems or prove theorems makes it easier to learn. One example is "Maxwell's Equations" for electro-magnetism; the most commonly used modern form consisting of 4 equations was condensed from Maxwell's 20 equations by Oliver Heaviside: https://en.wikipedia.org/wiki/Maxwell%27s_equations#Formulation_in_terms_of_electric_and_magnetic_fields https://en.wikipedia.org/wiki/Maxwell%27s_equations#Formulat... If the original 20 equation form was more conducive to use and teaching, I suspect we those would be more widely used.
syats 10y ago
A must read! Don't despair if it takes you a while to read it, my guess is at least one month for someone with undergrad math understanding. It will be gratifying in the end.
- Swizec 10y ago
  It really is a great paper. I had an entire semester-long course on just this paper in undergrad. So many hours of lessons and instruction and studying and tutorials. And it wasn't clicking. I flunked the exam 3 times. Then I tossed out my professor's material and sat down with Shannon's original paper for a weekend. Got an A. Maybe that says more about my professor than about this paper, but it's a great paper.
frequentlybayes 10y ago
Completely random, I just had googled this before coming on Hacker News so that I could cite the original article. Great read if you haven't done so yet.
diego898 10y ago
If this really interests you, you might also like Christopher Olah's blog post on Visual Information Theory [1] [1]: https://colah.github.io/posts/2015-09-Visual-Information/ https://colah.github.io/posts/2015-09-Visual-Information/
quakeguy 10y ago
There is a great Computerphile video on YT about this topic i can recommend: https://www.youtube.com/watch?v=5sskbSvha9M&index=4&list=PLzH6n4zXuckpKAj1_88VS-8Z6yn9zX_P6 https://www.youtube.com/watch?v=5sskbSvha9M&index=4&list=PLz... (Link to playlist, as all of those are great.)
ryanmarsh 10y ago
Is there a pedestrian explanation of this? My math is, shall we say, lacking.
- kragen 10y ago
  No, there is no royal road to Geometry. Learn the math. Have patience with yourself; it will take a while. You'll be glad you did!
- sn9 10y ago
  Read James Gleick's The Information. One of the best nonfiction books I've ever read and an accessible explanation of Shannon's work is a major part of the book.
carapace 10y ago
Meaning no disparagement of Shannon and Information Theory, I would urge you to study Cybernetics as well. Information Theory can be understood as an attempt to make real world phenomenon act like digital symbols. Cybernetics, in contrast, attempts to make digital symbols act like real world phenomenon. In logic, "A = not A" is a contradiction that jams the works, but in cybernetics it's just an oscillator. Our systems are more properly modelled by the formalisms of Cybernetics than Information Theory. (You can get a PDF copy of "Introduction to Cybernetics" from http://pespmc1.vub.ac.be/ASHBBOOK.html http://pespmc1.vub.ac.be/ASHBBOOK.html)
- cgio 10y ago
  Cybernetics was highly influenced by Shannon's IT. Shannon was also an active member in the cybernetics community. I would not consider the theories antithetical but rather synthetical.
- bpchaps 10y ago
  Thanks for the link. I've been struggling recently in trying to explain a lot of ideas that seem to coincide very tightly with cybernetics. This gives me so much to read on! :)
panic 10y ago
This is a pretty clever way to generate random bigrams without a computer: To construct (3) for example, one opens a book at random and selects a letter at random on the page. This letter is recorded. The book is then opened to another page and one reads until this letter is encountered. The succeeding letter is then recorded. Turning to another page this second letter is searched for and the succeeding letter recorded, etc. A similar process was used for (4), (5) and (6). It would be interesting if further approximations could be constructed, but the labor involved becomes enormous at the next stage.
- panic 10y ago
  More neat stuff -- the redundancy of English text happens to be just right for making crossword puzzles! The redundancy of a language is related to the existence of crossword puzzles. If the redundancy is zero any sequence of letters is a reasonable text in the language and any two-dimensional array of letters forms a crossword puzzle. If the redundancy is too high the language imposes too many constraints for large crossword puzzles to be possible. A more detailed analysis shows that if we assume the constraints imposed by the language are of a rather chaotic and random nature, large crossword puzzles are just possible when the redundancy is 50%. If the redundancy is 33%, three-dimensional crossword puzzles should be possible, etc.
PDoyle 10y ago
Shameless self-promotion: by chance, I happened to write a blog post today that's all about information theory: "Measuring Information in Millibytes" https://engineering.vena.io/2016/07/12/measuring-information-in-millibytes/ https://engineering.vena.io/2016/07/12/measuring-information...
quinndupont 10y ago
Three years prior, Shannon worked out many of the issues for his theory of information in his work on cryptography: Shannon, Claude. “A Mathematical Theory of Cryptography.” Murray Hill, NJ: Bell Labs, September 1, 1945. http://www.cs.bell-labs.com/who/dmr/pdfs/shannoncryptshrt.pdf http://www.cs.bell-labs.com/who/dmr/pdfs/shannoncryptshrt.pd....
- abecedarius 10y ago
  Not found. Did you mispaste the url?
  - Kikawala 10y ago
    Working alternative link with PDF here: https://www.iacr.org/museum/shannon45.html https://www.iacr.org/museum/shannon45.html
- femto 10y ago
  I've just finished the history book "The Theory that would not die", as mentioned here a couple of weeks ago [1]. It's got some interesting stuff to say on how Shannon's work emerged from the cryptography scene. According to the book, Information Theory was the culmination of all sorts of pragmatic techniques that were developed during code breaking. The terminology and expression was different (eg. information was measured in bans rather than bits), but it was really interesting to read about how practice developed into theory. [1] https://news.ycombinator.com/item?id=11983200 https://news.ycombinator.com/item?id=11983200
justifier 10y ago
> The significant aspect is that the actual message is one selected from a set of possible messages. this is an amazing opener does anyone know of the history of simultaneous possibility theory?

Trivia: this paper was renamed The Mathematical Theory of Communication the following year, after people realized just how significant it was.

Bromskloss 10y ago
And the year after that, simply _The Theory_.

epistasis 10y ago

Great to see this classic. But when I saw it was on worrydream.com I got my hopes up that it would be a link to a Bret Victor explanatory web experiment...

j2kun 10y ago
Looks like he's not quite ready to kill math?

minipci1321 10y ago

Also, the OpenCourseWare course 6.450 by Prof. Gallagher on YouTube can be helpful to digest the main ideas.

0xdeadbeefbabe 10y ago

This paper and lots of others are mentioned in the book The Dream Machine: J.C.R. Licklider and the Revolution That Made Computing Personal. I'm reading it now, and it's wonderful. Thanks HN. Edit: It's like a very entertaining index.

danielam 10y ago

For those interested in the nature of information as such and as it relates to computation, you might find "From Aristotle to John Searle and Back Again: Formal Causes, Teleology, and Computation in Nature" by E. Feser interesting.

gshubert17 10y ago
Feser's blog post about his paper, and some interesting comments: http://edwardfeser.blogspot.com/2016/05/aristotle-searle-and-computation-in.html http://edwardfeser.blogspot.com/2016/05/aristotle-searle-and...
- SilasX 10y ago
  Don't think it's going to be of much interest to HN readers: >Yet, a powerful objection has been raised by John Searle, who argues that computational features are observer-relative, rather than intrinsic to natural processes. If Searle is right, then computation is not a natural kind, but rather a kind of human artifact, and is therefore unavailable for purposes of scientific explanation. >In this paper, I argue that Searle’s objection has not been, and cannot be, successfully rebutted by his naturalist critics. Computation inaccessible to science? Searle being correct about computation? Waterfalls play chess, as viewed by the right observers?
  - cgio 10y ago
    Do you refute Searle by just asking? Waterfalls play chess regardless the observer? Do my 4 apples compute their sum just by virtue of being 4?
    - eggy 10y ago
      The quote made by a poster referencing another party's paper on Searle about being not natural, an artifact of the observer, raises some cautions to me even if I get the drift. I think man is part of nature, is nature, and therefore arguments couched from the 'supernatural' perspective are faulty from the get go. Take the hexagonal pattern of honeycombs. Nobody really knows yet how bees actually pull it off. There are hypotheses about the pheromone or chemical trail fading, and circle-walking they carry out with the hexagaonal shape being an emergent property. The hexagonal shape also happens to be one of the 'Close Packing' methods, HCP, or Hexagonal Close Packing. I am re-reading Cellular Automata: A Discrete Universe by Andrew Ilachinski published in 2001. I am on the chapter about possibly defining a new physics, "Information Physics", section 12.4 to be exact. Paraphrasing a bit, the term 'primordial information', or the notion that information exists independently of the semantics used to ascribe meaning to it. That "all observables found in nature are essentially 'data structures' that the universe uses to encode information with." It goes on to remark that all computations are inherently physical processes (slide rule, electrons in computers) and that information is possibly more than just a concept, but one of the fundamental units woven into the very fabric of the universe. I have become less of a reductionist as I get older, and I have been following Complexity Science since the 1980s/90s. I am starting to lean towards 'information' as not being just a concept, but something real and physical no matter how it is encoded or contained. I guess from a superficial point this puts me at odds with Searle, or the indirect quote of his works. I'll have to read Searle; I've only learned of him via second-hand quotes, and his counters with Daniel Dennett.

pklausler 10y ago

It's somewhat depressing how much smarter people seem to have been in the past than they seem to be now.

vecter 10y ago
What gives you that impression? When Newton alive, no one knew calculus. He had to invent it (along with Leibniz). Now we learn calculus in high school.
- qubex 10y ago
  Everything we take for granted today must have been by definition been invented previously, so any list of who-invented-what contains Great People Of The Past but doesn't contain the rank and file of those who worked in obscurity and achieved little, leaving the impression that in the past folks were smarter. It is a form of survivorship bias.
jonnybgood 10y ago
People of today are just as smart. It was only simpler then. Math has grown in complexity and has caused mathematicians to become more specialized. So, in order to see the good stuff and the smart people of today, it requires going deep in to those specialized fields. It's a matter of accessibility.
- amelius 10y ago
  Could you give some examples in the field of Computer Science then perhaps?
  - jackmott 10y ago
    http://tomasp.net/coeffects/ http://tomasp.net/coeffects/ http://www.scottaaronson.com/blog/?p=2741 http://www.scottaaronson.com/blog/?p=2741
- privong 10y ago
  > People of today are just as smart. It was only simpler then. An additional effect is that when people learn the major past discoveries (e.g., calculus, mechanics), the version that is taught is often significantly different from how the discoverer cast it or how the idea was originally formulated. Years of teaching, refinement, and finding other techniques to solve problems or prove theorems makes it easier to learn. One example is "Maxwell's Equations" for electro-magnetism; the most commonly used modern form consisting of 4 equations was condensed from Maxwell's 20 equations by Oliver Heaviside: https://en.wikipedia.org/wiki/Maxwell%27s_equations#Formulation_in_terms_of_electric_and_magnetic_fields https://en.wikipedia.org/wiki/Maxwell%27s_equations#Formulat... If the original 20 equation form was more conducive to use and teaching, I suspect we those would be more widely used.

syats 10y ago

A must read! Don't despair if it takes you a while to read it, my guess is at least one month for someone with undergrad math understanding. It will be gratifying in the end.

Swizec 10y ago
It really is a great paper. I had an entire semester-long course on just this paper in undergrad. So many hours of lessons and instruction and studying and tutorials. And it wasn't clicking. I flunked the exam 3 times. Then I tossed out my professor's material and sat down with Shannon's original paper for a weekend. Got an A. Maybe that says more about my professor than about this paper, but it's a great paper.

frequentlybayes 10y ago

Completely random, I just had googled this before coming on Hacker News so that I could cite the original article. Great read if you haven't done so yet.

diego898 10y ago

If this really interests you, you might also like Christopher Olah's blog post on Visual Information Theory [1] [1]: https://colah.github.io/posts/2015-09-Visual-Information/ https://colah.github.io/posts/2015-09-Visual-Information/

quakeguy 10y ago

There is a great Computerphile video on YT about this topic i can recommend: https://www.youtube.com/watch?v=5sskbSvha9M&index=4&list=PLzH6n4zXuckpKAj1_88VS-8Z6yn9zX_P6 https://www.youtube.com/watch?v=5sskbSvha9M&index=4&list=PLz... (Link to playlist, as all of those are great.)

ryanmarsh 10y ago

Is there a pedestrian explanation of this? My math is, shall we say, lacking.

kragen 10y ago
No, there is no royal road to Geometry. Learn the math. Have patience with yourself; it will take a while. You'll be glad you did!
sn9 10y ago
Read James Gleick's The Information. One of the best nonfiction books I've ever read and an accessible explanation of Shannon's work is a major part of the book.

carapace 10y ago

Meaning no disparagement of Shannon and Information Theory, I would urge you to study Cybernetics as well. Information Theory can be understood as an attempt to make real world phenomenon act like digital symbols. Cybernetics, in contrast, attempts to make digital symbols act like real world phenomenon. In logic, "A = not A" is a contradiction that jams the works, but in cybernetics it's just an oscillator. Our systems are more properly modelled by the formalisms of Cybernetics than Information Theory. (You can get a PDF copy of "Introduction to Cybernetics" from http://pespmc1.vub.ac.be/ASHBBOOK.html http://pespmc1.vub.ac.be/ASHBBOOK.html)

cgio 10y ago
Cybernetics was highly influenced by Shannon's IT. Shannon was also an active member in the cybernetics community. I would not consider the theories antithetical but rather synthetical.
bpchaps 10y ago
Thanks for the link. I've been struggling recently in trying to explain a lot of ideas that seem to coincide very tightly with cybernetics. This gives me so much to read on! :)

panic 10y ago

This is a pretty clever way to generate random bigrams without a computer: To construct (3) for example, one opens a book at random and selects a letter at random on the page. This letter is recorded. The book is then opened to another page and one reads until this letter is encountered. The succeeding letter is then recorded. Turning to another page this second letter is searched for and the succeeding letter recorded, etc. A similar process was used for (4), (5) and (6). It would be interesting if further approximations could be constructed, but the labor involved becomes enormous at the next stage.

panic 10y ago
More neat stuff -- the redundancy of English text happens to be just right for making crossword puzzles! The redundancy of a language is related to the existence of crossword puzzles. If the redundancy is zero any sequence of letters is a reasonable text in the language and any two-dimensional array of letters forms a crossword puzzle. If the redundancy is too high the language imposes too many constraints for large crossword puzzles to be possible. A more detailed analysis shows that if we assume the constraints imposed by the language are of a rather chaotic and random nature, large crossword puzzles are just possible when the redundancy is 50%. If the redundancy is 33%, three-dimensional crossword puzzles should be possible, etc.

PDoyle 10y ago

Shameless self-promotion: by chance, I happened to write a blog post today that's all about information theory: "Measuring Information in Millibytes" https://engineering.vena.io/2016/07/12/measuring-information-in-millibytes/ https://engineering.vena.io/2016/07/12/measuring-information...

quinndupont 10y ago

Three years prior, Shannon worked out many of the issues for his theory of information in his work on cryptography: Shannon, Claude. “A Mathematical Theory of Cryptography.” Murray Hill, NJ: Bell Labs, September 1, 1945. http://www.cs.bell-labs.com/who/dmr/pdfs/shannoncryptshrt.pdf http://www.cs.bell-labs.com/who/dmr/pdfs/shannoncryptshrt.pd....

abecedarius 10y ago
Not found. Did you mispaste the url?
- Kikawala 10y ago
  Working alternative link with PDF here: https://www.iacr.org/museum/shannon45.html https://www.iacr.org/museum/shannon45.html
femto 10y ago
I've just finished the history book "The Theory that would not die", as mentioned here a couple of weeks ago [1]. It's got some interesting stuff to say on how Shannon's work emerged from the cryptography scene. According to the book, Information Theory was the culmination of all sorts of pragmatic techniques that were developed during code breaking. The terminology and expression was different (eg. information was measured in bans rather than bits), but it was really interesting to read about how practice developed into theory. [1] https://news.ycombinator.com/item?id=11983200 https://news.ycombinator.com/item?id=11983200

justifier 10y ago

> The significant aspect is that the actual message is one selected from a set of possible messages. this is an amazing opener does anyone know of the history of simultaneous possibility theory?