How can information (Shannon) entropy decrease ?

[studiot]

The thread is inspired by a claim in a recent thread that information entropy, as defined by Shannon, is the same as the thermodynamic definition of entropy which obeys the Second Law and therefore cannot decrease.

Is this correct ?

Edited February 20, 2022 by studiot

[SuperSlim]

2 hours ago, studiot said:

The thread is inspired by a claim in a recent thread that information entropy, as defined by Shannon, is the same as the thermodynamic definition of entropy which obeys the Second Law and therefore cannot decrease.

I haven't seen that, but I have seen a claim that thermodynamic entropy is connected to Shannon entropy. I personally believe the connection is quite a strong one, mainly because thermodynamic entropy must be considered in any computational device.

 

[Ghideon]

Initial note: I do not have enough knowledge yet to provide an answer but hopefully enough to get a discussion going.

As far as I know entropy is a property of a random variable's distribution, typically a measure of Shannon entropy is a snapshot value at a specific point in time, it is not dynamic.
It is quite possible to create time-variant entropy by having a distribution that evolves with time. In this case entropy can increase or decrease depending on how the distribution is parameterised by time (t).

I would have to read some more before providing an opinion on decreasing Shannon entropy and its connection to physical devices and thermodynamics. An example of what I mean: (source: https://en.wikipedia.org/wiki/Entropy_(information_theory))

Quote

The first 128 symbols of the Fibonacci sequence has an entropy of approximately 7 bits/symbol, but the sequence can be expressed using a formula [F(n) = F(n−1) + F(n−2) for n = 3, 4, 5, ..., F(1) =1, F(2) = 1] and this formula has a much lower entropy and applies to any length of the Fibonacci sequence.

In the example above some actions or computations are required to find the low entropy formula. How is thermodynamic entropy affected by that? This is a part I am not sure about yet.

 

This wikipedia page and it's references may be a starting point for adding more aspects to the discussion: https://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_information_theory

 

 

 

 

 

 

[SuperSlim]

I'll just add this comment: The mathematical Fibonacci sequence can be written down and assumed to be a static picture. That is, it can be assumed to be "free of physics". How accurate is that assumption, though?

[studiot]

OK, thanks for the replies.

Here is my process example for idscussion.

I have a 4 x 4 square board as in the diagram.

On one square I have placed a coin but you cannot see it (you can see the one in the diagram for the purposes of explanation)

In order to 'win' the coin you ask questions that may only be answered yes or no, represented by 1 (yes) and 0 (no)

When you think you have determined the position of the coin you represent the answers to your questions by a string of ones and zeros.

Using the example

Is it in the first column?  -  No
Is it in the second column? - Yes
Is it in the first row?  -  No
Is it in the second row?  -  Yes

represented as information by the string 0101

What happens to the information entropy at each stage of the Q&A  ?

[joigus]

As I understand, Shannon entropy --apart from the trivial difference of being defined in base two, which makes it ln2-proportional to "physical entropy" \( -\sum_{i}p_{i}\ln p_{i} \), so that both are proportional-- is always referred to a part of the universe.

A computer is always a part of the universe, so there is no problem for entropy to decrease in it. That's what Landauer's principle is telling us: When I erase a bit from a computer, I insist the certain circuit is in state 0. That makes the particular state of the circuit predictable. Its state is 0 with probability one, and thus I heat up the universe, because the entropy in my computer goes down. The entropy of a computer, whether classical (binary) or quantum (based on q-bits), or a set of N coins, or whatever other example for Shannon's entropy to be relevant, is but a part of the universe, so its entropy doesn't have to increase necessarily.

I hope that's a satisfactory answer, if I understood you correctly, of course.

 

Edited February 20, 2022 by joigus
minor correction

[studiot]

 

7 minutes ago, joigus said:

As I understand, Shannon entropy --apart from the trivial difference of being defined in base two, which makes it ln2-proportional to "physical entropy" −∑ipilnpi , so that both are proportional-- is always referred to a part of the universe.

A computer is always a part of the universe, so there is no problem for entropy to decrease in it. That's what Landauer's principle is telling us:

I like the first part.

7 minutes ago, joigus said:

When I erase a bit from a computer, I insist the certain circuit is in state 0. That makes the particular state of the circuit predictable. Its state is 0 with probability one,

But this part runs into the difficulty I mentioned with the RAM chip.
Notably the different erasure methods.

For instance I can simply switch off the power to that chip.
Or I can cut one or more address lines making the given cell unavailable.
Or I can perform the more conventional activation of the appropriate address lines and then overwrite a zero into the given cell.

I am sure there are more options.

Edited February 20, 2022 by studiot

[joigus]

37 minutes ago, studiot said:

OK, thanks for the replies.

Here is my process example for idscussion.

I have a 4 x 4 square board as in the diagram.

On one square I have placed a coin but you cannot see it (you can see the one in the diagram for the purposes of explanation)

In order to 'win' the coin you ask questions that may only be answered yes or no, represented by 1 (yes) and 0 (no)

When you think you have determined the position of the coin you represent the answers to your questions by a string of ones and zeros.

Using the example

Is it in the first column?  -  No
Is it in the second column? - Yes
Is it in the first row?  -  No
Is it in the second row?  -  Yes

represented as information by the string 0101

What happens to the information entropy at each stage of the Q&A  ?

In the case you propose, entropy decreases in every step.

0) Initial entropy

