 # Complexity Explorer Santa Few Institute ## Introduction to Renormalization

• Introduction
• Coarse graining Alice and Dinah
• Coarse graining part I - Clustering algorithms
• Coarse graining part II - Entropy
• Markov Chains
• Mathematics of coarse grained Markov chains
• Mathematics of Coarse grained Markov Chains: The General Case
• A puzzle: origin of the slippy counter
• Where we are so far
• Cellular Automata: Introduction
• Israeli and Goldenfeld; projection and commuting diagrams
• Networks of Renormalization
• Coarse-graining the Lattice
• From Quantum Electrodynamics to Plasma Physics
• Conclusion: Keeping the things that matter
• Homework

#### 5.2 Irreversible Computations, Forgetful Computers and the Krohn-Rhodes Theorem » Quiz Solution

What is a semi-group?

A. a subset of a group's moves (of the things you can do to a normal creature)
B. a creature where some of the moves can not be universally "undone"
C. a creature with a move that takes it invariably to a unique internal state regardless of current state.
D. (B), with (C) as a special case.

Answer (D). A creature of type (C) has a reset move built in; but creatures like (B) are the more general case of systems with irreversible operations. These are called semi-groups. The Krohn-Rhodes theorem tells you that all creatures of type (B) have, in their hierarchical decomposition, a "reset" machine of like (C).