A. Entropy

What is Entropy?

Entropy is a measure of uncertainty, surprise, or irreducible description length. The exact meaning depends on the conceptual model of data you adopt. This page compares three influential paradigms—Shannon, Turing/Algorithmic, and a Hossack-style ontological lens—and shows how “entropy” fits (or doesn’t) in each.

---

TL;DR

• Shannon entropy: Average unpredictability of symbols from a source; equals the best achievable average code length when compressing those symbols.

• Algorithmic (Turing) entropy / Kolmogorov complexity: Shortest program length that outputs a specific object; measures its intrinsic compressibility.

• Ontological (Hossack-style): Truths/facts don’t have entropy; our beliefs about which truth obtains do. Entropy here is epistemic, not ontological.

---

1) Shannon Information Entropy (Communication Paradigm)

Setup. A random source emits symbols from an alphabet with probabilities (p(x)).

Definition. (H(X) = -\sum_x p(x),\log_2 p(x)) bits.

Meaning.

• Uncertainty: Higher when outcomes are more uniform and unpredictable.

• Coding Theorem: (H(X)) is the best achievable average number of bits per symbol for any (lossless) compressor matched to (p).

Use when you have (or posit) a probability model for your data source and care about transmission, compression, or rate–distortion.

Example. A fair coin has (H=1) bit; a biased coin with (p(\text{Heads})=0.9) has (H\approx 0.469) bits.

---

2) Algorithmic Entropy (Turing/Computation Paradigm)

Setup. Data are finite strings. Explanations are programs running on a universal Turing machine (U).

Definition. Kolmogorov complexity (K_U(x)): the length (in bits) of the shortest program that outputs (x) and halts.

Meaning.

• Intrinsic structure: If (x) is highly regular, (K(x)) is small (short description). If (x) is patternless, (K(x)) is near (|x|) (incompressible).

• Distribution-free: No need to assume a source model; applies to individual objects.

• Bridge to Shannon: For computable distributions (P), typical strings satisfy (K(x) \approx -\log_2 P(x)) up to constants; expected (K) tracks Shannon code length.

Use when you care about model selection/MDL, structure discovery, or reasoning about the complexity of specific data without a trusted probabilistic source.

Notes. (K(x)) is uncomputable in general; in practice we approximate via compressors (LZ, BWT, etc.) or MDL criteria.

---

3) Entropy under an Ontological (Hossack-style) View

Setup. Mathematical and logical structures (facts, propositions, states of affairs) exist independently of observation; truths are necessary or mind-independent.

Claim. Entropy does not attach to the truths themselves (they don’t vary or “surprise”). Entropy attaches to our epistemic state—our probability distribution over which proposition/fact obtains.

Meaning.

• Entropy here measures ignorance/credence dispersion (agent-relative), not a property of the world’s abstract structures.

• Once the truth is known, entropy about that proposition collapses to zero, though the truth itself didn’t change.

Use when clarifying the status of uncertainty in mathematics, logic, or ontology: entropy is a tool for agents, not a feature of necessary structures.

---

Unifying Picture

Question	Shannon	Algorithmic (Turing)	Ontological (Hossack-style)
What is data?	Draws from a probabilistic source	A finite object/string for computation	A truth-bearing structure; facts/propositions
What is entropy?	Expected surprise / optimal average codelength	Shortest effective description of the specific object	Agent’s uncertainty over which truth obtains
Needs a distribution?	Yes	No	Only as a model of belief (credences)
Typical application	Communication, compression, channel capacity	MDL, anomaly detection, structure discovery	Epistemology of math/logic; clarifying agent ignorance

---

Practical Guidance

• Have a source model? Use Shannon entropy (or cross-entropy) for coding, compression, and ML losses.

• No reliable model? Use algorithmic ideas: approximations to (K(x)) (compressors), MDL, description-length penalties.

• Doing foundations/philosophy? Be explicit: entropy quantifies your epistemic state, not the being of mathematical truths.

---

Common Pitfalls & Myths

• “High entropy means randomness everywhere.” Not necessarily: a deterministic process can produce a distribution with high entropy over outputs.

• “Entropy is always about thermodynamics.” In data contexts, it’s about information (though there are deep links via statistical mechanics).

• “Kolmogorov complexity is computable.” It isn’t; you must approximate.

---

Worked Micro‑Examples

1. Shannon: Alphabet {A,B} with (p(A)=p(B)=1/2) ⇒ (H=1) bit. With (p(A)=0.9), (H\approx 0.469) bits.