\[ 16\times\left(-\frac{1}{16}\log_{2}\frac{1}{16}\right)=\log_{2}2^{4}=4 \] 

1) It's not in the first column (12 possibilities, assume equiprobable):

\[ 4\times\left(-0\log_{2}0\right)+12\times\left(-\frac{1}{12}\log_{2}\frac{1}{12}\right)=\log_{2}12=\log_{2}4+\log_{2}3=2+\log_{2}3<4 \]

2) It's in the second column (4 possibilities, assume equiprobable):

\[ 4\times\left(-\frac{1}{4}\log_{2}\frac{1}{4}\right)=\log_{2}4=2<2+\log_{2}3 \]

3) It's not in the first row (3 possibilities, assume equiprobable):

\[ 3\times\left(-\frac{1}{3}\log_{2}\frac{1}{3}\right)=\log_{2}3<2+\log_{2}3 \]

4) It's in the second row (1 possibility, entropy is zero):

\[ -1\log_{2}1=0<\log_{2}3 \]

Entropy has decreased in every step, and there's nothing wrong with it.

28 minutes ago, studiot said:

But this part runs into the difficulty I mentioned with the RAM chip.
Notably the different erasure methods.

For instance I can simply switch off the power to that chip.
Or I can cut one or more address lines making the given cell unavailable.
Or I can perform the more conventional activation of the appropriate address lines and then overwrite a zero into the given cell.

I am sure there are more options.

I'll think about this in more detail later.

I think I see your point about the RAM circuit, and it reminds me of a question that somebody posed about Landauer's principle years ago. Very interesting!

But I would have to go back to mentioned thread.

One thing I can tell you for sure: You will have to increase the universe's entropy if you want to know where the coin is. There's no way around it: You have to look at the coins; for that you need light, and in focusing your light you will have to set some machinery in motion that will disturb the environment more than you order your system.

So Shannon and Boltzmann are joined at the hip.

[SuperSlim]

The non-informational d.o.f of a physical system must have effectively infinite dimensions. This seems to be a necessity to erase all evidence of some information-bearing physical quantity, such as a fixed amount of charge in a digital computer.

It can't even be like burning paper, which "erases" a written message; there is evidence that a message was "erased" so, in principle the message is still around. Not all the IBDGs have been dissipated into an ocean of "no information".

[joigus]

3 minutes ago, SuperSlim said:

The non-informational d.o.f of a physical system must have effectively infinite dimensions. This seems to be a necessity to erase all evidence of some information-bearing physical quantity, such as a fixed amount of charge in a digital computer.

It can't even be like burning paper, which "erases" a written message; there is evidence that a message was "erased" so, in principle the message is still around. Not all the IBDGs have been dissipated into an ocean of "no information".

This would be true in classical mechanics. Nevertheless, in classical mechanics you can still asign a measure to the phase space (space of possible states). So even in classical mechanics, which asigns a system infinitely many states, entropy is finite. Entropy is related to the measure of phase space:

https://en.wikipedia.org/wiki/Entropy_(information_theory)#Measure_theory

It is definitely not true when quantum mechanics makes an appearance. All systems are spatially finite. If they're finite, their momentum is quantized, and the basis of wave functions becomes a countable set.

Also, there is no such a thing as non-informational DOF of a physical system. All DOF are on the same footing.

There are two concepts of entropy; one is the fine-grained entropy, which corresponds to the volume (measure) of the phase space, and the coarse-grained entropy, which depends on how much information we have on the system. The total content of information is constant. It cannot be lost.

INFORMATION = information - entropy = volume (phase space)

Where by INFORMATION (in capitals) I mean the negative of fine-grained entropy; and by information (in lower-case letters) I mean the negative of coarse grained entropy.

You're also confusing #(dimensions) with #(elements) = cardinal. Those are different things.

