In retrospect, it was a pity that he used the name 'entropy', because there is a longstanding concept in physics with the same name, normally interpreted as 'disorder'. Its opposite, 'order', is usually identified with complexity. The context here is the branch of physics known as thermodynamics, which is a specific simplified model of a gas. In thermodynamics, the molecules of a gas are modelled as 'hard spheres', tiny billiard balls. Occasionally balls collide, and when they do, they bounce off each other as if they are perfectly elastic. The Laws of Thermodynamics state that a large collection of such spheres will obey certain statistical regularities. In such a system, there are two forms of energy: mechanical energy and heat energy.
The First Law states that the total energy of the system never changes. Heat energy can be transformed into mechanical energy, as it is in, say, a steam engine; conversely, mechanical energy can be transformed into heat. But the sum of the two is always the same. The Second Law states, in more precise terms (which we explain in a moment), that heat cannot be transferred from a cool body to a hotter one. And the Third Law states that there is a specific temperature below which the gas cannot go - 'absolute zero', which is around -273 degrees Celsius.
The most difficult -and the most interesting -of these laws is the Second. In more detail, it involves a quantity that is again called 'entropy', which is usually interpreted as 'disorder'. If the gas in a room is concentrated in one corner, for instance, this is a more ordered (that is, less disordered!) state than one in which it is distributed uniformly throughout the room. So when the gas is uniformly distributed, its entropy is higher than when it is all in one corner. One formulation of the Second Law is that the amount of entropy in the universe always increases as time passes. Another way to say this is that the universe always becomes less ordered, or equivalently less complex, as time passes. According to this interpretation, the highly complex world of living creatures will inevitably become less complex, until the universe eventually runs out of steam and turns into a thin, lukewarm soup.
This property gives rise to one explanation for the 'arrow of time', the curious fact that it is easy to scramble an egg but impossible to unscramble one. Time flows in the direction of increasing entropy. So scrambling an egg makes the egg more disordered -that is, increases its entropy which is in accordance with the Second Law. Unscrambling the egg makes it less disordered, and decreases energy, which conflicts with the Second Law. An egg is not a gas, mind you, but thermodynamics can be extended to solids and liquids, too.
At this point we encounter one of the big paradoxes of physics, a source of considerable confusion for a century or so. A different set of physical laws, Newton's laws of motion, predicts that scrambling an egg and unscrambling it are equally plausible physical events. More precisely, if any dynamic behaviour that is consistent with Newton's laws is run backwards in time, then the result is also consistent with Newton's laws. In short, Newton's laws are 'time-reversible'.
However, a thermodynamic gas is really just a mechanical system built from lots of tiny spheres.
In this model, heat energy is just a special type of mechanical energy, in which the spheres vibrate but do not move en masse. So we can compare Newton's laws with the laws of thermodynamics. The First Law of Thermodynamics is simply a restatement of energy conservation in Newtonian mechanics, so the First Law does not contradict Newton's laws.
Neither does the Third Law: absolute zero is just the temperature at which the spheres cease vibrating. The amount of vibration can never be less than zero.
Unfortunately, the Second Law of Thermodynamics behaves very differently. It contradicts Newton's laws. Specifically, it contradicts the property of time-reversibility. Our universe has a definite direction for its 'arrow of time', but a universe obeying Newton's laws has two distinct arrows of time, one the opposite of the other. In our universe, scrambling eggs is easy and unscrambling them seems impossible. Therefore, according to Newton's laws, in a time-reversal of our universe, unscrambling eggs is easy but scrambling them is impossible. But Newton's laws are the same in both universes, so they cannot prescribe a definite arrow of time.
Many suggestions have been made to resolve this discrepancy. The best mathematical one is that thermodynamics is an approximation, involving a 'coarse-graining' of the universe in which details on very fine scales are smeared out and ignored. In effect, the universe is divided into tiny boxes, each containing (say) several thousand gas molecules. The detailed motion inside such a box is ignored, and only the average state of its molecules is considered.
It's a bit like a picture on a computer screen. If you look at it from a distance, you can see cows and trees and all kinds of structure. But if you look sufficiently closely at a tree, all you see is one uniformly green square, or pixel. A real tree would still have detailed structure at this scale leaves and twigs, say -but in the picture all this detail is smeared out into the same shade of green.
In this approximation, once 'order' has disappeared below the level of the coarse-graining, it can never come back. Once a pixel has been smeared, you can't unsmear it. In the real universe, though, it sometimes can, because in the real universe the detailed motion inside the boxes is still going on, and a smeared-out average ignores that detail. So the model and the reality are different. Moreover, this modelling assumption treats forward and backward time asymmetrically. In forward time, once a molecule goes into a box, it can't escape. In contrast, in a time-reversal of this model it can escape from a box but it can never get in if it wasn't already inside that box to begin with.
This explanation makes it clear that the Second Law of Thermodynamics is not a genuine property of the universe, but merely a property of an approximate mathematical description.
Whether the approximation is helpful or not thus depends on the context in which it is invoked, not on the content of the Second Law of Thermodynamics. And the approximation involved destroys any relation with Newton's laws, which are inextricably linked to that fine detail. Now, as we said, Shannon used the same word 'entropy' for his measure of the structure introduced by statistical patterns in an information source. He did so because the mathematical formula for Shannon's entropy looks exactly the same as the formula for the thermodynamic concept. Except for a minus sign. So thermodynamic entropy looks like negative Shannon entropy: that is, thermodynamic entropy can be interpreted as 'missing information'. Many papers and books have been written exploiting this relationship -attributing the arrow of time to a gradual loss of information from the universe, for instance. After all, when you replace all that fine detail inside a box by a smeared-out average, you lose information about the fine detail. And once it's lost, you can't get it back. Bingo: time flows in the direction of information-loss.
However, the proposed relationship here is bogus. Yes, the formulas look the same ... but they apply in very different, unrelated, contexts. In Einstein's famous formula relating mass and energy, the symbol c represents the speed of light. In Pythagoras's Theorem, the same letter represents one side of a right triangle. The letters are the same, but nobody expects to get sensible conclusions by identifying one side of a right triangle with the speed of light. The alleged relationship between thermodynamic entropy and negative information isn't quite that silly, of course. Not quite.