2. Algorithmic: The string 010101... (length 1,000) has a tiny description: “print ‘01’ 500 times.” (K(x)) ≪ 1,000. A typical random 1,000‑bit string has (K(x)) ≈ 1,000.

3. Ontological: The proposition “There are infinitely many primes” has no entropy. Your credence about its truth might once have had positive entropy; after learning Euclid’s proof, your credence distribution collapses.

---

See Also

• Cross-entropy & KL divergence

• Mutual information & channel capacity

• Minimum Description Length (MDL)

• Entropy in statistical mechanics (Boltzmann/Gibbs)

---

Further Reading (short list)

• Shannon, C. E. (1948). A Mathematical Theory of Communication.

• Cover & Thomas. Elements of Information Theory.

• Li & Vitányi. An Introduction to Kolmogorov Complexity and Its Applications.

• Grünwald. The Minimum Description Length Principle.

• (Foundations) Discussions on facts/propositions, mereology, and complex unities; relations between truth and structure.

Think of “entropy” as a yardstick for uncertainty or description length—but what counts as “uncertainty” depends on the model of data you’re using.

Snapshot: entropy across three paradigms

Paradigm	What “data” is	What “entropy” measures
Shannon (communication/information theory)	Symbols drawn from a probabilistic source	Average unpredictability of symbols: $(H(X)=-\sum_x p(x)\log p(x))$ . Also the best achievable average code length per symbol.
Turing (computation/description/algorithmic)	Finite strings processed by a (universal) Turing machine	Algorithmic entropy = Kolmogorov complexity: the length of the shortest program that outputs the string. Measures irredundant information / incompressibility of an individual object.
Hossack (ontological, truth-based structures)	Truths about complex unities (facts/propositions/states of affairs) that exist independently of us	Entropy is not intrinsic to these truths. At most it’s epistemic: a measure of our credence-distribution over which fact obtains—uncertainty in us, not in the structure itself.

---

How to justify “entropy” in Turing’s framework

Turing gives you a computational microscope: data are strings; explanations are programs. This naturally leads to algorithmic information theory:

1. Fix a universal Turing machine (U).
   For any finite string (x), its Kolmogorov complexity (K_U(x)) is the length (in bits) of the shortest input (p) such that (U(p)=x).

2. Interpretation.

   • (K(x)) is the minimal description length of (x).

   • If (x) has patterns, you can describe it concisely; if not, (K(x)) is about the length of (x) itself (it’s algorithmically random).

3. Why call this “entropy”?

   • In Shannon’s world, entropy is expected code length under a known distribution.

   • In Turing’s world, when no reliable distribution is known, (K(x)) plays the role of an individual-sequence entropy: the best-possible codelength any computable compressor can achieve on that specific (x).

   • Coding theorems connect the two: for a computable distribution (P), the expected (K(x)) over (P) tracks Shannon codelengths (roughly, $(K(x)\approx -\log P(x))$ up to constants). Thus algorithmic entropy generalizes Shannon’s from distributions to single objects.

So, Turing justifies entropy by replacing probabilities with program-length optimality. Entropy becomes “how short can the best explanation be?”—fully aligned with the Turing paradigm of data as inputs to computation.

---

Where does that leave Hossack?

Hossack grounds mathematics and sets in truth-bearing complex unities (facts, propositions, states of affairs). On this view:

• The relevant structures (numbers, orders, sets in an NFU-style model, etc.) exist necessarily; truth is secured by the correspondence of beliefs/statements to these unities.

• Entropy doesn’t attach to the structures (they’re not chancy). It can only attach to our uncertainty over which truth/fact obtains, i.e., to a probability distribution over propositions we entertain. In other words, entropy is epistemic bookkeeping for agents navigating an ontologically fixed landscape.

If you like a slogan:

Shannon: entropy is about surprise when symbols arrive.
Turing: entropy is about how short the best explanation is.
Hossack: entropy is about our ignorance, not the facts themselves.

---

Bonus: fitting the pieces together

• Use Shannon entropy when you have (or posit) a source distribution and care about coding/communication.

• Use algorithmic (Turing) entropy when you care about model selection, MDL, or intrinsic structure of particular data objects—no distribution assumed.

• Use a Hossack-style lens to remind yourself that whatever entropy you compute is about agents and access, not about being. The structures you learn about don’t fluctuate; your knowledge does.