[SuperSlim]

Quote

Also, there is no such a thing as non-informational DOF of a physical system. All DOF are on the same footing.

Right, a computer is indeed a physical system; however an active computation sees heat as non-informational, in an electronic computer.

A quote from Charles C Bennett (the inventor of the Brownian motion computer).

Quote

While a computer as a whole (including its power supply and other parts of its environment), may be viewed as a closed system 
obeying reversible laws of motion (Hamiltonian or, more properly for a quantum system, unitary dynamics), Landauer noted that the logical state often evolves irreversibly, with two or more distinct logical states having a single logical successor. Therefore, because Hamiltonian/unitary dynamics conserves (fine-grained) entropy, the entropy decrease of the IBDF during a logically irreversible operation must be compensated by an equal or greater entropy increase in the NIBDF and environment. This is Landauer’s principle.

--https://arxiv.org/pdf/physics/0210005.pdf

Edited February 21, 2022 by SuperSlim

[SuperSlim]

Information: it's something whose nature depends on a choice. It can be all kinds of physical objects, but computation is a different level. Information can be defined in terms of static objects with fixed physical values, but computation has to transform some information, there has to be an information-transport mechanism that takes inputs to outputs.

It seems that if we choose electric charge to be a computational basis (the presence or absence of fixed amounts), then we restrict the choice for erasure. Erasure has to mean a complete lack of any "forensic charges" left lying around, there has to be a large number of d.o.f. when electrons dissipate so a charge vanishes from some location (where it might have been stored briefly, or been conducted through a transistor, etc.). Erasure is by definition the same type of local change as storage.

Edited February 21, 2022 by SuperSlim

[studiot]

6 hours ago, SuperSlim said:

Erasure is by definition the same type of local change as storage.

No it isn't.

This is where my RAM example comes in.

The information may be set but unavailable, which has the same effect as being reset.

This would be an example of the Caratheodory version of the second law.

"In any system, there are nearby local states that are unavailable to the system"

 

A computation that involves no energy is the topological transformation of a square to a circle.

The information is available whether the actual transformation is performed or not and whether the necessary topological theory has ever been conceived, let alone enacted.

You have now also mentioned this idea

9 hours ago, SuperSlim said:

So is there something like a "Kirchoff's algorithm" for chemistry? If you can define an abstract machine and paths through it, and algorithms, well, maybe.

 

 

 

 

10 hours ago, joigus said:

In the case you propose, entropy decreases in every step.

Thank you for spelling all that out in detail  +1

10 hours ago, joigus said:

I think I see your point about the RAM circuit, and it reminds me of a question that somebody posed about Landauer's principle years ago. Very interesting!

My apologies, I didn't lin to the originating thread.

https://www.scienceforums.net/topic/126656-experiments-and-information/?tab=comments#comment-1200346

 

Edited February 21, 2022 by studiot

[SuperSlim]

6 hours ago, studiot said:

No it isn't.

This is where my RAM example comes in.

The information may be set but unavailable, which has the same effect as being reset.

I'm not sure what you mean, there. In a deterministic machine (a digital computer running a program) storage and erasure are not concerned with "unavailable information".

Storage and erasure are logical operations; both are local, not global, operations. A global reset is something not usually considered to be a program although it does leave the sytem in a known state. Powering down a computer is one way to leave it in a known state.

6 hours ago, studiot said:

A computation that involves no energy is the topological transformation of a square to a circle.

Computation without energy doesn't make a lot of sense to me. If information is being transformed, and if information is physical, how can it be transformed without a source of energy to physically transform it? Or are you just pointing out that a square is topologically already a circle, no computing required?

[studiot]

5 hours ago, SuperSlim said:

I'm not sure what you mean, there. In a deterministic machine (a digital computer running a program) storage and erasure are not concerned with "unavailable information".

Storage and erasure are logical operations; both are local, not global, operations. A global reset is something not usually considered to be a program although it does leave the sytem in a known state. Powering down a computer is one way to leave it in a known state.

Computation without energy doesn't make a lot of sense to me. If information is being transformed, and if information is physical, how can it be transformed without a source of energy to physically transform it? Or are you just pointing out that a square is topologically already a circle, no computing required?

 

Well I'm sorry if all you want to do is make unqualified generalistic pronouncements , one counter example is enough to disprove your claim.

 

18 hours ago, SuperSlim said:

but computation has to transform some information,

Mathematical theory requires that there be such a thing as 'the identity transformation' for any operation or transformation.

Such a transformation require exactly zero energy since no change occurs.

 

 

However I would much rather you entered a proper discussion like other members here and addressed some of the points, posted for your benefit.

