Lockless algorithms for mere mortals

Posted Jul 29, 2020 6:11 UTC (Wed) by madhatter (subscriber, #4665)
In reply to: Lockless algorithms for mere mortals by ras
Parent article: Lockless algorithms for mere mortals

You seem to be proposing that the 2nd law of thermodynamics (2T) says that, when evaluated over the universe as a whole, entropy must always rise. You say that it's fine for it to temporarily drop in certain lucky locales, it's just that the number of spontaneously melting ice cubes in cups of tea significantly outweighs the number of spontaneously freezing ones in similar cups of tea, and so over the universe as a whole entropy still rises.

It's been a long time since I was a professional physicist, but as I recall 2T says that in any isolated system the entropy count can never decrease. 2T is a local, as well as a global, truth. That is to say, unless there's an interaction across the system border of any given nearly-melted ice cube in a cup of tea - eg, I stick a cooling coil in and shunt heat outside the local system - it can't spontaneously refreeze. A thermodynamically-exploitable temperature gradient will not spontaneously arise without intervention.

The casino analogy is a poor one because very few players in a casino are isolated. Any player who is - one playing solitaire in a broom cupboard, for example - will find that they never win big, because there's nobody to win from. Moreover, they can only not lose if they stop eating the chips (entropy count must rise in an isolated system unless all local processes are thermodynamically reversible).

Lockless algorithms for mere mortals

Posted Jul 29, 2020 7:43 UTC (Wed) by ras (subscriber, #33059) [Link] (1 responses)

> A thermodynamically-exploitable temperature gradient will not spontaneously arise without intervention.

My guess is that is demonstrably false. Lets say your system consists of 3 gas molecules 3m x 3m x 3m room. I doubt anyone's checked, but it seems certain those 3 molecules will end up on one side of the room at some point.

That is not terribly realistic of course. In real life a 3m x 3m x 3m room at 1atm has about 5e25 molecules in it. Statistically, I think we can say we are fairly safe from someone's ear drums bursting because all the air ended up on one side of the room. However, nothing has changed except the number of molecules. As far as I know nothing in physics says the universe behaves differently because that number has changed.

Your mind is now telling you that you can extract energy from that if it happened, so it must violate the 1st law of thermodynamics. I don't know the answer to that, but I don't feel too bad about it because it took about 50 years to figure out why Maxwell's daemon was a myth. I'm sure the universe has accounted for it somehow. It probably has to do with the fact that you have to wait for the universe goes dark to have a fair chance it will happen, and by that time the 2nd law has recovered the energy from you evaporating. [0]

> The casino analogy is a poor one because very few players in a casino are isolated

You play against the house, not the other players. Example: in Keno, the odds a published and fixed. So you can place a minimum bet and win the maximum even if no one else plays that round.

[0] That was a joke. Well part of it was. If it's not accounted for somewhere, it's where dark energy comes from [1].

[1] Also a joke. I really have no idea. [2]

[2] Actually, it could well be the Maxwell daemon thing again. Sitting there, actively monitoring the room so you know when all the gas molecules are on one side of the room takes an external energy source.

Lockless algorithms for mere mortals

Posted Sep 6, 2020 17:43 UTC (Sun) by nix (subscriber, #2304) [Link]

> [2] Actually, it could well be the Maxwell daemon thing again. Sitting there, actively monitoring the room so you know when all the gas molecules are on one side of the room takes an external energy source.

This was figured out a decade or so ago. You don't need the cost of monitoring: even if that's zero, the mere fact that the demon has to make a decision about whether to allow a given molecule through or not is enough to ensure that the entropy of the system (demon + box) always increases, given that the demon's memory capacity is finite such that it eventually has to erase the states of some of its memory (increasing its entropy) in order to make more decisions about whether to let molecules through.

Lockless algorithms for mere mortals

Posted Jul 29, 2020 7:46 UTC (Wed) by cyphar (subscriber, #110703) [Link] (7 responses)

I don't think you're disagreeing with @ras -- the reason why the second law of thermodynamics applies to any closed system is because it is so statistically unlikely so as to be impossible for a closed system to move towards a lower-entropy state. The second law of thermodynamics isn't magic and it isn't a force being applied to thermodynamic systems -- it's a consequence of the fact that thermodynamic systems have so many microstates that the probability random perturbations will result in you moving to a lower-entropy microstate is effectively zero.

However, if you had a thermodynamic system with a handful of particles, you would observe the system move into lower entropy configurations purely by chance. All of the interactions occurring in thermodynamics are reversible, it's just that the likelihood of such interactions occurring is effectively zero. The same applies to even more mundane physics like the kinematics of billiard balls -- if you imagine a perfectly-spaced grid of one billion billiard balls being struck by another ball, while the interaction is entirely reversible it's incredibly unlikely that you'd be able to collide the balls in such a way that they would form a perfectly-spaced grid. The second law of thermodynamics is just a far more formalised version of that intuition.

Lockless algorithms for mere mortals

Posted Jul 29, 2020 8:31 UTC (Wed) by Wol (subscriber, #4433) [Link] (6 responses)

And this is where it gets messy. DEFINE ENTROPY.

Sorry, I can't quote the source beyond "I saw it in New Scientist", but there was a wonderful article where someone had two different (equally plausible) definitions of entropy, AND ONE OF THEM DECREASED.

The conclusion was the 2nd law was still valid, but it was no longer entropy it was measuring. It was information. Because iirc that made the correct selection between the two different definitions of entropy.

Isn't science wonderful :-)

Cheers,
Wol

Lockless algorithms for mere mortals

Posted Jul 29, 2020 9:02 UTC (Wed) by Cyberax (✭ supporter ✭, #52523) [Link] (2 responses)

> DEFINE ENTROPY
Easy. It's the number of microstates of a system. There are other ways to re-formulate this definition, but they are equivalent to each other.

Lockless algorithms for mere mortals

Posted Jul 29, 2020 11:18 UTC (Wed) by Wol (subscriber, #4433) [Link] (1 responses)

How come those two states were equally plausible but different?

Mind you, your definition looks like the new version "information == entropy".

Cheers,
Wol

Lockless algorithms for mere mortals

Posted Jul 29, 2020 16:28 UTC (Wed) by Cyberax (✭ supporter ✭, #52523) [Link]

It's not information per se. Entropy is simply the measure of the number of microstates of a system, and that's all it is.

Lockless algorithms for mere mortals

Posted Jul 30, 2020 1:55 UTC (Thu) by cyphar (subscriber, #110703) [Link] (2 responses)

In thermodynamics, S = k_B ln Ω by definition. The term "entropy" is used in many different fields (such as computer science) and can mean different things (such as Shannon entropy), but in thermodynamics it has a specific meaning -- it is a measure of the number of microstates which appear as a single macrostate. Entropy increases because systems tend towards the macrostates which have the most microstates (again, purely because of statistics).

Lockless algorithms for mere mortals

Posted Jul 31, 2020 21:06 UTC (Fri) by NYKevin (subscriber, #129325) [Link] (1 responses)

> Entropy increases because systems tend towards the macrostates which have the most microstates (again, purely because of statistics).

The problem with this argument is that it is time-symmetric. In other words, you can just as easily argue that the present macrostate is more likely to have evolved from past macrostates which had more microstates. Observation tells us that the time-reversed argument is empirically wrong (because we observe entropy increasing as a function of time), which is a bit of a problem because it appears to be symmetric with the (empirically correct) non-reversed argument. The only (obvious) way to break this symmetry is to assert a boundary condition of low entropy at or near the beginning of the universe. This boundary condition, IMHO, is the real mystery: Why did the early universe have such low entropy? I don't think we have a working answer to that question (yet).

Lockless algorithms for mere mortals

Posted Aug 1, 2020 4:11 UTC (Sat) by ras (subscriber, #33059) [Link]

> In other words, you can just as easily argue that the present macro state is more likely to have evolved from past macro states which had more microstates.

Actually no, you can't. In the definition of entropy the number of microstates is fixed and you are measuring how many of those microstate arrangements look like a given macro state.

That aside, no one is disputing there is a thermodynamic arrow of time. The argument being made is that all transitions between microstates are reversible, lossless in terms of information and equally likely in both directions. It's possible for that to be true for micro states and yet there be preferred direction for the evolution of macro states. It's not only possible, it's what happens.

It's not only what happens, there is no mystery as to why it happens. For example, take a go board covered with black and white stones and assume we are near blind. If all black stones are on one side of the board and white on the other we can see that, so black/white is a macro state, but the rest of the possible microstate arrangements just look like grey to us, so grey is another macro state. Back/white corresponds to a few micro states where the black and white stores are poorly mixed. I think there are 361! / 181! possible board arrangements or about 10^431. Most of those states will look just grey - a random mixture of black and white. If the pieces are moving randomly, all of the microstates will be equally likely. This means the odds of seeing black/white instead of grey look to be about 1 in 10^245 if you assume 10% can be out of place. [0] If your go board starts in the black / white macro state, then is allowed to evolve through random 100% completely reversible symmetric swaps you will see it change to grey, and stay that way.

That is the thermodynamic arrow of time. Yet it arose from a completely reversible process. Microstates and macro states are both reasonable ways of looking at the system. When we say time is reversible, we are talking about the former.

[0] Caveat: I am deriving the formulas for these probabilities in my head, as I write this. They are almost certainly wrong.

Lockless algorithms for mere mortals

Posted Jul 29, 2020 18:27 UTC (Wed) by ianmcc (subscriber, #88379) [Link]

The second law is about probabilities. For an isolated system, the probability that entropy decreases in some given time period is exponentially small in the number of degrees of freedom. For a sufficiently small system, this will happen quite often. For a macroscopic system the probability is so small that you will never see it in the lifetime of the universe. But in principle, every isolated system eventually returns to its initial state (this is the Poincaré
recurrence theorem), so in that sense the entropy is cyclic, if you start from a very low entropy state then eventually it will return to that low entropy state again. But the time it takes to get there is again exponentially large in the number of particles, so the time required very quickly exceeds any sensible number (even using units of the lifetime of the universe).