4 ms·

The original paper on "memcomputing" has also been posted on HN[0], not that it is worth reading in details. But I can recommend Scott's paper "NP-complete Pro

• pjungwir 12y ago
  Reading the comments in your [0], I'm confused about the relationship between thermodynamic entropy and information entropy. In thermodynamics, I've always thought of entropy as randomness, with the 2nd law saying that eventually the universe will turn to static. That is, entropy is increasing and information is decreasing. But in [2] and [3] I read that information entropy is information, and it has the same formula as thermodynamic entropy! Am I missing a negation or reciprocal somewhere? Is entropy information or lack or information? Reading those Wikipedia pages isn't helping me. Can someone explain why my intuition is wrong here? [2] http://en.wikipedia.org/wiki/Entropy_%28information_theory%29 http://en.wikipedia.org/wiki/Entropy_%28information_theory%2... [3] http://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_information_theory http://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_i...
  • jrochkind1 12y ago
    Well, the entropy in information theory is randomness too, in the sense that it's _unpredictable_, right? If you've got 1000 numbers, but you can predict them all with "n[i] = i * 2", then there's not that much information present, in the information theoretical entropy sense -- all you need is the formula `n[i] = i * 2` to describe all 1000 numbers, actually writing all 1000 (or 100,000) out just wastes space without providing any more information beyond `n[i] = i * 2 for i=1..1000` or whatever. But if the 1000 numbers are truly random, you need all 1000 numbers to describe the set of 1000 numbers in it. There is more information present, there is more entropy, precisely because of the randomness or unpredictability. Or to put it another way, if you can compress something losslessly, then it makes sense to think the uncompressed version doesn't have more "information" in it than the compressed version, even though it's more bytes, right? And what can't be compressed losslessly at all? Something entirely random with no predictability. So that's my understanding of the relationship -- information theoretic entropy is, in fact, randomness too. Random here meaning 'unpredictable', not describable by any formula or shortcut or compression -- the normal way we use the term 'random' in day-to-day software engineering, in fact, and the meaning that's crucial for cryptography for instance. (Then, as now, military budgets drove computer science research -- Shannon was a cryptographer on a DoD contract) (It doesn't neccesarily mean the 'random' data is _senseless_, just that it's entirely irregular and unpredictable). So, okay, now I'm grasping and I'm not sure what I'm talking about, but in this sense, as the entropy in the universe increases, the 'information' in the universe increases in the sense that there's no shortcut for describing the universe's state, it's increasingly just randomly distributed stuff? I don't know if that last paragraph makes sense, or if you can really talk at all about 'the amount of information in the universe increasing' -- I vaguely recall reading stuff on that before, the relationship between physical and information entropy, but I don't remember enough to speak on it really. But my understanding is that Shannon was inspired by the thermodynamic entropy in inventing information theory, realizing that the amount of randomness present in a sequence of data, the amount of unpredictability in it, was usefully understood as 'how much' information it contained. The "information" in "information theory" is not the plain-use meaning of the word 'information', although it has a relationship to it. But it means, well, precisely this, entropy or unpredictability. And that meaning has proven useful for reasoning about computation. But it's a low-level mathematical/computational sort of 'information', not information like answers to trivia questions.
    • pjungwir 12y ago
      That is really an awesome explanation, thank you! And thanks to the other commenters as well. I think my interpretation of the 2nd law as "static" (like on a TV) misleads me because static seems so uniform, and really increasing entropy is the opposite of uniform. It is n[i] = rand() rather than n[i] = C. So your explanation helps a lot! EDIT: So a followup question: Does information theory have anything like the 2nd law of thermodynamics? In the digital world we are used to lossless transfer, but children know that when you play "telephone" you lose information (or "gain" it in the sense the new message can't be predicted). Or maybe the analog of the 2nd law is the pigeonhole principle---I'm not sure. But if there is so much symmetry between the two kinds of entropy, is there a 2nd law for information?
      • jrochkind1 12y ago
        Thanks! I have no idea the answer to your followup question, heh.
      • lovemenot 12y ago
        My naive understanding of your follow up question is that energy is a special case of information and the Second Law is a special case of Shannon's Information Theory. The system in the second law is a special case of Shannon's channel. Apparent lossless digital transfer is a red herring though. Noise is inherent to any channel.
        • orbifold 12y ago
          I think it is unfair to give Shannon too much credit, Boltzmann and Gibbs came up with the exact definition Shannon gave S = -k \Sigma p_i ln(p_i), including a suitable information theoretic interpretation. As physicists they only thought about ignorance of the exact particles position and momentum in systems of 10^24 particles, but the essential idea is the same. Moreover von Neumann had generalized that notion to quantum mechanics S = - tr(\rho ln(\rho)), which gives it a form that is even more abstract than the information theoretic formulation. It was only ignorance on Shannons part that he was not familiar with the work of physicists and mathematicians before him on the subject.
  • jfoutz 12y ago
    Casual and handwavy, but these two ideas might be worth thinking about. Maxwell's demon is a good bridge. If you have perfect information you can reverse entropy. Another way to connect the two is to look at the edge case - when the universe is just a uniform heat - it won't take much information to describe. Yup, same temperature everywhere.
    • hackinthebochs 12y ago
      >when the universe is just a uniform heat - it won't take much information to describe. Actually this is when it takes maximum information to describe, as no particle is correlated with any other (and thus no savings from encoding). You basically have to fully describe each particle individually as a point in space. The alternate extreme is where matter is maximally compact and thus maximally correlated.
      • lomnakkus 12y ago
        (Not the PP, but...) That's a great way of putting it. Maximum entropy means minimal intrinsic information (and thus you need a lot of external information) and vice versa. I've never thought of it that way, thanks!
  • pash 12y ago
    No, you're right, it's just a terminological morass. Entropy and information are different names for the same concept, one that in its full generality is simply a measure of the uncertainty about the value of a random variable. Entropy is a bad name, one that will probably continue to confuse people for generations. Information is a decent name, but it's a bit backwards: information is the resolution of uncertainty. Really, the concepts implied by the names information and uncertainty are opposite sides of the same coin: for each unit of uncertainty, you gain one unit of information when you observe a random variable's outcome. The problem is that in the conventional definition (with the negative sign in front of the sum), a more positive quantity denotes more uncertainty. Perhaps the conventional quantity should have been called uncertainty and the name information should have been given to the inverse quantity, i.e., to the sum without the negative sign. As it is, people usually use the word information as a synonym for entropy or uncertainty, but when they focus on resolving uncertainty they sometimes use it to mean something like the opposite. In the end, so long as you are confident in you understanding of the concept, it doesn't much matter because it's easy to figure out what everybody means.
    • hackinthebochs 12y ago
      How about: entropy := amount of disorder information := knowledge of the system (knowledge of disorder) uncertainty := unknown disorder (entropy - information) And so entropy and information are opposites: as you gain more information about a system the uncertainty is reduced. If the entropy of a system increase, the amount of information required to describe it increases. If you have an amount of information equal to the entropy, your uncertainty is zero and the system is completely described. This seems to square with our usage of the terms in the context of thermodynamics and information theory.
      • tjradcliffe 12y ago
        Another way to look at this is the process of reading a stream of bytes. A high-entropy stream means that based on what you have read so far you have a very small chance of predicting the next byte you read. By the same token (as it were) in those circumstances the next byte you read will contain a great deal of information about its value that you did not previously have. In a low-entropy stream the bytes coming in might be: 0, 1, 2, 3... and by the time you get to byte N you can be pretty sure of its value, so the next byte contains very little information you don't already have. Both information and entropy are measures of the novelty of the next byte in the stream, but information is measured from the perspective of what you get when you read it and entropy is measured from the perspective of what you have before you read it.
  • hackinthebochs 12y ago
    The way I've squared the similar terminologies in different fields is that as thermodynamic entropy increases, the amount of information required to encode/duplicate the state of the system increases (consider the extremes of maximally compact matter (say pre-big bang) and heat death where all matter is spread out arbitrarily over an unbounded volume). So entropy is equivalent to information as understood as a measure of disorder. This squares with shannon entropy as it can be understood as just a measure of the "disorder" in a random variable. The difficulty is distinguishing the other interpretation of information as a specific correlation, a quantification of order rather than disorder. When we think of communicating the state of a RV as some number of bits of "information", one way to think of it is that we're reducing the "possible disorder" (i.e. uncertainty) by communicating partial state. And so information here is the change in the possible disorder (uncertainty), the more information you receive the less uncertainty that remains.
  • moultano 12y ago
    The confusion comes from what posesses the information, you or the object. If a distribution is spread out, I know very little about it. If I learn something about it, and make it less spread out, then I have more information about it, and there is less information left in it. Learning about something is taking information out of it. So something has a lot of information if you know nothing about it. If you know a lot about it, you've taken all the information out of it, and there's nothing left.