You have made no visible attempt to answer the question posed in the opening post or thread title or to discuss entropy.

 

 

[SuperSlim]

On 2/21/2022 at 8:54 AM, studiot said:

The thread is inspired by a claim in a recent thread that information entropy, as defined by Shannon, is the same as the thermodynamic definition of entropy which obeys the Second Law and therefore cannot decrease.

Is this correct ?

Let me at least try, once again then.

It is not correct that the claim you refer to, which I made, is that Shannon entropy and thermodynamic entropy have the same definition. Neither is it correct, as you conclude, that entropy cannot decrease. You have perhaps forgotten what thermodynamic entropy is, or you haven't grasped the significance of Maxwell's demon.

I guess the last thing there is excusable to some extent, it took over a century to explain why it can't violate the laws of physics.

14 minutes ago, studiot said:

However I would much rather you entered a proper discussion like other members here and addressed some of the points, posted for your benefit.

I honestly think I have been addressing them. I've already noticed that some posters here seem to have a problem with understanding what a computer is.

That's actually a bit of a worry; I'm not sure I'm discussing the subject with people who really know what the word means. You yourself appear to have just suggested I can build a computer that doesn't have to erase information if It doesn't do anything.  So I have to ask, do you really know what a computer is?

 

Edited February 21, 2022 by SuperSlim

[studiot]

10 minutes ago, SuperSlim said:

Let me at least try, once again then.

It is not correct that the claim you refer to, which I made, is that Shannon entropy and thermodynamic entropy have the same definition. Neither is it correct, as you conclude, that entropy cannot decrease. You have perhaps forgotten what thermodynamic entropy is, or you haven't grasped the significance of Maxwell's demon.

I guess the last thing there is excusable to some extent, it took over a century to explain why it can't violate the laws of physics.

Thank you for trying.

Please state exactly what you think is the difference between thermodynamic entropy and Shannon (or Hartley) entropy and what exactly you think the Second Law says about both of them.

[SuperSlim]

3 minutes ago, studiot said:

Please state exactly what you think is the difference between thermodynamic entropy and Shannon (or Hartley) entropy and what exactly you think the Second Law says about both of them.

Ok. Maybe tomorrow if I can find the time.

p.s. Please state exactly why you think building a computer that does nothing, so doesn't generate any heat, is a counterexample to what I said.

Edited February 21, 2022 by SuperSlim

[studiot]

5 minutes ago, SuperSlim said:

Ok. Maybe tomorrow if I can find the time.

p.s. Please state exactly why you think building a computer that does nothing, so doesn't generate any heat, is a counterexample to what I said.

Do you deny the mathematics of the identity transformation ?

Or do you deny that a computer that can perform exactly one transformation (the identity transformation) is a computer ?

[SuperSlim]

Why does your question seem so bloody irrelevant?

I wonder if Maxwell spent a whole morning figuring out whether to have his demon sit around doing nothing?

I've just been shown a sign. It starts with Church and ends with Turing. A Turing machine that doesn't erase any symbols on a tape is equivalent to a finite-state acceptor; it accepts a string but if there's a programmed halt condition and a return to a "start of tape", that's an output, it's information.

But not to the Turing machine itself, because it's just another symbol in an overall string which hasn't changed--the identity operation.

If that's how you decide to define the identity operation. But it implies that all read-only Turing machines are just FSA's with the important distinction of the start-of-tape halt condition. That includes those machines that hop around, the FSA-only ones could hop around the string forever and never halt.

 

 

Edited February 21, 2022 by SuperSlim

[studiot]

 

17 hours ago, SuperSlim said:

17 hours ago, studiot said:

Please state exactly what you think is the difference between thermodynamic entropy and Shannon (or Hartley) entropy and what exactly you think the Second Law says about both of them.

Ok. Maybe tomorrow if I can find the time.

p.s. Please state exactly why you think building a computer that does nothing, so doesn't generate any heat, is a counterexample to what I said.

 

16 hours ago, SuperSlim said:

Why does your question seem so bloody irrelevant?

I wonder if Maxwell spent a whole morning figuring out whether to have his demon sit around doing nothing?

I've just been shown a sign. It starts with Church and ends with Turing. A Turing machine that doesn't erase any symbols on a tape is equivalent to a finite-state acceptor; it accepts a string but if there's a programmed halt condition and a return to a "start of tape", that's an output, it's information.

But not to the Turing machine itself, because it's just another symbol in an overall string which hasn't changed--the identity operation.

If that's how you decide to define the identity operation. But it implies that all read-only Turing machines are just FSA's with the important distinction of the start-of-tape halt condition. That includes those machines that hop around, the FSA-only ones could hop around the string forever and never halt.

 

 

I don't see this as a difference difference between thermodynamic entropy and Shannon (or Hartley) entropy or any statement about the Second Law.

 

Since you don't want to answer the question, for my part I think the most significant difference is that

Once you have perfomed a computation and incurred whatever resource price the universe exacts in terms of energy, entropy etc, you do not have to incur those costs again since the result of that computation is then known, the next time it is required.

However in thermodynamics the universe exacts its pound of flesh each and every time the given process is run or occurs.

 

 

[Ghideon]

3 hours ago, studiot said:

Once you have perfomed a computation and incurred whatever resource price the universe exacts in terms of energy, entropy etc, you do not have to incur those costs again since the result of that computation is then known, the next time it is required.

However in thermodynamics the universe exacts its pound of flesh each and every time the given process is run or occurs.

I agree that the result of computation is known. How do you retrieve the known result again later; does that require (some small) cost?  

Note: I'm not question your statement, just curious to understand it correctly for further reading.

 

edit: Here are two papers that may be of interest for those following this thread:

1: Critical Remarks on Landauer’s principle of erasure–dissipation https://arxiv.org/pdf/1412.2166.pdf 

This paper discusses examples that as far as I can tell are related to @studiot's example of RAM

Quote

Do computers execute erasure when they discard information? The answer is usually “no” since, in practice, they do not reset the memory bits but just change the address of the boundary of the free part of memory

2:https://arxiv.org/pdf/1311.1886.pdf Thermodynamic and Logical Reversibilities Revisited

The second paper investigates erasure of memory: 

Quote

In this section, we discuss the conventional Landauer principle [7], and clarify the relationship between the thermodynamic and logical reversibilities in the standard setup of information erasure.

(I have not yet read both papers in detail)

Edited February 22, 2022 by Ghideon
added papers

[studiot]

50 minutes ago, Ghideon said:

I agree that the result of computation is known. How do you retrieve the known result again later; does that require (some small) cost?  

Note: I'm not question your statement, just curious to understand it correctly for further reading.

Thank you for a thoughtful, pleasant and cooperative reply.  An example to everyone. +1

I don't think I said that there is no cost to storing (and retrieval)  -  certainly I did not mean to imply that.

Here is an admitedly extreme example.

Let us suppose the computation takes 3 hours of running the met office supercomputer and the output result is the temperature  at 9 pm in Trafalgar Square at 7.3^oC.

How much resource does it take to store the result compared to how much it would take to exactly repeat the calculation ?

 

I will certainly look at your references with interest.

[SuperSlim]

4 hours ago, studiot said:

I don't see this as a difference difference between thermodynamic entropy and Shannon (or Hartley) entropy or any statement about the Second Law.

Neither do I. It's something I aimed at your idea of a computer that only has an identity operation; the input is the same as the output. Perhaps you missed it.

 

4 hours ago, studiot said:

Once you have perfomed a computation and incurred whatever resource price the universe exacts in terms of energy, entropy etc, you do not have to incur those costs again since the result of that computation is then known, the next time it is required.

That's a somewhat simplified version of what a computation is; actually what that is is a way to classify computations: all those computations that have a known output and don't need to run again, plus all the computations that run again despite not having to. It might be a useful distinction, but it is only a distinction.

But I see you have a way to go to. A computation is not something that comes with a fixed time to compute; we build "fast" computers, we get results "quickly", but that is a choice, it really doesn't affect what computation is. It doesn't affect what transmission of information is either.

Edited February 22, 2022 by SuperSlim

[studiot]

20 minutes ago, SuperSlim said:

Neither do I. It's something I aimed at your idea of a computer that only has an identity operation; the input is the same as the output. Perhaps you missed it.

So why did you 'aim' such  personally abusive remarks instead of answering the question you still have not answered?

20 minutes ago, SuperSlim said:

That's a somewhat simplified version of what a computation is; actually what that is is a way to classify computations: all those computations that have a known output and don't need to run again, plus all the computations that run again despite not having to. It might be a useful distinction, but it is only a distinction.

But I see you have a way to go to. A computation is not something that comes with a fixed time to compute; we build "fast" computers, we get results "quickly", but that is a choice, it really doesn't affect what computation is. It doesn't affect what transmission of information is either.

So you are now shifting your ground, when I point out that the energy or entropy involved in computation (and it does not matter how long or how much) can vary simply because obtaining the result can take different routes.

This is not the case with thermodynamics which is founded on the idea of route independence between defined states.

Edited February 22, 2022 by studiot